题目链接：?pid=3549题目大意：就是求源点为1，汇点为n的网络最大流题目分析：博客以前有写过几道最大流的题目，可是用的是EK算法，EK这个算法已经可以被淘汰了，因为它的时间复杂度太高，这题用EK搞要2000ms＋，EK算法就不贴了，下面主要提到sap里的两个主流算法，dinic和isap算法，，这两个算法在求解这道题上时间相当，都是150ms左右，但实际上isap的效率是比dinic高的，关于dinic和isap算法的介绍会在别的文章里阐述，这里就贴一下模板Dinic 1: 隐性层次网#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;int const MAX = 16;int const INF = 0x3fffffff;int cap[MAX][MAX];int d[MAX];int n, m;bool BFS(){memset(d, 0, sizeof(d));queue <int> Q;d[1] = 0;Q.push(1);while(!Q.empty()){int cur = Q.front();Q.pop();for(int i = 2; i <= n; i++){if(cap[cur][i] > 0 && d[i] == 0){d[i] = d[cur] + 1;Q.push(i);}}}return d[n];}int Dinic(int t, int flow){if(t == n)return flow;int tmp = flow;for(int i = 1; i <= n; i++){if(d[i] == d[t] + 1 && cap[t][i] > 0){int mi = Dinic(i, min(flow, cap[t][i]));cap[t][i] -= mi;cap[i][t] += mi;flow -= mi;}}return tmp – flow;}int main(){int T;scanf("%d", &T);for(int ca = 1; ca <= T; ca++){memset(cap, 0, sizeof(cap));scanf("%d %d", &n, &m);for(int i = 0; i < m; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);cap[u][v] += w;}int ans = 0;while(BFS())ans += Dinic(1, INF);printf("Case %d: %d\n", ca, ans);}}Dinic 2: 显性层次网#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;int const MAX = 20;int const INF = 0x3fffffff;int cap[MAX][MAX];bool sign[MAX][MAX], vis[MAX];int d[MAX];int n, m;bool BFS(){memset(vis, false, sizeof(vis));memset(sign, false, sizeof(sign));queue <int> Q;d[1] = 0;Q.push(1);while(!Q.empty()){int cur = Q.front();Q.pop();for(int i = 2; i <= n; i++){if(!vis[i] && cap[cur][i]){vis[i] = true;sign[cur][i] = true;Q.push(i);}}}return vis[n];}int Dinic(int t, int flow){if(t == n)return flow;int tmp = flow;for(int i = 2; i <= n; i++){if(sign[t][i]){int mi = Dinic(i, min(flow, cap[t][i]));cap[t][i] -= mi;cap[i][t] += mi;flow -= mi;}}return tmp – flow;}int main(){int T;scanf("%d", &T);for(int ca = 1; ca <= T; ca++){memset(cap, 0, sizeof(cap));scanf("%d %d", &n, &m);for(int i = 0; i < m; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);cap[u][v] += w;}int ans = 0;while(BFS())ans += Dinic(1, INF);printf("Case %d: %d\n", ca, ans);}}ISAP：#include <cstdio>#include <queue>#include <cstring>#include <algorithm>using namespace std;int const INF = 0x3fffffff;int const MAXN = 2000;int const MAXM = 2000;int head[MAXN], gap[MAXN], d[MAXN], cur[MAXN], pre[MAXN];int n, m, e_cnt;struct EDGE{int to, cap, flow, next;}e[MAXM];void Add_Edge(int u, int v, int cap){e[e_cnt].to = v;e[e_cnt].cap = cap;e[e_cnt].flow = 0;e[e_cnt].next = head[u];head[u] = e_cnt ++;e[e_cnt].to = u;e[e_cnt].cap = 0;e[e_cnt].flow = 0;e[e_cnt].next = head[v];head[v] = e_cnt ++;}void BFS(int t){queue <int> Q;memset(gap, 0, sizeof(gap));memset(d, -1, sizeof(d));d[t] = 0;Q.push(t);while(!Q.empty()){int v = Q.front();Q.pop();gap[d[v]] ++;for(int i = head[v]; i != -1; i = e[i].next){int u = e[i].to;if(d[u] == -1){d[u] = d[v] + 1;Q.push(u);}}}}int ISAP(int s, int t){BFS(t);int ans = 0, u = s, flow = INF;memcpy(cur, head, sizeof(cur));while(d[s] < e_cnt){int i = cur[u];for(; i != – 1; i = e[i].next){int v = e[i].to;if(e[i].cap > e[i].flow && d[u] == d[v] + 1){u = v;pre[v] = i;flow = min(flow, e[i].cap – e[i].flow);if(u == t){while(u != s){int j = pre[u];e[j].flow += flow;e[j ^ 1].flow -= flow;u = e[j ^ 1].to;}ans += flow;flow = INF;}break;}}if(i == -1){if(– gap[d[u]] == 0)break;int mi = e_cnt – 1;cur[u] = head[u];for(int j = head[u]; j != -1; j = e[j].next)if(e[j].cap > e[j].flow)mi = min(mi, d[e[j].to]);d[u] = mi + 1;gap[d[u]] ++;if(u != s)u = e[pre[u] ^ 1].to;}}return ans;}int main(){int T, ans;scanf("%d", &T);for(int ca = 1; ca <= T; ca++){scanf("%d %d", &n, &m);e_cnt = 0;memset(head, -1, sizeof(head));for(int i = 0; i < m; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);Add_Edge(u, v, w);}ans = ISAP(1, n);printf("Case %d: %d\n", ca, ans);}}
今天不想走，明天就要跑了。
