电脑网站在哪里找,php餐饮网站,今天最新体育新闻,无极县在线招聘信息1834: [ZJOI2010]network 网络扩容 Time Limit: 3 SecMemory Limit: 64 MBDescription 给定一张有向图#xff0c;每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求#xff1a; 1、 在不扩容的情况下#xff0c;1到N的最大流#xff1b; 2、… 1834: [ZJOI2010]network 网络扩容 Time Limit: 3 SecMemory Limit: 64 MB Description 给定一张有向图每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求 1、 在不扩容的情况下1到N的最大流 2、 将1到N的最大流增加K所需的最小扩容费用。 Input 输入文件的第一行包含三个整数N,M,K表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W表示一条从u到v容量为C扩容费用为W的边。 Output 输出文件一行包含两个整数分别表示问题1和问题2的答案。 Sample Input 5 8 2 1 2 5 8 2 5 9 9 5 1 6 2 5 1 1 8 1 2 8 7 2 5 4 9 1 2 1 1 1 4 2 1 Sample Output 13 19 30%的数据中N100 100%的数据中N1000M5000K10 HINT Source Day1 【题解】 网络流啊TAT 每次都是数组开小啊 这道题第一问就是直接dinic最大流 第二问就是在做费用流的时候求出的解是满足最大流情况下的解。设第一问的最大流是ANS,要扩容K有可能在加了新边后最大流大于ANSK。这样费用可能不是最小的。因此我们可以在1号或N号点新增一条边容量是K费用是0。这样就限制了最大流。 1 #include stdio.h2 #include queue3 #include string.h4 using namespace std;5 const int B30010;6 const int INF2139062143;7 int next[B], head[B], to[B], flow[B], w[B], c[B], oq[B];8 int pre[B], cnt-1, bi[B], n, m, k, ans0, d[B];9 bool vis[B];10 int u[B], v[B], _f[B], _w[B];11 queue int q;12 inline void add(int u,int v,int flo,int _w) {13 cnt; to[cnt]v; next[cnt]head[u]; head[u]cnt; flow[cnt]flo; w[cnt]_w;14 }15 inline int min(int a,int b) {return ab?a:b;}16 inline void G(int x) {17 int y0, yy1; char chgetchar();18 while(ch0||ch9) {19 if(ch-) yy-1;20 chgetchar();21 }22 while(ch0ch9) {23 y(y1)(y3)ch-0;24 chgetchar();25 }26 xy*yy;27 }28 inline void qclear() {29 while(!q.empty()) q.pop();30 }31 inline bool getdfn() {32 qclear();33 memset(c,-1,sizeof(c));34 q.push(1); c[1]1;35 while(!q.empty()) {36 int topq.front();37 q.pop();38 for (int ihead[top];i0;inext[i]) {39 int tto[i];40 if(c[t]0||flow[i]0) continue;41 c[t]c[top]1;42 q.push(t);43 if(tn) return 1;44 } 45 }46 return 0;47 }48 int dinic(int x,int low) {49 if(xn) return low;50 int flo,rlow;51 for (int ihead[x];i0;inext[i]) {52 int tto[i], flflow[i];53 if(c[t]!c[x]1 || fl0) continue;54 flodinic(t,min(r,fl));55 r-flo;56 flow[i]-flo;57 flow[i^1]flo;58 if(!r) return low;59 }60 if(rlow) c[x]-1;61 return low-r;62 }63 inline bool spfa() {64 memset(vis,0,sizeof(vis));65 memset(oq,0,sizeof(oq));66 memset(d,0X7f,sizeof(d));67 qclear();68 vis[1]1; d[1]0; q.push(1);69 while(!q.empty()) {70 int topq.front(); q.pop();71 vis[top]0; oq[top];72 if(oq[top]n) return 0;73 for (int ihead[top];i0;inext[i]) {74 if(flow[i]d[top]w[i]d[to[i]]) {75 d[to[i]]d[top]w[i];76 pre[to[i]]i;77 if(!vis[to[i]]) {78 vis[to[i]]1;79 q.push(to[i]);80 }81 }82 }83 }84 if(d[n]INF) return 0;85 return 1;86 }87 inline void mincostflow() {88 int sINF;89 for (int ipre[n];i0;ipre[to[i^1]]) {90 smin(s,flow[i]);91 if(to[i^1]1) break;92 }93 for (int ipre[n];i0;ipre[to[i^1]]) {94 flow[i]-s;95 flow[i^1]s;96 anss*w[i];97 if(to[i^1]1) break;98 }99 }
100 int main() {
101 G(n), G(m), G(k);
102 memset(head,-1,sizeof(head));
103 for (int i1;im;i) {
104 G(u[i]), G(v[i]), G(_f[i]), G(_w[i]);
105 add(u[i],v[i],_f[i],0);
106 add(v[i],u[i],0,0);
107 }
108 int _flowx0;
109 while(getdfn()) _flowx dinic(1,INF);
110 printf(%d ,_flowx);
111 for (int i1;im;i) {
112 add(u[i],v[i],INF,_w[i]);
113 add(v[i],u[i],0,-_w[i]);
114 }
115 add(n,n1,k,0); add(n1,n,0,0);
116 n;
117 while(spfa()) mincostflow();
118 printf(%d\n,ans);
119 return 0;
120 } View Code 转载于:https://www.cnblogs.com/TonyNeal/p/bzoj1834.html
