题目大意：给一个无向图,任选两个不同的点作为源点和汇点做最小割,问所有最小割的最小值。
解题思路：解题什么都看这篇吧。传送门，我找了这么多中解释的比较好的。
但是网上还有一种代码量更少的思路,( 整体上是一样的,但是删点的时候处理方式不一样 )
我用的的是代码量较少的。
貌似这是道模板题,整个OJ就这么一道,
把模板掌握了应该就够用了..
我同样会把原思路中的代码贴在下面,
如果这种删点方式理解不了的话可以先看第二个模板。
(我就因为那个删点的马甲没理解以为我把算法理解错了,足足坑了两天)
算法框架：
1. 设当前找到的最小割MinCut 为+∞
2. 在 G中求出任意 s-t 最小割 c，MinCut = min(MinCut, c)
3. 对 G作 Contract(s, t)操作，得到 G'=(V', E')，若|V'| > 1，则G=G'并转 2，否则MinCut 为原图的全局最
小割
Contract 操作定义：
若不存在边(p, q)，则定义边(p, q)权值w(p, q) = 0
Contract(a, b): 删掉点 a, b 及边(a, b)，加入新节点 c，对于任意 v V ∈ ，w(v, c) = w(c, v) = w(a, v) + w(b,
v)
求 G=(V, E)中任意 s-t 最小割的算法：
定义w(A, x) = ∑w(v[i], x)，v[i] ∈ A
定义 Ax 为在x 前加入 A 的所有点的集合（不包括 x）
1. 令集合 A={a}，a为 V中任意点
2. 选取 V - A中的 w(A, x)最大的点 x加入集合 A
3. 若|A|=|V|，结束
令倒数第二个加入 A的点为 s，最后一个加入 A的点为 t，则s-t 最小割为 w(At, t)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define DSC(i,r,l) for(int i=(r);i>=(l);--i)
#define N 510
int map[N][N];
int sum[N];//记录w(A,i)
int v[N]; //给每个点装个马甲,在删点的时候用
bool visit[N];//标记是否加入了A集合
int solve(int n)
{
int ans=1e9;
REP(i,n) v[i]=i; //最开始每个马甲初始化为自身
while(n>1)
{
memset(visit,0,sizeof(visit));
memset(sum,0,sizeof(sum));
int k,pre=0;
for(int i=1;i<n;i++)
{
k=-1;
for(int j=1;j<n;j++)
if(!visit[v[j]])
{
sum[v[j]]+=map[v[pre]][v[j]];
if(k==-1 || sum[v[k]]<sum[v[j]]) k=j; //选择出最大的w(A,v[j])
}
visit[v[k]]=1;//把v[k]只想的点加入A集合
//在循环的过程中马甲会变化,v[k]不一定是指向k的
if(i==n-1) break;
pre=k;
}
ans=min(ans,sum[v[k]]);
if(ans==0) return 0;
REP(j,n) map[v[j]][v[pre]]=map[v[pre]][v[j]]+=map[v[k]][v[j]];
v[k]=v[--n];
//这就是这道题为什么要用马甲的地方
//你需要删掉的是k点,并且总点数要减一
//所以你就把马甲披在了第n-1个点上,而因为--n了,以后的循环便不会直接循环到第n-1个点
//而是通过v[k]来访问第n-1个点,同时删掉了k点
}
return ans;
}
int main()
{
int n,m,x,y,c;
while(cin>>n>>m)
{
memset(map,0,sizeof(map));
while(m--)
{
scanf("%d%d%d",&x,&y,&c);
map[x][y]+=c;
map[y][x]+=c;
}
cout<<solve(n)<<endl;
}
return 0;
}
接下来来一发正常的删点的模板,来自 路竹
#include<cstdio>
#include<cstring>
#include<climits>
const int N = 501;
int n,mat[N][N],del[N],vis[N],dist[N];
int S,T;
int search(int tn){//T表征最后一个扩展进最大生成树的点,S是倒数第二个
int i,j,tmp,max,cut;
T=S=-1;
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));//最大生成树
for(i=0;i<=n-tn;i++){
max=-1;
for(j=0;j<n;j++){
if(!vis[j] && !del[j] && dist[j]>max)
max=dist[j], tmp=j;
}
S=T; T=tmp;
cut=max;
vis[T]=1;
for(j=0;j<n;j++){
if(!vis[j] && !del[j])
dist[j]+=mat[T][j];
}
}
return cut;
}
int Stoer_Wagner(){
int ans=INT_MAX;
memset(del,0,sizeof(del));
for(int i=1;i<n;i++){//i 表征搜索次数,i越大图中剩余的点越少,自然搜索次数越少
int cut=search(i);
if(cut<ans)ans=cut;
if(ans==0)return 0;//图不连通时最小割为0
del[T]=1;
for(int j=0;j<n;j++){//S,T合并
if(!del[j])mat[S][j]=mat[j][S]+=mat[T][j];
}
}
return ans;
}
int main()
{
int a,b,c,m;
while(~scanf("%d%d",&n,&m))
{
memset(mat,0,sizeof(mat));
while(m--){
scanf("%d%d%d",&a,&b,&c);
mat[a][b]=mat[b][a]+=c;
}
int ans=Stoer_Wagner();
printf("%d\n",ans);
}
return 0;
}