题目分析

题意简述

给定一个无向图，其中两个顶点之间可以有多条边连接，求该图的最小割的大小。即至少需要移除多少条边才能将图分成两个子图？如果图已经不连通，则输出 $0$。

输入

• 多组测试用例，每组给出两个整数 $N$ 和 $M$（$2 \leq N \leq 500$，$0 \leq M \leq N \times (N - 1) / 2$）。
• 接下来的 $M$ 行，每行包含三个整数 $A$、$B$ 和 $C$（$0 \leq A, B < N$，$A \neq B$，$C > 0$），表示有 $C$ 条边连接顶点 $A$ 和 $B$。

输出

每组测试用例的结果，表示该图的最小割的大小。如果图已经不连通，则输出 $0$。

解题思路

Stoer-Wagner 算法

本题使用 Stoer-Wagner 算法求解无向图的全局最小割。该算法的核心思想是通过不断合并顶点，逐步缩小图的规模，最终找到最小割。

算法步骤

1. 初始化：固定一个顶点 $P$，初始时 $min = \infty$。
2. 扩展最大生成树：从顶点 $P$ 开始，使用类似 Prim 算法的方法扩展出“最大生成树”，每次选择与当前集合连接边权和最大的顶点加入集合，并记录最后扩展的顶点和边。
3. 计算切割值：计算最后扩展到的顶点的切割值（即与此顶点相连的所有边权和），若比 $min$ 小，则更新 $min$。
4. 合并顶点：合并最后扩展的那条边的两个端点为一个顶点，并更新边权（合并后的顶点与其他顶点的边权为原两个顶点与其他顶点的边权之和）。
5. 重复步骤 2-4：直到图中只剩下一个顶点，此时 $min$ 即为所求的最小割。

关键点

• 合并顶点：每次合并后，图的顶点数减 $1$，边权更新为原两个顶点的边权之和。
• 处理重边：算法自然处理重边，因为边权直接累加。
• 判断不连通：若最终 $min$ 仍为初始值（即图中没有边），则输出 $0$。

代码实现

#include <cstdio>
#include <string.h>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int NMax=550;
int N,M,G[NMax][NMax],dist[NMax],map[NMax];
bool inA[NMax];

int Dinic() {
    int ret=(~0u>>1),s=1,pre;
    for(int i=1;i<=N;i++) map[i]=i;
    while(N>1) {
        memset(inA,0,sizeof(inA));
        inA[map[s]]=1;
        int lastx,lasty;pre=s;
        for(int i=1;i<=N;i++) dist[map[i]]=G[map[s]][map[i]];
        for(int I=1;I<N;I++) {
            int next=-1;
            for(int i=2;i<=N;i++) if(!inA[map[i]]&&(next==-1||dist[map[i]]>dist[map[next]])) next=i;
            inA[map[next]]=1;
            for(int i=1;i<=N;i++) if(!inA[map[i]]) dist[map[i]]+=G[map[next]][map[i]];
            if(I==N-1) {lastx=pre;lasty=next;}
            pre=next;
        }
        ret=min(ret,dist[map[lasty]]);
        for(int i=1;i<=N;i++) G[map[lastx]][map[i]]=G[map[i]][map[lastx]]=G[map[lastx]][map[i]]+G[map[i]][map[lasty]];
        //就是上一行，千万不要写成G[map[lastx]][map[lasty]]+G[map[i]][map[lasty]]
        map[lasty]=map[N--];
    }
    return ret==(~0u>>1)?0:ret;
}

int main()
{
    while(scanf("%d%d",&N,&M)!=EOF) {
        int x,y,z;
        memset(G,0,sizeof(G));
        for(int i=1;i<=M;i++) {
            scanf("%d%d%d",&x,&y,&z);
            x++;y++;
            G[x][y]+=z;G[y][x]+=z;
        }
        printf("%d\n",Dinic());
    }
    return 0;
}

代码说明

1. 输入处理

   • 使用邻接矩阵 G 存储图的边权，处理多组测试用例。
   • 输入的顶点编号加 $1$ 以适应 $1$-based 索引。

2. Stoer-Wagner 算法

   • Dinic() 函数实现核心算法，返回最小割的值。
   • map 数组用于映射合并后的顶点编号。
   • 每次循环找出最大生成树的最后两个顶点，合并它们并更新最小割。

3. 合并顶点

   • 将最后扩展的顶点合并到前一个顶点，并更新边权。
   • 顶点数 $N$ 减 $1$，直到剩下一个顶点。

4. 处理不连通图

   • 若算法结束后 $ret$ 仍为初始值（即图中没有边），返回 $0$。

复杂度分析

• 时间复杂度：$O(N^3)$，其中 $N$ 是顶点数。每次合并操作需要 $O(N^2)$ 时间，共进行 $N-1$ 次合并。
• 空间复杂度：$O(N^2)$，主要用于存储邻接矩阵。