题目大意:有一个有n个点的,求1到n的最大流
1<=n<=15
思路:从起点开始寻找能够到达终点的路径,并找出这条路径上的最小容量,沿着这条路每条边的容量对应减少,反向边增加,直至找不到这样一条路径为止
- #include
- using namespace std;
- const int N = 1e3 + 5;
- int g[20][20];//邻接矩阵存图
- int pre[20], cnt = 0;
- bool vis[20];
- int n, m;
- int mi = 1000;
- bool bfs(int s, int t)
- {//验证在残余网络中是否有增广路
- memset(pre, -1, sizeof pre);
- memset(vis, 0, sizeof vis);
- queue<int>q;
- mi = 1000;
- vis[s] = 1;
- q.push(s);
- while (!q.empty())
- {
- int u = q.front();
- q.pop();
- for (int i=1;i<=n;i++)
- {
- if (!vis[i] && g[u][i]!=0)
- {
- vis[i] = 1;
- pre[i] = u;//记录路径
- q.push(i);
- mi = min(mi, g[u][i]);//记录最小容量
- if (i == t)//到达终点
- return 1;
- }
- }
- }
- return 0;
- }
- int ek(int s, int t)
- {
- int ans = 0, flow = 0;
- while (bfs(s, t))
- {
- flow = mi;//这个增广路的最小容量
- ans += flow;
- int u = t;
- while (u != s)
- {
- g[pre[u]][u] -= flow;//沿路径的容量减
- g[u][pre[u]] += flow;//反向路径容量+
- u = pre[u];
- }
- }
- return ans;
- }
- int main()
- {
- int t;
- cin >> t;
- for (int cas = 1; cas <= t; cas++)
- {
- scanf("%d%d", &n, &m);
- memset(g, 0, sizeof g);
- for (int i = 1; i <= m; i++)
- {
- int u, v, w;
- scanf("%d%d%d", &u, &v, &w);
- g[u][v] += w;
- }
- printf("Case %d: %d\n", cas,ek(1, n));
- }
- return 0;
- }