1、看了好久，囧。
n个节点，np个源点，nc个汇点，m条边（对应代码中即节点u 到节点v 的最大流量为z）
求所有汇点的最大流。
2、多个源点，多个汇点的最大流。
建立一个超级源点、一个超级汇点，然后求超级源点到超级汇点的最大流即可。
3、
1、SAP邻接矩阵形式：
/* SAP算法（矩阵形式） 结点编号从0开始 */ #include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MAXN=128; int maze[MAXN][MAXN]; int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN]; int sap(int start,int end,int nodenum){ memset(cur,0,sizeof(cur)); memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); int u=pre[start]=start,maxflow=0,aug=-1; gap[0]=nodenum; while(dis[start]<nodenum){ loop: for(int v=cur[u];v<nodenum;v++) if(maze[u][v]&&dis[u]==dis[v]+1){ if(aug==-1||aug>maze[u][v])aug=maze[u][v]; pre[v]=u; u=cur[u]=v; if(v==end){ maxflow+=aug; for(u=pre[u];v!=start;v=u,u=pre[u]){ maze[u][v]-=aug; maze[v][u]+=aug; } aug=-1; } goto loop; } int mindis=nodenum-1; for(int v=0;v<nodenum;v++) if(maze[u][v]&&mindis>dis[v]){ cur[u]=v; mindis=dis[v]; } if((--gap[dis[u]])==0)break; gap[dis[u]=mindis+1]++; u=pre[u]; } return maxflow; } int main(){ int n,np,nc,m;//节点总数，源点，汇点，边数 int u,v,z;//节点u，节点v，最大流量z char str[5];//处理空格 int sp,sc;//超级源点，超级汇点 while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){ memset(maze,0,sizeof(maze)); for(int i=0;i<m;++i){ scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z); maze[u][v]=z; } //建立超级源点 sp=n++; for(int i=0;i<np;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); maze[sp][u]=z; } //建立超级汇点 sc=n++; for(int i=0;i<nc;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); maze[u][sc]=z; } printf("%d\n",sap(sp,sc,n)); } return 0; }
2、SAP邻接矩阵形式2：
/* 保留原矩阵，可用于多次使用最大流 SAP邻接矩阵形式 点的编号从0开始 增加个flow数组，保留原矩阵maze，可用于多次使用最大流 */ #include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MAXN=128; int maze[MAXN][MAXN]; int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN]; int flow[MAXN][MAXN];//存最大流的容量 int sap(int start,int end,int nodenum){ memset(cur,0,sizeof(cur)); memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); memset(flow,0,sizeof(flow)); int u=pre[start]=start,maxflow=0,aug=-1; gap[0]=nodenum; while(dis[start]<nodenum){ loop: for(int v=cur[u];v<nodenum;v++) if(maze[u][v]-flow[u][v]&&dis[u]==dis[v]+1){ if(aug==-1||aug>maze[u][v]-flow[u][v])aug=maze[u][v]-flow[u][v]; pre[v]=u; u=cur[u]=v; if(v==end){ maxflow+=aug; for(u=pre[u];v!=start;v=u,u=pre[u]){ flow[u][v]+=aug; flow[v][u]-=aug; } aug=-1; } goto loop; } int mindis=nodenum-1; for(int v=0;v<nodenum;v++) if(maze[u][v]-flow[u][v]&&mindis>dis[v]){ cur[u]=v; mindis=dis[v]; } if((--gap[dis[u]])==0)break; gap[dis[u]=mindis+1]++; u=pre[u]; } return maxflow; } int main(){ int n,np,nc,m;//节点总数，源点，汇点，边数 int u,v,z;//节点u，节点v，最大流量z char str[5];//处理空格 int sp,sc;//超级源点，超级汇点 while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){ memset(maze,0,sizeof(maze)); for(int i=0;i<m;++i){ scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z); maze[u][v]=z; } //建立超级源点 sp=n++; for(int i=0;i<np;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); maze[sp][u]=z; } //建立超级汇点 sc=n++; for(int i=0;i<nc;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); maze[u][sc]=z; } printf("%d\n",sap(sp,sc,n)); } return 0; }
3、ISAP邻接表形式：注意一下边数的范围
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MAXN=128;//点数的最大值 const int MAXM=20500;//边数的最大值（加的双向加，所以是2倍，别忘了加上超级源点和超级汇点（共400条）） const int INF=0x3f3f3f3f; struct Edge{ int to,next,cap,flow; }edge[MAXM];//注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN]; void init(){ tol=0; memset(head,-1,sizeof(head)); } //加边，单向图三个参数，双向图四个参数 void addedge(int u,int v,int w,int rw=0){ edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u]; edge[tol].flow=0;head[u]=tol++; edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v]; edge[tol].flow=0;head[v]=tol++; } //输入参数：起点、终点、点的总数 //点的编号没有影响，只要输入点的总数 int sap(int start,int end,int N){ memset(gap,0,sizeof(gap)); memset(dep,0,sizeof(dep)); memcpy(cur,head,sizeof(head)); int u=start; pre[u]=-1; gap[0]=N; int ans=0; while(dep[start]<N){ if(u==end){ int Min=INF; for(int i=pre[u];i!=-1;i=pre[edge[i^1].to]) if(Min>edge[i].cap-edge[i].flow) Min=edge[i].cap-edge[i].flow; for(int i=pre[u];i!=-1;i=pre[edge[i^1].to]){ edge[i].flow+=Min; edge[i^1].flow-=Min; } u=start; ans+=Min; continue; } bool flag=false; int v; for(int i=cur[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){ flag=true; cur[u]=pre[v]=i; break; } } if(flag){ u=v; continue; } int Min=N; for(int i=head[u];i!=-1;i=edge[i].next) if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){ Min=dep[edge[i].to]; cur[u]=i; } gap[dep[u]]--; if(!gap[dep[u]])return ans; dep[u]=Min+1; gap[dep[u]]++; if(u!=start)u=edge[pre[u]^1].to; } return ans; } int main(){ int n,np,nc,m;//节点总数，源点，汇点，边数 int u,v,z;//节点u，节点v，最大流量z char str[5];//处理空格 int sp,sc;//超级源点，超级汇点 while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){ init(); for(int i=0;i<m;++i){ scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z); addedge(u,v,z); } //建立超级源点 sp=n++; for(int i=0;i<np;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); addedge(sp,u,z); } //建立超级汇点 sc=n++; for(int i=0;i<nc;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); addedge(u,sc,z); } printf("%d\n",sap(sp,sc,n)); } return 0; }
4、ISAP+bfs初始化+栈优化：注意一下边数的范围
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MAXN=128;//点数的最大值 const int MAXM=20500;//边数的最大值 const int INF=0x3f3f3f3f; struct Edge{ int to,next,cap,flow; }edge[MAXM];//注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN]; void init(){ tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w,int rw=0){ edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0; edge[tol].next=head[u];head[u]=tol++; edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0; edge[tol].next=head[v];head[v]=tol++; } int Q[MAXN]; void BFS(int start,int end){ memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=1; int front=0,rear=0; dep[end]=0; Q[rear++]=end; while(front!=rear){ int u=Q[front++]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(dep[v]!=-1)continue; Q[rear++]=v; dep[v]=dep[u]+1; gap[dep[v]]++; } } } int S[MAXN]; int sap(int start,int end,int N){ BFS(start,end); memcpy(cur,head,sizeof(head)); int top=0; int u=start; int ans=0; while(dep[start]<N){ if(u==end){ int Min=INF; int inser; for(int i=0;i<top;i++) if(Min>edge[S[i]].cap-edge[S[i]].flow){ Min=edge[S[i]].cap-edge[S[i]].flow; inser=i; } for(int i=0;i<top;i++){ edge[S[i]].flow+=Min; edge[S[i]^1].flow-=Min; } ans+=Min; top=inser; u=edge[S[top]^1].to; continue; } bool flag=false; int v; for(int i=cur[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){ flag=true; cur[u]=i; break; } } if(flag){ S[top++]=cur[u]; u=v; continue; } int Min=N; for(int i=head[u];i!=-1;i=edge[i].next) if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){ Min=dep[edge[i].to]; cur[u]=i; } gap[dep[u]]--; if(!gap[dep[u]])return ans; dep[u]=Min+1; gap[dep[u]]++; if(u!=start)u=edge[S[--top]^1].to; } return ans; } int main(){ int n,np,nc,m;//节点总数，源点，汇点，边数 int u,v,z;//节点u，节点v，最大流量z char str[5];//处理空格 int sp,sc;//超级源点，超级汇点 while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){ init(); for(int i=0;i<m;++i){ scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z); addedge(u,v,z); } //建立超级源点 sp=n++; for(int i=0;i<np;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); addedge(sp,u,z); } //建立超级汇点 sc=n++; for(int i=0;i<nc;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); addedge(u,sc,z); } printf("%d\n",sap(sp,sc,n)); } return 0; }
5、dinic：注意一下边数的范围
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MAXN=128;//点数的最大值 const int MAXM=20500;//边数的最大值 const int INF=0x3f3f3f3f; struct Edge{ int to,next,cap,flow; }edge[MAXM];//注意是MAXM int tol; int head[MAXN]; void init(){ tol=2; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w,int rw=0){ edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0; edge[tol].next=head[u];head[u]=tol++; edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0; edge[tol].next=head[v];head[v]=tol++; } int Q[MAXN]; int dep[MAXN],cur[MAXN],sta[MAXN]; bool bfs(int s,int t,int n){ int front=0,tail=0; memset(dep,-1,sizeof(dep[0])*(n+1)); dep[s]=0; Q[tail++]=s; while(front<tail){ int u=Q[front++]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(edge[i].cap>edge[i].flow&&dep[v]==-1){ dep[v]=dep[u]+1; if(v==t)return true; Q[tail++]=v; } } } return false; } int dinic(int s,int t,int n){ int maxflow=0; while(bfs(s,t,n)){ for(int i=0;i<n;i++)cur[i]=head[i]; int u=s,tail=0; while(cur[s]!=-1){ if(u==t){ int tp=INF; for(int i=tail-1;i>=0;i--) tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow); maxflow+=tp; for(int i=tail-1;i>=0;i--){ edge[sta[i]].flow+=tp; edge[sta[i]^1].flow-=tp; if(edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i; } u=edge[sta[tail]^1].to; } else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){ sta[tail++]=cur[u]; u=edge[cur[u]].to; } else{ while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to; cur[u]=edge[cur[u]].next; } } } return maxflow; } int main(){ int n,np,nc,m;//节点总数，源点，汇点，边数 int u,v,z;//节点u，节点v，最大流量z char str[5];//处理空格 int sp,sc;//超级源点，超级汇点 while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){ init(); for(int i=0;i<m;++i){ scanf("%1s%d%1s%d%1s%d",str,&u,str,&v,str,&z); addedge(u,v,z); } //建立超级源点 sp=n++; for(int i=0;i<np;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); addedge(sp,u,z); } //建立超级汇点 sc=n++; for(int i=0;i<nc;++i){ scanf("%1s%d%1s%d",str,&u,str,&z); addedge(u,sc,z); } printf("%d\n",dinic(sp,sc,n)); } return 0; }
POJ - 1459 Power Network（最大流）（模板）
原文：http://www.cnblogs.com/bofengyu/p/4986704.html
