首先是我把我们的第一篇题解

#include <bits/stdc++.h>
using namespace std;
const int MAXN=610,INF=1e9;
int n,m,x,y,z,s,t,dis[MAXN][MAXN],w[MAXN],dap[MAXN],vis[MAXN],ord[MAXN];
int proc (int x) {
	memset(vis,0,sizeof(vis));
	memset(w,0,sizeof(w));
	w[0]=-1;
	for (int i=1;i<=n-x+1;i++) {
		int mx=0;
		for (int j=1;j<=n;j++) {
			if (!dap[j]&&!vis[j]&&w[j]>w[mx]) {mx=j;}
		}
		vis[mx]=1,ord[i]=mx;
		for (int j=1;j<=n;j++) {
			if (!dap[j]&&!vis[j]) {w[j]+=dis[mx][j];}
		}
	}
	s=ord[n-x],t=ord[n-x+1];
	return w[t];
}
int sw () {
	int res=INF;
	for (int i=1;i<n;i++) {
		res=min(res,proc(i));
		dap[t]=1;
		for (int j=1;j<=n;j++) {
			dis[s][j]+=dis[t][j];
			dis[j][s]+=dis[j][t];
		}
	}
	return res;
}
int main () {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) {
		scanf("%d%d%d",&x,&y,&z);
		dis[x][y]+=z,dis[y][x]+=z;
	}
	printf("%d\n",sw());
	return 0;
}

中的一个片段

int sw () {
	int res=INF;
	for (int i=1;i<n;i++) {
		res=min(res,proc(i));
		dap[t]=1;
		for (int j=1;j<=n;j++) {
			dis[s][j]+=dis[t][j];
			dis[j][s]+=dis[j][t];
		}
	}
	return res;
}

改为了

int sw () {
	int res=INF;
	for (int i=1;i<=5;i++) {
		res=min(res,proc(i));
		dap[t]=1;
		for (int j=1;j<=n;j++) {
			dis[s][j]+=dis[t][j];
			dis[j][s]+=dis[j][t];
		}
	}
	return res;
}

通过了洛谷的全部数据并成为了最优解，我本地大量对拍也卡不掉（）

应该是可以手搓出来的，但是我太懒了。

足以说明这题数据有点太水了。。

也许就是这个原因，引出了我下一个疑问，也有可能是真的对的，但是我对这个最小割的原理不甚了解，今天刚看懂代码，希望有大佬能 Hack 一下或者证明一下正确性。

int sw () {
	int res=INF;
	for (int i=1;i<n;i++) {
		res=min(res,proc(i));
		dap[t]=1;
		for (int j=1;j<=n;j++) {
			//if(!dap[j]){
  //dap[j]==1表示这个点被合并到其他人身上去了
				dis[s][j]+=dis[t][j];
				dis[j][s]+=dis[j][t];
			//}
		}
	}
	return res;
}

注释掉的那两行是我认为正确的写法，因为如果不这么写的话，合并的权值会加重，比如 (x,y) 合并成 y，然后 (y,z) 合并成 z，此时考察 d[x][j],d[y][j],d[z][j]，我们有

d[y][j]+=d[x][j];
d[z][j]+=d[x][j];
d[z][j]+=d[y][j],

显然 d[z][j] 被多加了。

关于这个问题我本地也大量对拍了，没有发现问题。

不知道这个是否有依据