[关闭]
@ivorysi 2018-03-29T13:22:25.000000Z 字数 24755 阅读 793

有上下界的网络流笔记

笔记

无源汇的可行流

ZOJ 2314 Reactor Cooling

The terrorist group leaded by a well known international terrorist Ben Bladen is buliding a nuclear reactor to produce plutonium for the nuclear bomb they are planning to create. Being the wicked computer genius of this group, you are responsible for developing the cooling system for the reactor.
The cooling system of the reactor consists of the number of pipes that special cooling liquid flows by. Pipes are connected at special points, called nodes, each pipe has the starting node and the end point. The liquid must flow by the pipe from its start point to its end point and not in the opposite direction.
Let the nodes be numbered from 1 to N. The cooling system must be designed so that the liquid is circulating by the pipes and the amount of the liquid coming to each node (in the unit of time) is equal to the amount of liquid leaving the node. That is, if we designate the amount of liquid going by the pipe from i-th node to j-th as fij, (put fij = 0 if there is no pipe from node i to node j), for each i the following condition must hold:
fi,1+fi,2+...+fi,N = f1,i+f2,i+...+fN,i
Each pipe has some finite capacity, therefore for each i and j connected by the pipe must be fij <= cij where cij is the capacity of the pipe. To provide sufficient cooling, the amount of the liquid flowing by the pipe going from i-th to j-th nodes must be at least lij, thus it must be fij >= lij.
Given cij and lij for all pipes, find the amount fij, satisfying the conditions specified above.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.

Input

The first line of the input file contains the number N (1 <= N <= 200) - the number of nodes and and M - the number of pipes. The following M lines contain four integer number each - i, j, lij and cij each. There is at most one pipe connecting any two nodes and 0 <= lij <= cij <= 10^5 for all pipes. No pipe connects a node to itself. If there is a pipe from i-th node to j-th, there is no pipe from j-th node to i-th.

Output

On the first line of the output file print YES if there is the way to carry out reactor cooling and NO if there is none. In the first case M integers must follow, k-th number being the amount of liquid flowing by the k-th pipe. Pipes are numbered as they are given in the input file.

Sample Input

2
4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2

4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3

Sample Input

NO

YES
1
2
3
2
1
1

题解

这里的水是循环流动的
我们考虑网络流，需要满足一个流量平衡条件，就像题里说的
对于任意一点i，设每条边经过的流量为，都有

也就是所说的流量平衡条件
然后由于每条边有一个上界，有一个下界，我们还要满足这个条件


我们设是新图边的流量

以为我们能在这个图上跑网络流了吗？so naive，不行
我们并不能满足下界
所以再去看这个流量平衡条件


我们设
新建一个源点和汇点
我们从源点连一条边到，容量为
我们从连一条边到汇点，容量为
我们再把每条边的容量改成上下界的差值，然后去跑一遍网络流，如果原点出发的任意一条弧，和到达汇点的任意一条弧都满流，那么就在原网络中对应一条可行流
最后检查一下到流量是否与源点出发的弧的容量总和相等即可
如果需要算出每条边的真实流量，就用流量下界，加上该边在新图中的流量即可
纠结了一会为什么源点满流代表到汇点的弧也满流，然后发现……每条边的下界被加一遍也被减一遍，所以当然从源点出发弧的容量总和等于到汇点的弧的容量总和

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define MAXN 205
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. struct node {
  14.     int to,next,val;
  15. }edge[100005];
  16. int head[MAXN],sumedge;
  17. int n,m,T;
  18. int d[MAXN],dis[MAXN],gap[MAXN],low[100005],source,sink,tot;
  19. void add(int u,int v,int c) {
  20.     edge[++sumedge].to=v;
  21.     edge[sumedge].next=head[u];
  22.     edge[sumedge].val=c;
  23.     head[u]=sumedge;
  24. }
  25. void addtwo(int u,int v,int c) {
  26.     add(u,v,c);add(v,u,0);
  27. }
  28. int sap(int u,int aug) {
  29.     if(u==sink) return aug;
  30.     int dmin=sink-1,flow=0;
  31.     for(int i=head[u];i;i=edge[i].next) {
  32.         if(edge[i].val>0) {
  33.             int v=edge[i].to;
  34.             if(dis[v]+1==dis[u]) {
  35.                 int t=sap(v,min(aug-flow,edge[i].val));
  36.                 flow+=t;
  37.                 edge[i].val-=t;
  38.                 edge[i^1].val+=t;
  39.                 if(dis[source]>=sink) return flow;
  40.                 if(flow==aug) return flow;
  41.             }
  42.             dmin=min(dmin,dis[v]);
  43.         }
  44.     }
  45.     if(!flow) {
  46.         --gap[dis[u]];
  47.         if(gap[dis[u]]==0) dis[source]=sink;
  48.         dis[u]=dmin+1;
  49.         ++gap[dis[u]];
  50.     }
  51.     return flow;
  52. }
  53. void solve() {
  54.     memset(dis,0,sizeof(dis));
  55.     memset(gap,0,sizeof(gap));
  56.     memset(d,0,sizeof(d));
  57.     memset(head,0,sizeof(head));sumedge=1;
  59.     scanf("%d%d",&n,&m);
  60.     int u,v,c;
  61.     siji(i,1,m) {
  62.         scanf("%d%d%d%d",&u,&v,&low[i],&c);
  63.         addtwo(u,v,c-low[i]);
  64.         d[v]+=low[i];
  65.         d[u]-=low[i];
  66.     }
  67.     source=n+1,sink=n+2;
  68.     tot=0;
  69.     siji(i,1,n) {
  70.         if(d[i]>0) addtwo(source,i,d[i]),tot+=d[i];
  71.         else if(d[i]<0) addtwo(i,sink,-d[i]);
  72.     }
  73.     while(dis[source]<sink && tot) tot-=sap(source,tot);
  74.     if(tot!=0) {
  75.         puts("NO");
  76.     }
  77.     else {
  78.         puts("YES");
  79.         siji(i,1,m) {
  80.             printf("%d\n",low[i]+edge[2*i+1].val);
  81.         }
  82.     }
  83. }
  84. int main() {
  85. #ifdef ivorysi
  86.     freopen("f1.in","r",stdin);
  87. #endif
  88.     scanf("%d",&T);
  89.     int cnt=0;
  90.     while(T--) {
  91.         ++cnt;
  92.         if(cnt!=1) puts("");
  93.         solve();
  94.     }
  95.     return 0;
  96. }

ZOJ 1994 /POJ 2396 Budget

We are supposed to make a budget proposal for this multi-site competition. The budget proposal is a matrix where the rows represent different kinds of expenses and the columns represent different sites. We had a meeting about this, some time ago where we discussed the sums over different kinds of expenses and sums over different sites. There was also some talk about special constraints: someone mentioned that Computer Center would need at least 2000K Rials for food and someone from Sharif Authorities argued they wouldn't use more than 30000K Rials for T-shirts. Anyway, we are sure there was more; we will go and try to find some notes from that meeting.
And, by the way, no one really reads budget proposals anyway, so we'll just have to make sure that it sums up properly and meets all constraints.

Input

The first line of the input contains an integer N, giving the number of test cases. The next line is empty, then, test cases follow: The first line of each test case contains two integers, m and n, giving the number of rows and columns (m <= 200, n <= 20). The second line contains m integers, giving the row sums of the matrix. The third line contains n integers, giving the column sums of the matrix. The fourth line contains an integer c giving the number of constraints. The next c lines contain the constraints. There is an empty line after each test case.
Each constraint consists of two integers r and q, specifying some entry (or entries) in the matrix (the upper left corner is 1 1 and 0 is interpreted as "ALL", i.e. 4 0 means all entries on the fourth row and 0 0 means the entire matrix), one element from the set {<, =, >} and one integer v, with the obvious interpretation. For instance, the constraint 1 2 > 5 means that the cell in the 1st row and 2nd column must have an entry strictly greater than 5, and the constraint 4 0 = 3 means that all elements in the fourth row should be equal to 3.

Output

For each case output a matrix of non-negative integers meeting the above constraints or the string "IMPOSSIBLE" if no legal solution exists. Put one empty line between matrices.

Sample Input

2

2 3
8 10
5 6 7
4
0 2 > 2
2 1 = 3
2 3 > 2
2 3 < 5

2 2
4 5
6 7
1
1 1 > 10

Sample Output

2 3 3
3 3 4

IMPOSSIBLE

题解

这道题思路比较明显当然是行列拆点，由于规定了行的和与列的和那么容易想到建一个源点连向每一行，每一列连向汇点，容量分别为各自的和，汇点再连到源点，由于源点和汇点都是流量平衡的，所以可以不用考虑他们，计算就考虑行列拆出的点即可
然后就是存图！！！只要我们能把行列的上下界记下来就万事大吉了……
注意我们要去众多上界中最小的上界，众多下界中最大的下界，如果是=号打个标记，下次修改的时候记录一下值的可取区间，如果这个之前固定好的容量不在这个可取区间里，那就不合法，注意如果在读判断条件的时候找到不合法了，把后面的东西读完再跳出

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. struct node {
  13.     int to,next,val;
  14. }edge[2000005];
  15. int sumedge,head[405];
  16. void add(int u,int v,int c) {
  17.     edge[++sumedge].to=v;
  18.     edge[sumedge].next=head[u];
  19.     edge[sumedge].val=c;
  20.     head[u]=sumedge;
  21. }
  22. void addtwo(int u,int v,int c) {
  23.     add(u,v,c);add(v,u,0);
  24. }
  25. int low[205][205],upp[205][205],r,c,op,d[405],tot,source,sink;
  26. bool disable[205][205];
  27. int dis[405],gap[405];
  28. int sap(int u,int aug) {
  29.     if(u==sink) return aug;
  30.     int dmin=sink-1,flow=0;
  31.     for(int i=head[u];i;i=edge[i].next) {
  32.         if(edge[i].val>0) {
  33.             int v=edge[i].to;
  34.             if(dis[v]+1==dis[u]) {
  35.                 int t=sap(v,min(edge[i].val,aug-flow));
  36.                 flow+=t;
  37.                 edge[i].val-=t;
  38.                 edge[i^1].val+=t;
  39.                 if(flow==aug) return flow;
  40.                 if(dis[source]>=sink) return flow;
  41.             }
  42.             dmin=min(dmin,dis[v]);
  43.         }
  44.     }
  45.     if(!flow) {
  46.         --gap[dis[u]];
  47.         if(gap[dis[u]]==0) dis[source]=sink;
  48.         dis[u]=dmin+1;
  49.         ++gap[dis[u]];
  50.     }
  51.     return flow;
  52. }
  53. void solve() {
  54.     memset(head,0,sizeof(head));sumedge=1;
  55.     memset(low,0,sizeof(low));
  56.     memset(dis,0,sizeof(dis));
  57.     memset(gap,0,sizeof(gap));
  58.     memset(d,0,sizeof(d));
  59.     memset(disable,0,sizeof(disable));
  60.     scanf("%d%d",&r,&c);
  61.     int x,y,v;
  62.     char s[10];
  63.     tot=0;
  64.     siji(i,1,r) {
  65.         scanf("%d",&x);
  66.         tot+=x;
  67.         d[i]+=x;
  68.     }
  69.     siji(i,1,c) {
  70.         scanf("%d",&x);
  71.         tot-=x;
  72.         d[i+r]-=x;
  73.     }
  74.     siji(i,1,r) {
  75.         siji(j,1,c) {
  76.             upp[i][j]=0x7fffffff;
  77.         }
  78.     }
  79.     scanf("%d",&op);
  80.     int a,b;
  81.     siji(i,1,op) {
  82.         scanf("%d%d%s%d",&x,&y,s,&v);
  83.         if(s[0]=='<') {v--;b=v;a=0;}
  84.         else if(s[0]=='>') {++v;a=v;b=0x7fffffff;}
  85.         else a=b=v;
  86.         if(x==0 &&y==0) {
  87.             siji(j,1,r) {
  88.                 siji(k,1,c) {
  89.                     if(disable[j][k] && (!(low[j][k]<=b && low[j][k]>=a))) {
  90.                         siji(h,i+1,op) scanf("%d%d%s%d",&x,&y,s,&v);
  91.                         puts("IMPOSSIBLE");
  92.                         return;
  93.                     }
  94.                     if(s[0]=='=') {upp[j][k]=low[j][k]=v;disable[j][k]=1;}
  95.                     else if(s[0]=='>') {low[j][k]=max(low[j][k],v);}
  96.                     else {upp[j][k]=min(upp[j][k],v);}
  97.                 }
  98.             }
  99.         }
  100.         else if(x==0) {
  101.             siji(j,1,r) {
  102.                 if(disable[j][y] && (!(low[j][y]<=b && low[j][y]>=a))) {
  103.                     siji(h,i+1,op) scanf("%d%d%s%d",&x,&y,s,&v);
  104.                     puts("IMPOSSIBLE");
  105.                     return;
  106.                 }
  107.                 if(s[0]=='=') {upp[j][y]=low[j][y]=v;disable[j][y]=1;}
  108.                 else if(s[0]=='>') {low[j][y]=max(low[j][y],v);}
  109.                 else {upp[j][y]=min(upp[j][y],v);}
  110.             }
  111.         }
  112.         else if(y==0) {
  113.             siji(k,1,c) {
  114.                 if(disable[x][k] && (!(low[x][k]<=b && low[x][k]>=a))) {
  115.                     siji(h,i+1,op) scanf("%d%d%s%d",&x,&y,s,&v);
  116.                     puts("IMPOSSIBLE");
  117.                     return;
  118.                 }
  119.                 if(s[0]=='=') {upp[x][k]=low[x][k]=v;disable[x][k]=1;}
  120.                 else if(s[0]=='>') {low[x][k]=max(low[x][k],v);}
  121.                 else {upp[x][k]=min(upp[x][k],v);}
  122.             }
  123.         }
  124.         else {
  125.             if(disable[x][y] && (!(low[x][y]<=b && low[x][y]>=a))) {
  126.                 siji(h,i+1,op) scanf("%d%d%s%d",&x,&y,s,&v);
  127.                 puts("IMPOSSIBLE");
  128.                 return;
  129.             }
  130.             if(s[0]=='=') {upp[x][y]=low[x][y]=v;disable[x][y]=1;}
  131.             else if(s[0]=='>') {low[x][y]=max(low[x][y],v);}
  132.             else {upp[x][y]=min(upp[x][y],v);}
  133.         }
  134.     }
  135.     if(tot!=0) {puts("IMPOSSIBLE");return;}
  136.     siji(i,1,r) {
  137.         siji(j,1,c) {
  138.             d[i]-=low[i][j];
  139.             d[j+r]+=low[i][j];
  140.             if(low[i][j]>upp[i][j]) {puts("IMPOSSIBLE");return;}
  141.             addtwo(i,j+r,upp[i][j]-low[i][j]);
  142.         }
  143.     }
  144.     source=r+c+1,sink=r+c+2;
  145.     tot=0;
  146.     siji(i,1,r+c) {
  147.         if(d[i]>0) addtwo(source,i,d[i]),tot+=d[i];
  148.         else if(d[i]<0) addtwo(i,sink,-d[i]);
  149.     }
  150.     while(dis[source]<sink) tot-=sap(source,tot);
  151.     if(tot) {puts("IMPOSSIBLE");return;}
  152.     siji(i,1,r) {
  153.         siji(j,1,c) {
  154.             int id=((i-1)*c+j)*2+1;
  155.             printf("%d%c",low[i][j]+edge[id].val," \n"[j==c]);
  156.         }
  157.     }
  158. }
  159. int main() {
  160. #ifdef ivorysi
  161.     freopen("f1.in","r",stdin);
  162. #endif
  163.     int T,cnt=0;
  164.     scanf("%d",&T);
  165.     while(T--) {
  166.         ++cnt;
  167.         if(cnt!=1) puts("");
  168.         solve();
  169.     }
  170.     return 0;
  171. }

有源汇的有上下界的最大流

这道题需要先从终点到起点连一条容量下界为0上界是inf的边，然后做一遍有无源汇的可行流
然后从s到t在残余网络做一遍最大流，开始时如果终点到起点有流的话，这条流还会被退回去

ZOJ 3229

SPJ挂了，垃圾题，可我代码都写完了

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define MAXN 40005
  10. //#define ivorysi
  11. using namespace std;
  12. typedef long long ll;
  13. struct node {
  14.     int to,next,val;
  15. }edge[400005];
  16. int head[MAXN],sumedge,n,m,source,sink,S,T,maxnum;
  17. int dis[MAXN],gap[MAXN],d[MAXN],pos[MAXN],ans[MAXN],cnt;
  18. void add(int u,int v,int c) {
  19.     edge[++sumedge].to=v;
  20.     edge[sumedge].next=head[u];
  21.     edge[sumedge].val=c;
  22.     head[u]=sumedge;
  23. }
  24. void addtwo(int u,int v,int c) {
  25.     add(u,v,c);add(v,u,0);
  26. }
  27. int sap(int u,int aug,int &Si,int &Ti) {
  28.     if(u==Ti) return aug;
  29.     int dmin=maxnum-1,flow=0;
  30.     for(int i=head[u];i;i=edge[i].next) {
  31.     if(edge[i].val>0) {
  32.         int v=edge[i].to;
  33.         if(dis[v]+1==dis[u]) {
  34.         int t=sap(v,min(aug-flow,edge[i].val),Si,Ti);
  35.         flow+=t;
  36.         edge[i].val-=t;
  37.         edge[i^1].val+=t;
  38.         if(flow==aug) return flow;
  39.         if(dis[Si]>=maxnum) return flow;
  40.         }
  41.         dmin=min(dmin,dis[v]);
  42.     }
  43.     }
  44.     if(!flow) {
  45.     gap[dis[u]]--;
  46.     if(gap[dis[u]]==0) dis[Si]=maxnum;
  47.     dis[u]=dmin+1;
  48.     gap[dis[u]]++;
  49.     }
  50.     return flow;
  51. }
  52. void solve() {
  53.     memset(head,0,sizeof(head));sumedge=1;
  54.     memset(d,0,sizeof(d));
  55.     memset(ans,0,sizeof(ans));
  56.     memset(pos,0,sizeof(pos));
  57.     cnt=0;
  58.     source=1,sink=n+m+2;
  59.     int x;
  60.     siji(i,1,m) {
  61.     scanf("%d",&x);
  62.     addtwo(n+1+i,sink,0x7fffffff);
  63.     d[sink]+=x;
  64.     d[n+1+i]-=x;
  65.     }
  66.     int C,D,t,l,r;
  67.     siji(i,1,n) {
  68.     scanf("%d%d",&C,&D);
  69.     addtwo(source,i+1,D);
  70.     siji(j,1,C) {
  71.         scanf("%d%d%d",&t,&l,&r);++t;
  72.         ++cnt;
  73.         addtwo(i+1,t+n+1,r-l);
  74.         pos[cnt]=sumedge;
  75.         ans[cnt]=l;
  76.         d[i+1]-=l;
  77.         d[t+n+1]+=l;
  78.     }
  79.     }
  80.     addtwo(sink,source,0x7fffffff);
  81.     S=sink+1,T=sink+2;
  82.     int tot=0;
  83.     siji(i,1,n+m+2) {
  84.     if(d[i]>0) {addtwo(S,i,d[i]);tot+=d[i];}
  85.     else if(d[i]<0) addtwo(i,T,-d[i]);
  86.     }
  87.     memset(dis,0,sizeof(dis));
  88.     memset(gap,0,sizeof(gap));
  89.     maxnum=n+m+4;
  90.     while(dis[S]<maxnum) tot-=sap(S,tot,S,T);
  91.     if(tot) {puts("-1");return;}
  92.     memset(dis,0,sizeof(dis));
  93.     memset(gap,0,sizeof(gap));
  94.     while(dis[source]<maxnum) tot+=sap(source,0x7fffffff,source,sink);
  95.     printf("%d\n",tot);
  96.     siji(i,1,cnt) {
  97.     ans[i]+=edge[pos[i]].val;
  98.     printf("%d\n",ans[i]);
  99.     }
  100.    }
  101. int main() {
  102. #ifdef ivorysi
  103.     freopen("f1.in","r",stdin);
  104. #endif
  105.     while(scanf("%d",&n)!=EOF) {
  106.     scanf("%d",&m);
  107.     solve();
  108.     puts("");
  109.     }
  110.     return 0;
  111. }

ZOJ 3496 Assignment

Time Limit: 2 Seconds Memory Limit: 65536 KB
Company A wants to transport as many goods as possible from city S to city T. So they ask company B to do the transportation. There are n cities here in the problem and there are directed roads from cities i to city j with capacity cij.
After a long negotiation, A and B reach a consensus that A first decide how to transport the goods (Of course under the condition that most goods are transported and that the quantity transported in each road cannot exceed the capacity) and then B can assign non-negative integer unit transportation costs to each road such that the total unit transportation costs in all roads sum to P. So the money A has to pay is the sum of costs of all roads while the cost of a certain road is the quantity transported (assigned by A) multiplied by the unit transportation cost (assigned by B). Notice that since the goods are not divisible, the quantity transported for each road should be a non-negative integer.
Of course A wants to minimize the cost and B want to maximize the cost. So you are to work out what the total cost will be?
To make the problem more fun, you should also work out the total cost that A wants to maximize the cost while B wants to minimize it and other conditions keep the same.

Input

There are multiple test cases. The first line of the input is an integer T ≈ 100 indicating the number of test cases.
For each test case, the first line contains 5 integers n, m, S, T, P (2 ≤ n ≤ 500, 0 ≤ m ≤ 10000, 0 ≤ S, T < n, 0 ≤ P ≤ 100000). The next m lines describe the roads between cities. In each of the m lines, 3 integers u, v, c (0 ≤ u, v, 1 ≤ c ≤ 100000) are given indicating a road from u to v with capacity c.

Output

For each test case, output one line with two integers. The first is the total cost that A wants to minimize and B wants to maximize, the second is the total cost that A wants to maximize and B wants to minimize.

Sample Input

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

Sample Output

1 0

Hint

A can assign the transported quantity in roads to (1, 0, 1, 0, 1) or (0, 1, 0, 1, 1) in the order as the input. Both of the assignment can transport 1 unit of goods.
So in the first situation, B can assign 1 unit cost to a road that transport 1 unit of goods and 0 to other roads. The total cost is 1. In the second situation, B can assign 1 unit cost to a road that transport 0 units of goods and 0 to other roads. The total cost is 0.

题解

这道题一看就是二分……然而题面有点绕，导致我没有仔细读题
"Of course under the condition that most goods are transported and that the quantity transported in each road cannot exceed the capacity"告诉我们要求货物的运输量不管怎么样都要最大
“then B can assign non-negative integer unit transportation costs to each road such that the total unit transportation costs in all roads sum to P”
A公司设定运输计划
B公司会在一些道路上增加单位花费，共计加上P
然后A公司去运输，交给B公司钱
求两个东西，一个是A公司希望花费最小B公司希望花费最大
一个是B公司希望花费最小A公司希望花费最大
实际上B公司只需要把A公司流量最大的那条边设成P就好，这样A公司花费最大，A公司需要让最大值最小
第二个B公司把A公司流量最小的那条边设成P，A公司花费最小，A公司需要让最小值最大

先求出最大流
二分答案
然后对于一个问题二分上界，直接做网络流
对第二个问题二分下界，做有上下界的网络流，求最大流，和一开始求出的最大流比较是否相等

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. struct node {
  13.     int to,next,val;
  14. }edge[400005];
  15. int head[505],sumedge,d[505],dis[505],gap[505],maxnum;
  16. struct data {
  17.     int u,v,c;
  18. }Eg[100005];
  19. int n,m,S,T,P,source,sink,Maxflow;
  20. void add(int u,int v,int c) {
  21.     edge[++sumedge].to=v;
  22.     edge[sumedge].next=head[u];
  23.     edge[sumedge].val=c;
  24.     head[u]=sumedge;
  25. }
  26. void addtwo(int u,int v,int c) {
  27.     add(u,v,c);add(v,u,0);
  28. }
  29. int sap(int u,int aug,int &Si,int &Ti) {
  30.     if(u==Ti) return aug;
  31.     int dmin=maxnum-1,flow=0;
  32.     for(int i=head[u];i;i=edge[i].next) {
  33.         if(edge[i].val>0) {
  34.             int v=edge[i].to;
  35.             if(dis[v]+1==dis[u]) {
  36.                 int t=sap(v,min(aug-flow,edge[i].val),Si,Ti);
  37.                 flow+=t;
  38.                 edge[i].val-=t;
  39.                 edge[i^1].val+=t;
  40.                 if(flow==aug) return flow;
  41.                 if(dis[Si]>=maxnum) return flow;
  42.             }
  43.             dmin=min(dmin,dis[v]);
  44.         }
  45.     }
  46.     if(!flow) {
  47.         --gap[dis[u]];
  48.         if(gap[dis[u]]==0) dis[Si]=maxnum;
  49.         dis[u]=dmin+1;
  50.         ++gap[dis[u]];
  51.     }
  52.     return flow;
  53. }
  54. void getmaxflow() {
  55.     memset(head,0,sizeof(head));sumedge=1;
  56.     memset(gap,0,sizeof(gap));
  57.     memset(dis,0,sizeof(dis));
  58.     siji(i,1,m) {
  59.         addtwo(Eg[i].u,Eg[i].v,Eg[i].c);
  60.     }
  61.     Maxflow=0;
  62.     while(dis[S]<maxnum) Maxflow+=sap(S,0x7fffffff,S,T);
  63. }
  64. bool check1(int up) {
  65.     memset(head,0,sizeof(head));sumedge=1;
  66.     memset(dis,0,sizeof(dis));
  67.     memset(gap,0,sizeof(gap));
  68.     siji(i,1,m) {
  69.         addtwo(Eg[i].u,Eg[i].v,min(up,Eg[i].c));
  70.     }
  71.     int tot=0;
  72.     while(dis[S]<maxnum) tot+=sap(S,0x7fffffff,S,T);
  73.     return tot==Maxflow;
  74. }
  75. bool check2(int low) {
  76.     memset(head,0,sizeof(head));sumedge=1;
  77.     memset(d,0,sizeof(d));
  78.     siji(i,1,m) {
  79.         if(Eg[i].c<low) return false;
  80.         d[Eg[i].u]-=low;
  81.         d[Eg[i].v]+=low;
  82.         addtwo(Eg[i].u,Eg[i].v,Eg[i].c-low);
  83.     }
  84.     addtwo(T,S,0x7fffffff);
  85.     int tot=0;
  86.     siji(i,1,n) {
  87.         if(d[i]>0) addtwo(source,i,d[i]),tot+=d[i];
  88.         else if(d[i]<0) addtwo(i,sink,-d[i]);
  89.     }
  91.     memset(dis,0,sizeof(dis));
  92.     memset(gap,0,sizeof(gap));
  93.     while(dis[source]<maxnum) tot-=sap(source,tot,source,sink);
  94.     if(tot) return false;
  95.     memset(dis,0,sizeof(dis));
  96.     memset(gap,0,sizeof(gap));
  97.     while(dis[S]<maxnum) tot+=sap(S,0x7fffffff,S,T);
  98.     return tot==Maxflow;
  99. }
  100. void solve() {
  101.     scanf("%d%d%d%d%d",&n,&m,&S,&T,&P);
  103.     source=n+1,sink=n+2;
  104.     maxnum=n+2;
  105.     ++S;++T;
  106.     int rmax=0;
  107.     siji(i,1,m) {
  108.         scanf("%d%d%d",&Eg[i].u,&Eg[i].v,&Eg[i].c);
  109.         ++Eg[i].u;++Eg[i].v;
  110.         rmax=max(rmax,Eg[i].c);
  111.     }
  112.     if(m==0) {
  113.         puts("0 0");return;
  114.     }
  115.     getmaxflow();
  116.     if(Maxflow == 0) {
  117.     puts("0 0");return;
  118.     }
  119.     int l=0,r=rmax;
  120.     while(l<r) {
  121.         int mid=(l+r)>>1;
  122.         if(check1(mid)) r=mid;
  123.         else l=mid+1;
  124.     }
  125.     printf("%lld ",1LL*r*P);
  126.     l=0,r=rmax;
  127.     while(l<r) {
  128.         int mid=(l+r+1)>>1;
  129.         if(check2(mid)) l=mid;
  130.         else r=mid-1;
  131.     }
  132.     printf("%lld\n",1LL*l*P);
  133. }
  134. int main() {
  135. #ifdef ivorysi
  136.     freopen("f1.in","r",stdin);
  137. #endif
  138.     int T,cnt=0;
  139.     scanf("%d",&T);
  140.     while(T--) {
  141.         solve();
  142.     }
  143.     return 0;
  144. }

这道题还可以看成无源汇的可行流来做，从汇点到源点流一条下界为最大流流量的边，然后判断是否合法

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. struct node {
  13.     int to,next,val;
  14. }edge[400005];
  15. int head[505],sumedge,d[505],dis[505],gap[505],maxnum;
  16. struct data {
  17.     int u,v,c;
  18. }Eg[100005];
  19. int n,m,S,T,P,source,sink,Maxflow;
  20. void add(int u,int v,int c) {
  21.     edge[++sumedge].to=v;
  22.     edge[sumedge].next=head[u];
  23.     edge[sumedge].val=c;
  24.     head[u]=sumedge;
  25. }
  26. void addtwo(int u,int v,int c) {
  27.     add(u,v,c);add(v,u,0);
  28. }
  29. int sap(int u,int aug,int &Si,int &Ti) {
  30.     if(u==Ti) return aug;
  31.     int dmin=maxnum-1,flow=0;
  32.     for(int i=head[u];i;i=edge[i].next) {
  33.         if(edge[i].val>0) {
  34.             int v=edge[i].to;
  35.             if(dis[v]+1==dis[u]) {
  36.                 int t=sap(v,min(aug-flow,edge[i].val),Si,Ti);
  37.                 flow+=t;
  38.                 edge[i].val-=t;
  39.                 edge[i^1].val+=t;
  40.                 if(flow==aug) return flow;
  41.                 if(dis[Si]>=maxnum) return flow;
  42.             }
  43.             dmin=min(dmin,dis[v]);
  44.         }
  45.     }
  46.     if(!flow) {
  47.         --gap[dis[u]];
  48.         if(gap[dis[u]]==0) dis[Si]=maxnum;
  49.         dis[u]=dmin+1;
  50.         ++gap[dis[u]];
  51.     }
  52.     return flow;
  53. }
  54. void getmaxflow() {
  55.     memset(head,0,sizeof(head));sumedge=1;
  56.     memset(gap,0,sizeof(gap));
  57.     memset(dis,0,sizeof(dis));
  58.     siji(i,1,m) {
  59.         addtwo(Eg[i].u,Eg[i].v,Eg[i].c);
  60.     }
  61.     Maxflow=0;
  62.     while(dis[S]<maxnum) Maxflow+=sap(S,0x7fffffff,S,T);
  63. }
  64. bool check1(int up) {
  65.     memset(head,0,sizeof(head));sumedge=1;
  66.     memset(dis,0,sizeof(dis));
  67.     memset(gap,0,sizeof(gap));
  68.     siji(i,1,m) {
  69.         addtwo(Eg[i].u,Eg[i].v,min(up,Eg[i].c));
  70.     }
  71.     addtwo(source,S,Maxflow);
  72.     addtwo(T,sink,Maxflow);
  73.     int tot=Maxflow;
  74.     while(dis[source]<maxnum) tot-=sap(source,tot,source,sink);
  75.     return !tot;
  76. }
  77. bool check2(int low) {
  78.     memset(head,0,sizeof(head));sumedge=1;
  79.     memset(d,0,sizeof(d));
  80.     siji(i,1,m) {
  81.         if(Eg[i].c<low) return false;
  82.         d[Eg[i].u]-=low;
  83.         d[Eg[i].v]+=low;
  84.         addtwo(Eg[i].u,Eg[i].v,Eg[i].c-low);
  85.     }
  86.     d[S]+=Maxflow;
  87.     d[T]-=Maxflow;
  88.     int tot=0;
  89.     siji(i,1,n) {
  90.         if(d[i]>0) addtwo(source,i,d[i]),tot+=d[i];
  91.         else if(d[i]<0) addtwo(i,sink,-d[i]);
  92.     }
  94.     memset(dis,0,sizeof(dis));
  95.     memset(gap,0,sizeof(gap));
  96.     while(dis[source]<maxnum) tot-=sap(source,tot,source,sink);
  97.     return !tot;
  98. }
  99. void solve() {
  100.     scanf("%d%d%d%d%d",&n,&m,&S,&T,&P);
  102.     source=n+1,sink=n+2;
  103.     maxnum=n+2;
  104.     ++S;++T;
  105.     int rmax=0;
  106.     siji(i,1,m) {
  107.         scanf("%d%d%d",&Eg[i].u,&Eg[i].v,&Eg[i].c);
  108.         ++Eg[i].u;++Eg[i].v;
  109.         rmax=max(rmax,Eg[i].c);
  110.     }
  111.     if(m==0) {
  112.         puts("0 0");return;
  113.     }
  114.     getmaxflow();
  115.     if(Maxflow == 0) {
  116.     puts("0 0");return;
  117.     }
  118.     int l=0,r=rmax;
  119.     while(l<r) {
  120.         int mid=(l+r)>>1;
  121.         if(check1(mid)) r=mid;
  122.         else l=mid+1;
  123.     }
  124.     printf("%lld ",1LL*r*P);
  125.     l=0,r=rmax;
  126.     while(l<r) {
  127.         int mid=(l+r+1)>>1;
  128.         if(check2(mid)) l=mid;
  129.         else r=mid-1;
  130.     }
  131.     printf("%lld\n",1LL*l*P);
  132. }
  133. int main() {
  134. #ifdef ivorysi
  135.     freopen("f1.in","r",stdin);
  136. #endif
  137.     int T,cnt=0;
  138.     scanf("%d",&T);
  139.     while(T--) {
  140.         solve();
  141.     }
  142.     return 0;
  143. }

HDU 3157 / POJ 3801 Crazy Circuits

Problem Description

You’ve just built a circuit board for your new robot, and now you need to power it. Your robot circuit consists of a number of electrical components that each require a certain amount of current to operate. Every component has a + and a - lead, which are connected on the circuit board at junctions. Current flows through the component from + to - (but note that a component does not "use up" the current: everything that comes in through the + end goes out the - end).
The junctions on the board are labeled 1, ..., N, except for two special junctions labeled + and - where the power supply terminals are connected. The + terminal only connects + leads, and the - terminal only connects - leads. All current that enters a junction from the - leads of connected components exits through connected + leads, but you are able to control how much current flows to each connected + lead at every junction (though methods for doing so are beyond the scope of this problem1). Moreover, you know you have assembled the circuit in such a way that there are no feedback loops (components chained in a manner that allows current to flow in a loop).
Figure 1: Examples of two valid circuit diagrams.
In (a), all components can be powered along directed paths from the positive terminal to the negative terminal.
In (b), components 4 and 6 cannot be powered, since there is no directed path from junction 4 to the negative terminal.
In the interest of saving power, and also to ensure that your circuit does not overheat, you would like to use as little current as possible to get your robot to work. What is the smallest amount of current that you need to put through the + terminal (which you can imagine all necessarily leaving through the - terminal) so that every component on your robot receives its required supply of current to function?

Hint

1 For those who are electronics-inclined, imagine that you have the ability to adjust the potential on any componentwithout altering its current requirement, or equivalently that there is an accurate variable potentiometer connected in series with each component that you can adjust. Your power supply will have ample potential for the circuit.

Input

The input file will contain multiple test cases. Each test case begins with a single line containing two integers: N (0 <= N <= 50), the number of junctions not including the positive and negative terminals, and M (1 <= M <= 200), the number of components in the circuit diagram. The next M lines each contain a description of some component in the diagram. The ith component description contains three fields: pi, the positive junction to which the component is connected, ni, the negative junction to which the component is connected, and an integer Ii (1 <= Ii <= 100), the minimum amount of current required for component i to function. The junctions pi and ni are specified as either the character '+' indicating the positive terminal, the character '-' indicating the negative terminal, or an integer (between 1 and N) indicating one of the numbered junctions. No two components have the same positive junction and the same negative junction. The end-of-file is denoted by an invalid test case with N = M = 0 and should not be processed.

Output

For each input test case, your program should print out either a single integer indicating the minimum amount of current that must be supplied at the positive terminal in order to ensure that every component is powered, or the message "impossible" if there is no way to direct a sufficient amount of current to each component simultaneously.

Sample Input

6 10
+ 1 1
1 2 1
1 3 2
2 4 5
+ - 1
4 3 2
3 5 5
4 6 2
5 - 1
6 5 3
4 6
+ 1 8
1 2 4
1 3 5
2 4 6
3 - 1
3 4 3
0 0

Sample Output

9
impossible

题解

这是一道有上下界的网络流有源汇求最小流
我们按照无源汇的可行流来做，只是一开始不加上汇点到源点的那条边
然后在加上源点到汇点那条下界为0上界为正无穷的边，再跑一次最大流，新加入的边的反边里的流量就是最小流
为什么呢，因为一开始做可行流的时候最大限度的计算了可以互相补偿下界使得流量平衡的流，然后再加上那条边使得从源点到汇点流过的流量尽可能小

代码

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. struct node {
  13.     int to,next,val;
  14. }edge[10005];
  15. int sumedge,head[55];
  16. void add(int u,int v,int c) {
  17.     edge[++sumedge].to=v;
  18.     edge[sumedge].next=head[u];
  19.     edge[sumedge].val=c;
  20.     head[u]=sumedge;
  21. }
  22. void addtwo(int u,int v,int c) {
  23.     add(u,v,c);add(v,u,0);
  24. }
  25. int source,sink,n,m,dis[55],gap[55],d[55];
  26. char s1[10],s2[10];
  27. int sap(int u,int aug) {
  28.     if(u==sink) return aug;
  29.     int dmin=sink-1,flow=0;
  30.     for(int i=head[u];i;i=edge[i].next) {
  31.         if(edge[i].val>0) {
  32.             int v=edge[i].to;
  33.             if(dis[v]+1==dis[u]) {
  34.                 int t=sap(v,min(edge[i].val,aug-flow));
  35.                 flow+=t;
  36.                 edge[i].val-=t;
  37.                 edge[i^1].val+=t;
  38.                 if(flow==aug) return flow;
  39.                 if(dis[source]>=sink) return flow;
  40.             }
  41.             dmin=min(dmin,dis[v]);
  42.         }
  43.     }
  44.     if(!flow) {
  45.         --gap[dis[u]];
  46.         if(gap[dis[u]]==0) dis[source]=sink;
  47.         dis[u]=dmin+1;
  48.         ++gap[dis[u]];
  49.     }
  50.     return flow;
  51. }
  52. void solve() {
  53.     memset(head,0,sizeof(head));sumedge=1;
  54.     memset(d,0,sizeof(d));
  55.     source=n+3;sink=n+4;
  56.     int u,v,c;
  57.     siji(i,1,m) {
  58.         scanf("%s%s%d",s1+1,s2+1,&c);
  59.         if(s1[1]=='+') u=n+1;
  60.         else sscanf(s1+1,"%d",&u);
  61.         if(s2[1]=='-') v=n+2;
  62.         else sscanf(s2+1,"%d",&v);
  63.         d[u]-=c;
  64.         d[v]+=c;
  65.         addtwo(u,v,0x7fffffff);
  66.     }
  67.     int tot=0;
  68.     siji(i,1,n+2) {
  69.         if(d[i]>0) addtwo(source,i,d[i]),tot+=d[i];
  70.         else if(d[i]<0) addtwo(i,sink,-d[i]);
  71.     }
  72.     memset(dis,0,sizeof(dis));
  73.     memset(gap,0,sizeof(gap));
  74.     while(dis[source]<sink) tot-=sap(source,tot);
  75.     addtwo(n+2,n+1,0x7fffffff);
  76.     memset(dis,0,sizeof(dis));
  77.     memset(gap,0,sizeof(gap));
  78.     while(dis[source]<sink) tot-=sap(source,tot);
  79.     if(tot) puts("impossible");
  80.     else {
  81.         printf("%d\n",edge[sumedge].val);
  82.     }
  83. }
  85. int main() {
  86. #ifdef ivorysi
  87.     freopen("f1.in","r",stdin);
  88. #endif
  89.     while(scanf("%d%d",&n,&m)!=EOF) {
  90.         if(n+m==0) break;
  91.         solve();
  92.     }
  93.     return 0;
  94. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注