主题链接：点击打开链接
意甲冠军：
给定n个点m条无向边 源点S
以下m行给出无向边以及边的容量。
问：
找一个汇点，使得图的最大流最小。
输出最小的流量。
思路：
最大流=最小割。
所以题意就是找全局最小割。
和源点无关。由于不关心源点在哪个点集里。
模版题： O(n^3)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 305;
const ll maxw = 1000007;
const ll inf = 1e17;
ll g[N][N], w[N];
int a[N], v[N], na[N];
ll mincut(int n) {
int i, j, pv, zj;
ll best = inf;
for(i = 0; i < n; i ++) v[i] = i; while(n > 1) {
for(a[v[0]] = 1, i = 1; i < n; i ++) {
a[v[i]] = 0;
na[i-1] = i;
w[i] = g[v[0]][v[i]];
}
for(pv = v[0], i = 1; i < n; i ++) {
for(zj = -1, j = 1; j < n; j ++)
if(!a[v[j]] && (zj < 0 || w[j] > w[zj])) zj = j; a[v[zj]] = 1;
if(i == n-1) {
if(best > w[zj]) best = w[zj];
for(i = 0; i < n; i ++) {
g[v[i]][pv] = g[pv][v[i]] += g[v[zj]][v[i]];
}
v[zj] = v[--n];
break;
}
pv = v[zj];
for(j = 1; j < n; j ++) if(!a[v[j]])
w[j] += g[v[zj]][v[j]];
}
}
return best;
}
int main() {
int n, m, K, u, v ,w;
while(~scanf("%d%d%d", &n, &m, &K)) {
if(n == 0) break;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < n; j ++) {
g[i][j] = g[j][i] = 0;
}
}
for(int i = 0; i < m; i ++) {
scanf("%d%d%d", &u, &v, &w);
u--; v --;
g[u][v] += w;
g[v][u] += w;
}
printf("%lld\n", mincut(n));
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。