最大流的模板题
给出边数M，顶点数N 以及每条边的容量 求1到N的最大流
注意可以有重边
邻接矩阵模板：
#include<iostream>#include<cstdio>#include<cstring>#define maxx 0x3f3f3f#define M 205using namespace std;int arc[M][M]; //弧的剩余流量int level[M];int n;int min(int a,int b){return a<b?a:b;}int bfs(){int q[M];int head=0,tail=0,v;for(int i=1; i<=n; i++)level[i]=-1;level[1]=0;q[tail++]=1;while(head<tail){v=q[head++];for(int i=1; i<=n; i++)if(level[i]==-1&&arc[v][i]){level[i]=level[v]+1;q[tail++]=i;}}return level[n]!=-1;}int dfs(int loc,int flow){int unused=flow;if(loc==n||flow==0)return flow;for(int i=1; i<=n; i++)if(arc[loc][i]&&level[loc]+1==level[i]){int used=dfs(i,min(unused,arc[loc][i]));arc[loc][i]-=used;arc[i][loc]+=used;unused-=used;}return flow-unused;}int main(){int m;while(~scanf("%d%d",&m,&n)){for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)arc[i][j]=arc[j][i]=0;int a,b,f;while(m–){scanf("%d%d%d",&a,&b,&f);arc[a][b]+=f;}int ans=0;while(bfs())ans+=dfs(1,maxx);cout<<ans<<endl;}return 0;}
邻接表模板：
#include<iostream>#include<cstdio>#include<cstring>#define maxx 0x3f3f3f#define M 205using namespace std;struct arc{int to,value;int pre;}edge[45555];int level[M];int table[M];int n;int sum;int min(int a,int b){return a<b?a:b;}void addedge(int a,int b,int v){edge[sum]={b,v,table[a]};table[a]=sum++;edge[sum]={a,0,table[b]};table[b]=sum++;return;}int bfs(){int q[M];int head=0,tail=0,v;for(int i=1; i<=n; i++)level[i]=-1;level[1]=0;q[tail++]=1;while(head<tail){v=q[head++];for(int i=table[v]; i!=-1; i=edge[i].pre)if(level[edge[i].to]==-1&&edge[i].value){level[edge[i].to]=level[v]+1;q[tail++]=edge[i].to;}}return level[n]!=-1;}int ss=0;int dfs(int loc,int flow){int unused=flow;if(loc==n||flow==0)return flow;for(int i=table[loc]; i!=-1; i=edge[i].pre)if(edge[i].value&&level[loc]+1==level[edge[i].to]){int used=dfs(edge[i].to,min(unused,edge[i].value));edge[i].value-=used;edge[i^1].value+=used; //正向边反向边的的序号的奇偶性不同且差一unused-=used;}return flow-unused;}int main(){int m;while(~scanf("%d%d",&m,&n)){for(int i=1;i<=n;i++)table[i]=-1;sum=0;int a,b,f;while(m–){scanf("%d%d%d",&a,&b,&f);addedge(a,b,f);}int ans=0;while(bfs())ans+=dfs(1,maxx);cout<<ans<<endl;}return 0;}
，想起那座山，那个城，那些人……
