HDU 3549 Flow Problem(最大流入门)
http://acm.hdu.edu.cn/showproblem.php?pid=3549
题意:
给你一个N个顶点M条边的有向图,要你求1号点到N号点的最大流.
分析:
注意本题有重边.
code 1:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 16;
int cap[maxn][maxn];
bool vis[maxn];
int n, m, s, t, maxflow;
int dfs(int u, int low)
{int flow;if(u == t)return low;vis[u] = true;for(int v = 1; v <= n; v++){if(!vis[v] && cap[u][v] && (flow = dfs(v, min(low, cap[u][v])))){cap[u][v] -= flow;cap[v][u] += flow;return flow;}}return 0;
}
int main()
{int T, u, v, w, flow;scanf("%d", &T);for(int kase = 1; kase <= T; kase++){scanf("%d%d", &n, &m);memset(cap, 0, sizeof(cap));memset(vis, false, sizeof(vis));for(int i = 1; i <= m ; i++){scanf("%d%d%d", &u, &v, &w);cap[u][v] += w;}s = 1, t = n;maxflow = 0;while(flow = dfs(s, INF)){maxflow += flow;memset(vis, false, sizeof(vis));}printf("Case %d: %d\n", kase, maxflow);}return 0;
}
code2: 多路增广
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 16;
int cap[maxn][maxn];
bool vis[maxn];
int n, m, s, t, maxflow;
int dfs(int u, int low)
{int flow, sum = 0;if(u == t)return low;vis[u] = true;for(int v = 1; v <= n; v++){if(!vis[v] && cap[u][v] && (flow = dfs(v, min(low, cap[u][v])))){sum += flow;low -= flow;cap[u][v] -= flow;cap[v][u] += flow;if(!low)break;}}return sum;
}
int main()
{int T, u, v, w, flow;scanf("%d", &T);for(int kase = 1; kase <= T; kase++){scanf("%d%d", &n, &m);memset(cap, 0, sizeof(cap));memset(vis, false, sizeof(vis));for(int i = 1; i <= m ; i++){scanf("%d%d%d", &u, &v, &w);cap[u][v] += w;}s = 1, t = n;maxflow = 0;while(flow = dfs(s, INF)){maxflow += flow;memset(vis, false, sizeof(vis));}printf("Case %d: %d\n", kase, maxflow);}return 0;
}