企业官网建设流程全解析

中国的平面设计网站,亚马逊被曝将裁员1万人,建设官网银行,搭建电子商务平台P6918 [ICPC 2016 WF] Branch Assignment 题目描述 创新消费品公司#xff08;ICPC#xff09;计划启动一个绝密项目。该项目由 sss 个子项目组成。将有 b≥sb \ge sb≥s 个 ICPC 的分支机构参与此项目#xff0c;ICPC 希望将每个分支机构分配给一个子项目。换句话说#x…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总部位于交叉路口b1b 1b1。接下来的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输入 #15 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输出 #113输入输出样例 #2输入 #25 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输出 #224说明/提示时间限制2000 毫秒内存限制1048576 kB。国际大学生程序设计竞赛ACM-ICPC世界总决赛 2016。题面翻译由 ChatGPT-4o 提供。思路动态规划决策单调性杂项wqs二分代码见下#includebits/stdc.husingnamespacestd;longlongn,b,s,r,a[5005],aa[5005],uu,vv,ee,f[5005],df[100005];structone{longlongu,e;};vectoronev[5005];vectoronevx[5005];booloperator(one a1,one b1){returna1.eb1.e;}priority_queueoneq;voidabc(longlongl,longlongr,longlongx,longlongy){if(lr1){return;}if(r-l15||y-x15){for(intil;ir;i){df[i]1e187;for(intjx;jmin(i-1ll,y);j){df[i]min(df[i],f[j](a[i]-a[j])*(i-j-1));}}return;}longlongmid(lr)/2,p;df[mid]1e187;for(intix;imin(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);pi;}}abc(l,mid-1,x,p);abc(mid1,r,p,y);return;}intmain(){cinnbsr;for(inti1;ir;i){cinuuvvee;v[uu].push_back({vv,ee});vx[vv].push_back({uu,ee});}memset(a,62,sizeof(a));q.push({b1,0});a[b1]0;while(q.size()!0){longlonga1q.top().u;//couta1endl;q.pop();for(inti0;iv[a1].size();i){one ttv[a1][i];if(a[tt.u]a[a1]tt.e1){a[tt.u]a[a1]tt.e;q.push({tt.u,a[tt.u]});}}}memset(aa,62,sizeof(aa));q.push({b1,0});aa[b1]0;while(q.size()!0){longlonga1q.top().u;//couta1endl;q.pop();for(inti0;ivx[a1].size();i){one ttvx[a1][i];if(aa[tt.u]aa[a1]tt.e1){aa[tt.u]aa[a1]tt.e;q.push({tt.u,aa[tt.u]});}}}for(inti1;ib;i){a[i]aa[i];}//coutf[b][s]endl;sort(a1,ab1);a[0]0;for(inti1;ib;i){a[i]a[i-1]a[i];//couti a[i]endl;}memset(f,62,sizeof(f));f[0]0;for(intj1;js;j){abc(1,b,0,b);for(inti0;ib;i){f[i]df[i];}}coutf[b]endl;return0;}