题意：和普通的求最大流没什么区别，就是多源点多汇点，只要建立一个超级源点和汇点就行了。
#include <queue> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 10000+5; const int INF = 0x3f3f3f3f; struct Edge { int from,to,cap,flow; }; vector<Edge> edges;//e和e^1互为反向弧 vector<int> G[maxn];//图的邻接表，表示节点i的第j条边在边数组里的编号 int d[maxn];// 用来记录标号距离（层次图使用） int cur[maxn];//当前弧的下标 bool vst[maxn]; int n, m, s, t;//节点数，边数，super源点编号，super汇点编号 int nt,ns; // 源点个数，汇点个数 void Init() //清空图 { for(int i=0; i<maxn; i++) { G[i].clear(); } edges.clear(); } void AddEdge(int from,int to,int cap) //加边时考虑到流量推回，再建立一条反向的边 { edges.push_back((Edge) { from,to,cap,0 }); edges.push_back((Edge) { to,from,0,0 }); int sz=edges.size(); G[from].push_back(sz-2); G[to].push_back(sz-1); } bool BFS() //BFS建立层次图 { memset(vst,false,sizeof(vst)); queue<int> Q; Q.push(s); d[s]=0; vst[s]= true; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=0; i<G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(!vst[e.to]&&e.cap>e.flow) //这里很关键，容量和流量的关系判断能否前进到汇点，如果没有増广路连接汇点的话，说明已经找到了最大流量了。 { d[e.to]=d[u]+1; vst[e.to]=true; Q.push(e.to); } } } return vst[t]; } int DFS(int u,int a) //传入的u为当前节点，a为到目前为止所有弧的最小残量 { if(u==t||a==0) return a; int f,flow= 0; for(int i=cur[u]; i<G[u].size(); i++) //从上次考虑的弧开始避免重复计算 { Edge& e = edges[G[u][i]]; if(d[e.to]==d[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { e.flow+=f; edges[G[u][i]^1].flow -= f; flow+=f; a-=f; if(a==0) break; } } return flow; } int Maxflow() { int flow = 0; while(BFS())//每次都寻找当前层的増广 { memset(cur,0,sizeof(cur)); flow += DFS(s,INF); } return flow; } int main() { while(cin >> n >> ns >> nt >> m) { Init(); int from,to,cap; char ch; for(int i=0; i<m; i++) { cin >> ch >> from >> ch >> to >>ch >> cap ; from+=2; to+=2; AddEdge(from,to,cap); } int pow,number; for(int i=0; i<ns; i++) { cin >> ch >> number >> ch >> pow ; number+=2; AddEdge(1,number,pow); } for(int i=0; i<nt; i++) { cin >> ch >> number >> ch >> pow ; number+=2; AddEdge(number,n+2,pow); } s=1; t=n+2; cout << Maxflow() <<endl; } return 0; }
