Drainage Ditches
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11306 Accepted Submission(s): 5328
Problem Description Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.
Input The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.
Output For each case, output a single integer, the maximum rate at which water may emptied from the pond.
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50
Source USACO 93
题大意：给出边数N,点数M，每条边都是单向的，问从1点到M的最大流是多少。
方法一：ISAP
?
#include
#include
#include
using namespace std; #define captype __int64 const int MAXN = 100010; const int MAXM = 400010; const int INF = 1<<30; struct EDG{ int to,next; captype cap,flow; } edg[MAXM]; int eid,head[MAXN]; int gap[MAXN]; //每种距离(或可认为是高度)点的个数 int dis[MAXN]; //每个点到终点eNode 的最短距离 int cur[MAXN]; //cur[u] 表示从u点出发可流经 cur[u] 号边 void init(){ eid=0; memset(head,-1,sizeof(head)); } //有向边 三个参数，无向边4个参数 void addEdg(int u,int v,captype c,captype rc=0){ edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++; edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++; } //预处理eNode点到所有点的最短距离 void BFS(int sNode, int eNode){ queue
q; memset(gap,0,sizeof(gap)); memset(dis,-1,sizeof(dis)); gap[0]=1; dis[eNode]=0; q.push(eNode); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u]; i!=-1; i=edg[i].next){ int v=edg[i].to; if(dis[v]==-1){ dis[v]=dis[u]+1; gap[dis[v]]++; q.push(v); } } } } int S[MAXN]; //路径栈，存的是边的id号 captype maxFlow_sap(int sNode,int eNode, int n){ BFS(sNode, eNode); //预处理eNode到所有点的最短距离 if(dis[sNode]==-1) return 0; //源点到不可到达汇点 memcpy(cur,head,sizeof(head)); int top=0; //栈顶 captype ans=0; //最大流 int u=sNode; while(dis[sNode]
edg[S[i]].cap-edg[S[i]].flow){ Min=edg[S[i]].cap-edg[S[i]].flow; inser=i; } for(int i=0; i
0 && dis[u]==dis[v]+1){ flag=true; cur[u]=i; break; } } if(flag){ S[top++] = cur[u]; //加入一条边 u=v; continue; } //如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1 int Mind= n; for(int i=head[u]; i!=-1; i=edg[i].next){ if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){ Mind=dis[edg[i].to]; cur[u]=i; }} gap[dis[u]]--; if(gap[dis[u]]==0) return ans; //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径 //因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，然而当前点又没能找到可流向的点，那么必然断流 dis[u]=Mind+1; //如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1 gap[dis[u]]++; if(u!=sNode) u=edg[S[--top]^1].to; //退一条边 } return ans; } int main(){ int n,m,u,v; captype c; while(scanf("%d%d",&m,&n)>0){ init(); while(m--){ scanf("%d%d%I64d",&u,&v,&c); addEdg(u,v,c); } printf("%I64d\n",maxFlow_sap(1,n,n)); } }
方法二：压入重标记push_relabel
?
?
#include
#include
#include
using namespace std; #define captype __int64 const int N = 210; const int MAX= 1<<30; struct EDG{ int to,nxt; captype c; //每条边的残留量 }edg[N*N]; int head[N],eid; captype vf[N]; //顶点的剩余流量 int h[N]; //顶点的高度 //int n; //顶点个总个数，包含源点与汇点 int min(int a,int b){return a>b?b:a; } void init(){ memset(head,-1,sizeof(head)); eid=0; } //添加 有向边 void addEdg(int u , int v, captype c){ edg[eid].to=v; edg[eid].nxt=head[u]; edg[eid].c=c; head[u]=eid++; edg[eid].to=u; edg[eid].nxt=head[v]; edg[eid].c=0; head[v]=eid++; } capty