[Wf2016]Branch Assignment题解

P6918 [ICPC 2016 WF] Branch Assignment

题目描述

创新消费品公司（ICPC）计划启动一个绝密项目。该项目由sss个子项目组成。将有b≥sb \ge sb≥s个 ICPC 的分支机构参与此项目，ICPC 希望将每个分支机构分配给一个子项目。换句话说，这些分支机构将形成sss个不相交的组，每个组负责一个子项目。

每个月底，每个分支机构将向其组内的每个其他分支机构发送一条消息（每个分支机构接收不同的消息）。ICPC 有一个特定的通信协议。每个分支机构iii有一个只有该分支机构和 ICPC 总部知道的密钥kik_iki​。假设分支机构iii想要向分支机构jjj发送消息。分支机构iii用其密钥kik_iki​加密消息。一个可信的信使从该分支机构取走消息并将其交付给 ICPC 总部。总部用密钥kik_iki​解密消息，并用密钥kjk_jkj​重新加密。然后信使将这个新加密的消息交付给分支机构jjj，分支机构jjj用其自己的密钥kjk_jkj​解密。出于安全原因，信使一次只能携带一条消息。

给定一个道路网络以及分支机构和总部在此网络中的位置，你的任务是确定信使在所有可能的分支机构到子项目的分配中，传递所有月底消息所需的最小总距离。

输入格式

输入的第一行包含四个整数nnn、bbb、sss和rrr，其中nnn(2≤n≤5 0002 \le n \le 5\, 0002≤n≤5000) 是交叉路口的数量，bbb(1≤b≤n−11 \le b \le n-11≤b≤n−1) 是分支机构的数量，sss(1≤s≤b1 \le s \le b1≤s≤b) 是子项目的数量，rrr(1≤r≤50 0001 \le r \le 50\, 0001≤r≤50000) 是道路的数量。交叉路口编号从111到nnn。分支机构位于交叉路口111到bbb，总部位于交叉路口b+1b + 1b+1。接下来的rrr行中的每一行包含三个整数uuu、vvv和ℓ\ellℓ，表示从交叉路口uuu到不同交叉路口vvv(1≤u,v≤n1 \leq u,v \leq n1≤u,v≤n) 的一条单向道路，长度为ℓ\ellℓ(0≤ℓ≤10 0000 \leq \ell \leq 10\, 0000≤ℓ≤10000)。没有有序对(u,v)(u,v)(u,v)会出现多次，并且从任何交叉路口都可以到达每个其他交叉路口。

输出格式

输出信使需要行驶的最小总距离。

输入输出样例 #1

输入 #1

5 4 2 10 5 2 1 2 5 1 3 5 5 4 5 0 1 5 1 2 3 1 3 2 5 2 4 5 2 1 1 3 4 2

输出 #1

13

输入输出样例 #2

输入 #2

5 4 2 10 5 2 1 2 5 1 3 5 5 4 5 10 1 5 1 2 3 1 3 2 5 2 4 5 2 1 1 3 4 2

输出 #2

24

说明/提示

时间限制：2000 毫秒，内存限制：1048576 kB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2016。

题面翻译由 ChatGPT-4o 提供。

思路

动态规划
决策单调性
杂项
wqs二分

代码见下

#include<bits/stdc++.h>usingnamespacestd;longlongn,b,s,r,a[5005],aa[5005],uu,vv,ee,f[5005],df[100005];structone{longlongu,e;};vector<one>v[5005];vector<one>vx[5005];booloperator<(one a1,one b1){returna1.e>b1.e;}priority_queue<one>q;voidabc(longlongl,longlongr,longlongx,longlongy){if(l>=r+1){return;}if(r-l+1<=5||y-x+1<=5){for(inti=l;i<=r;i++){df[i]=1e18+7;for(intj=x;j<=min(i-1ll,y);j++){df[i]=min(df[i],f[j]+(a[i]-a[j])*(i-j-1));}}return;}longlongmid=(l+r)/2,p;df[mid]=1e18+7;for(inti=x;i<=min(mid,y);i++){if(f[i]+(a[mid]-a[i])*(mid-i-1)<=df[mid]-1){df[mid]=f[i]+(a[mid]-a[i])*(mid-i-1);p=i;}}abc(l,mid-1,x,p);abc(mid+1,r,p,y);return;}intmain(){cin>>n>>b>>s>>r;for(inti=1;i<=r;i++){cin>>uu>>vv>>ee;v[uu].push_back({vv,ee});vx[vv].push_back({uu,ee});}memset(a,62,sizeof(a));q.push({b+1,0});a[b+1]=0;while(q.size()!=0){longlonga1=q.top().u;//cout<<a1<<endl;q.pop();for(inti=0;i<v[a1].size();i++){one tt=v[a1][i];if(a[tt.u]>=a[a1]+tt.e+1){a[tt.u]=a[a1]+tt.e;q.push({tt.u,a[tt.u]});}}}memset(aa,62,sizeof(aa));q.push({b+1,0});aa[b+1]=0;while(q.size()!=0){longlonga1=q.top().u;//cout<<a1<<endl;q.pop();for(inti=0;i<vx[a1].size();i++){one tt=vx[a1][i];if(aa[tt.u]>=aa[a1]+tt.e+1){aa[tt.u]=aa[a1]+tt.e;q.push({tt.u,aa[tt.u]});}}}for(inti=1;i<=b;i++){a[i]+=aa[i];}//cout<<f[b][s]<<endl;sort(a+1,a+b+1);a[0]=0;for(inti=1;i<=b;i++){a[i]=a[i-1]+a[i];//cout<<i<<" "<<a[i]<<endl;}memset(f,62,sizeof(f));f[0]=0;for(intj=1;j<=s;j++){abc(1,b,0,b);for(inti=0;i<=b;i++){f[i]=df[i];}}cout<<f[b]<<endl;return0;}