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){
queueq;
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; i0 && 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++;
}
captype maxFlow(int sNode,int eNode,int n){//源點與匯點
captype minh,ans=0;
queueq;
memset(h,0,sizeof(h));
memset(vf,0,sizeof(vf));
h[sNode]=n+1; //源點的高度
vf[sNode]=MAX; //源點的余流
q.push(sNode);
while(!q.empty()){
int u=q.front(); q.pop();
minh=MAX;
for(int i=head[u]; i!=-1; i=edg[i].nxt){
int v=edg[i].to;
captype fp;
if(edg[i].c0 ){
minh=min(minh, h[v]);
if(u==sNode || h[u]==h[v]+1){
edg[i].c-=fp;
edg[i^1].c+=fp; //反向邊，給個反回的通道
vf[u]-=fp;
vf[v]+=fp;
if(v==eNode) ans+=fp; //當到達匯點時，就加入最大流中
if(v!=sNode && v!=eNode ) //只有即不是源點，也不是匯點時才能進隊列
q.push(v);
}
}
if(vf[u]==0) break; //如果頂點的余流為0，則可以跳出for循環
}
//如果不是源點（也非匯點），且頂點仍有余流，則重新標記 高度+1 入隊
//這裡賦值為最低的相鄰頂點的高度高一個單位,也可以簡單的在原高度+1
if(u!=sNode && vf[u]>0){
h[u] = minh + 1;
q.push(u);
}
}
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(1,n,n));
}
}
方法三：EK
#include
#include
#include
using namespace std;
#define captype __int64
const int N = 205;
captype cap[N][N],f[N][N],rest[N];
int sNode,eNode,pre[N];
void init(){
memset(f,0,sizeof(f));
memset(cap,0,sizeof(cap));
}
bool searchPath(int n){//找一條增廣路
bool vist[N]={0};
queueq;
int u,v;
u=sNode; vist[u]=1;
pre[u]=u; rest[u]=1<<30;
q.push(u);
while(!q.empty()){
u=q.front(); q.pop();
for(v=1; v<=n; v++)
if(!vist[v]&&cap[u][v]-f[u][v]>0)
{
vist[v]=1; pre[v]=u;
if(cap[u][v]-f[u][v]>rest[u])
rest[v]=rest[u];
else
rest[v]=cap[u][v]-f[u][v];
if(v==eNode) return true;
q.push(v);
}
}
return false;
}
captype maxflow(int s,int t,int n){
captype ans=0;
sNode=s; eNode=t;
while(searchPath(n)){
ans+=rest[eNode];
int v=eNode;
while(v!=sNode){
int u=pre[v];
f[u][v]+=rest[eNode];
f[v][u]-=rest[eNode];//給一個回流的機會
v=u;
}
}
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);
cap[u][v]+=c;
}
printf("%I64d\n",maxflow(1,n,n));
}
}
