1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 6 using namespace std; 7 const int INF=2147483647; 8 const int maxn=210,maxm=410; 9 int cnt,fir[maxn],nxt[maxm],cap[maxm],to[maxm],dis[maxn],gap[maxn],path[maxn]; 10 11 void addedge(int a,int b,int c) 12 { 13 nxt[++cnt]=fir[a]; 14 to[cnt]=b; 15 cap[cnt]=c; 16 fir[a]=cnt; 17 } 18 19 bool BFS(int S,int T) 20 { 21 memset(dis,0,sizeof(dis)); 22 dis[T]=1; 23 queue<int>q;q.push(T); 24 while(!q.empty()) 25 { 26 int node=q.front();q.pop(); 27 for(int i=fir[node];i;i=nxt[i]) 28 { 29 if(dis[to[i]])continue; 30 dis[to[i]]=dis[node]+1; 31 q.push(to[i]); 32 } 33 } 34 return dis[S]; 35 } 36 int fron[maxn]; 37 int ISAP(int S,int T) 38 { 39 if(!BFS(S,T)) 40 return 0; 41 for(int i=1;i<=T;i++)++gap[dis[i]]; 42 int p=S,ret=0; 43 memcpy(fron,fir,sizeof(fir)); 44 while(dis[S]<=T) 45 { 46 if(p==T){ 47 int f=INF; 48 while(p!=S){ 49 f=min(f,cap[path[p]]); 50 p=to[path[p]^1]; 51 } 52 p=T;ret+=f; 53 while(p!=S){ 54 cap[path[p]]-=f; 55 cap[path[p]^1]+=f; 56 p=to[path[p]^1]; 57 } 58 } 59 int &ii=fron[p]; 60 for(;ii;ii=nxt[ii]){ 61 if(!cap[ii]||dis[to[ii]]+1!=dis[p]) 62 continue; 63 else 64 break; 65 } 66 67 if(ii){ 68 p=to[ii]; 69 path[p]=ii; 70 } 71 72 73 else{ 74 if(--gap[dis[p]]==0)break; 75 int minn=T+1; 76 for(int i=fir[p];i;i=nxt[i]) 77 if(cap[i]) 78 minn=min(minn,dis[to[i]]); 79 gap[dis[p]=minn+1]++; 80 fron[p]=fir[p]; 81 if(p!=S) 82 p=to[path[p]^1]; 83 } 84 } 85 return ret; 86 } 87 88 void Init() 89 { 90 memset(fir,0,sizeof(fir)); 91 memset(gap,0,sizeof(gap)); 92 cnt=1; 93 } 94 int main() 95 { 96 int n,m; 97 while(~scanf("%d%d",&m,&n)) 98 { 99 Init(); 100 for(int i=1;i<=m;i++){ 101 int x,y,c; 102 scanf("%d%d%d",&x,&y,&c); 103 addedge(x,y,c); 104 addedge(y,x,0); 105 } 106 printf("%d ",ISAP(1,n)); 107 } 108 109 return 0; 110 }
后来又打了一遍，代码风格都变了。（这个没有多组数据）
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 const int INF=1000000000; 7 const int maxn=10010; 8 const int maxm=20010; 9 int cnt=1,fir[maxn],to[maxm],nxt[maxm],cap[maxm]; 10 void addedge(int a,int b,int c){ 11 nxt[++cnt]=fir[a]; 12 fir[a]=cnt; 13 cap[cnt]=c; 14 to[cnt]=b; 15 } 16 17 queue<int>q; 18 int dis[maxn]; 19 bool BFS(int s,int t){ 20 dis[t]=1;q.push(t); 21 while(!q.empty()){ 22 int x=q.front();q.pop(); 23 for(int i=fir[x];i;i=nxt[i]) 24 if(!dis[to[i]]){ 25 dis[to[i]]=dis[x]+1; 26 q.push(to[i]); 27 } 28 } 29 return dis[s]; 30 } 31 32 int fron[maxn]; 33 int gap[maxn],path[maxn]; 34 int ISAP(int s,int t){ 35 if(!BFS(s,t))return 0; 36 for(int i=s;i<=t;i++)++gap[dis[i]]; 37 for(int i=s;i<=t;i++)fron[i]=fir[i]; 38 int p=s,ret=0,f; 39 while(dis[s]<=t){ 40 if(p==t){ 41 f=INF; 42 while(p!=s){ 43 f=min(f,cap[path[p]]); 44 p=to[path[p]^1]; 45 } 46 ret+=f;p=t; 47 while(p!=s){ 48 cap[path[p]]-=f; 49 cap[path[p]^1]+=f; 50 p=to[path[p]^1]; 51 } 52 } 53 int &ii=fron[p]; 54 for(;ii;ii=nxt[ii]) 55 if(cap[ii]&&dis[p]==dis[to[ii]]+1) 56 break; 57 if(ii) 58 path[p=to[ii]]=ii; 59 else{ 60 if(--gap[dis[p]]==0)break; 61 int minn=t+1; 62 for(int i=fir[p];i;i=nxt[i]) 63 if(cap[i])minn=min(minn,dis[to[i]]); 64 ++gap[dis[p]=minn+1];ii=fir[p]; 65 if(p!=s)p=to[path[p]^1]; 66 } 67 } 68 return ret; 69 } 70 71 int main(){ 72 int n,m; 73 scanf("%d%d",&m,&n); 74 for(int i=1,a,b,c;i<=m;i++){ 75 scanf("%d%d%d",&a,&b,&c); 76 addedge(a,b,c); 77 addedge(b,a,0); 78 } 79 printf("%d ",ISAP(1,n)); 80 return 0; 81 }
又打一遍，很好看的结构体。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 const int maxn=10010; 7 const int maxm=800010; 8 const int INF=1000000000; 9 int cnt,tot,fir[maxn],fron[maxn],dis[maxn]; 10 int to[maxm],nxt[maxm],gap[maxn],path[maxn]; 11 int cap[maxm];queue<int>q; 12 13 struct Max_Flow{ 14 void Init(int tot_=0){ 15 tot=tot_;cnt=1; 16 memset(fir,0,sizeof(fir)); 17 memset(dis,0,sizeof(dis)); 18 memset(gap,0,sizeof(gap)); 19 } 20 21 void add(int a,int b,int c){ 22 nxt[++cnt]=fir[a]; 23 fir[a]=cnt; 24 cap[cnt]=c; 25 to[cnt]=b; 26 } 27 28 void addedge(int a,int b,int c){ 29 add(a,b,c); 30 add(b,a,0); 31 } 32 33 bool BFS(int s,int t){ 34 dis[t]=1;q.push(t); 35 while(!q.empty()){ 36 int x=q.front();q.pop(); 37 for(int i=fir[x];i;i=nxt[i]) 38 if(!dis[to[i]]){ 39 dis[to[i]]=dis[x]+1; 40 q.push(to[i]); 41 } 42 } 43 return dis[s]; 44 } 45 46 int Aug(int s,int t,int &p){ 47 int f=INF; 48 while(p!=s){ 49 f=min(f,cap[path[p]]); 50 p=to[path[p]^1]; 51 }p=t; 52 while(p!=s){ 53 cap[path[p]]-=f; 54 cap[path[p]^1]+=f; 55 p=to[path[p]^1]; 56 } 57 return f; 58 } 59 60 int ISAP(int s,int t){ 61 if(!BFS(s,t))return 0; 62 for(int i=s;i<=t;i++)fron[i]=fir[i]; 63 for(int i=s;i<=t;i++)gap[dis[i]]+=1; 64 int p=s,ret=0; 65 while(dis[s]<=tot){ 66 if(p==t)ret+=Aug(s,t,p); 67 68 for(int &i=fron[p];i;i=nxt[i]) 69 if(cap[i]&&dis[p]==dis[to[i]]+1){ 70 path[p=to[i]]=i; 71 break; 72 } 73 74 if(!fron[p]){ 75 if(--gap[dis[p]]==0) 76 break; 77 int Min=tot; 78 for(int i=fir[p];i;i=nxt[i]) 79 if(cap[i])Min=min(Min,dis[to[i]]); 80 gap[dis[p]=Min+1]+=1;fron[p]=fir[p]; 81 if(p!=s)p=to[path[p]^1]; 82 } 83 } 84 return ret; 85 } 86 }isap;