主题链接：

意甲冠军：

给定n个点m条无向边 源点S

以下m行给出无向边以及边的容量。

问：

找一个汇点，使得图的最大流最小。

输出最小的流量。

思路：

最大流=最小割。

所以题意就是找全局最小割。

和源点无关。由于不关心源点在哪个点集里。

模版题： O(n^3)

#include 
     
      #include 
      
       #include 
       
        #include 
        
         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;}
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。