已解决
NIT: 初始化邻接矩阵g[][]；| CALL: res = mincut(n)；
来自网友在路上 169869提问 提问时间：2023-09-20 21:51:04阅读次数： 69
最佳答案 问答题库698位专家为你答疑解惑
INIT: 初始化邻接矩阵 g[][];
| CALL: res = mincut(n);
| 注 : Stoer-Wagner Minimum Cut;
| 找边的最小集合，若其被删去则图变得不连通（我们把这种形式称为最小
| 割问题）
\*==================================================*/
#define typec int // type of res
const typec inf = 0x3f3f3f3f; // max of res
const typec maxw = 1000; // maximum edge weight
typec g[V][V], w[V];
int a[V], v[V], na[V];
typec mincut( int n){
int i, j, pv, zj;
typec best = maxw * n * n;
for (i = 0; i < n; i++) v[i] = i; // vertex: 0 ~ n-1
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;
}
查看全文
99%的人还看了
相似问题
猜你感兴趣
版权申明
本文"NIT: 初始化邻接矩阵g[][]；| CALL: res = mincut(n)；"：http://eshow365.cn/6-10235-0.html 内容来自互联网，请自行判断内容的正确性。如有侵权请联系我们，立即删除！