题意：
给n个点，，m条边，有np个源点，nc个汇点，求最大流
思路：
超级源点把所有源点连起来，边权是该源点的最大允许值；
所有汇点和超级汇点连接起来，边权是该汇点的最大允许值；
跑最大流
code：
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<queue>#include<map>#include<set>#include<cmath>#include<cstdlib>using namespace std;#define INF 0x3f3f3f3f#define PI acos(-1.0)#define mem(a, b) memset(a, b, sizeof(a))typedef pair<int,int> pii;typedef long long LL;//——————————const int maxn = 205;const int maxm = 205 * 205;const int max_nodes = maxn;struct Edge{int from, to;int capacity, flow;Edge(){}Edge(int from_, int to_, int capacity_, int flow_){from = from_;to = to_;capacity = capacity_;flow = flow_;}};Edge edges[maxm];int cnte;vector<int> g[maxn];void graph_init(){cnte = 0;for(int i = 0; i < maxn; i++) g[i].clear();}void add_Edge(int from, int to, int cap){edges[cnte].from = from;edges[cnte].to = to;edges[cnte].capacity = cap;edges[cnte].flow = 0;g[from].push_back(cnte);cnte++;edges[cnte].from = to;edges[cnte].to = from;edges[cnte].capacity = 0;edges[cnte].flow = 0;g[to].push_back(cnte);cnte++;}int source;// 源点int sink;// 汇点int p[maxn]; // 可增广路上的上一条弧的编号int num[maxn]; // 和 t 的最短距离等于 i 的节点数量int cur[maxn]; // 当前弧下标int d[maxn]; // 残量网络中节点 i 到汇点 t 的最短距离bool visited[maxn];int num_nodes, num_edges;void bfs(){// 预处理, 反向 BFS 构造 d 数组memset(visited, 0, sizeof(visited));queue<int> q;q.push(sink);visited[sink] = true;d[sink] = 0;while(!q.empty()){int u = q.front(); q.pop();for(int i = 0; i < g[u].size(); i++){Edge& e = edges[g[u][i] ^ 1];int v = e.from;if(!visited[v] && e.capacity > e.flow){visited[v] = true;d[v] = d[u] + 1;q.push(v);}}}}int augment(){// 增广int u = sink, df = INF;// 从汇点到源点通过 p 追踪增广路径, df 为一路上最小的残量while(u != source){Edge& e = edges[p[u]];df = min(df, e.capacity – e.flow);u = e.from;}u = sink;// 从汇点到源点更新流量while(u != source){Edge& e = edges[p[u]];e.flow += df;edges[p[u]^1].flow -= df;u = e.from;}return df;}int max_flow(){int flow = 0;bfs();memset(num, 0, sizeof(num));for(int i = 0; i < num_nodes; i++) num[d[i]] ++; // 这个地方，针对的是点从0开始编号的情况int u = source;memset(cur, 0, sizeof(cur));while(d[source] < num_nodes){if(u == sink){flow += augment();u = source;}bool advanced = false;for(int i = cur[u]; i < g[u].size(); i++){Edge& e = edges[g[u][i]];if(e.capacity > e.flow && d[u] == d[e.to] + 1){advanced = true;p[e.to] = g[u][i];cur[u] = i;u = e.to;break;}}if(!advanced){ //retreatint m = num_nodes – 1;for(int i = 0; i < g[u].size(); i++){Edge& e = edges[g[u][i]];if(e.capacity > e.flow) m = min(m, d[e.to]);}if(–num[d[u]] == 0) break;// gap 优化num[d[u] = m+1] ++;cur[u] = 0;if(u != source){u = edges[p[u]].from;}}}return flow;}//————————我是分界线，上面是模板————————–int np, nc, n, m;void solve(){graph_init();int u, v, w;char ch;for(int i = 1; i <= m; i++){while(scanf("%c", &ch)){if(ch == '(') break;}scanf("%d,%d%c%d",&u,&v,&ch,&w);add_Edge(u, v, w);}for(int i = 1; i <= np; i++){while(scanf("%c", &ch)){if(ch == '(') break;}scanf("%d%c%d",&u, &ch, &w);add_Edge(n, u, w);}for(int i = 1; i <= nc; i++){while(scanf("%c", &ch)){if(ch == '(') break;}scanf("%d%c%d",&v, &ch, &w);add_Edge(v, n+1, w);}num_nodes = n+2;source = n; sink = n+1;int ans = max_flow();printf("%d\n",ans);}int main(){while(scanf("%d%d%d%d",&n,&np, &nc, &m) != EOF){solve();}return 0;}
终于自己写了一个还不错的最大流啦….窝原来用的那个模板我囧的很好了啊！但是我干囧大家好像都再说Dinic是好，又有人在说ISAP好像更棒啊！终于我现在两个都敲一下就好啦~~
ISAP跟DINIC还是有很多相似的。。
版权声明：本文为博主原创文章，未经博主允许不得转载。
人生至少要有两次冲动，一为奋不顾身的爱情，一为说走就走的旅行。
