JZOJ 5495 MiniumCut （最小割树）

发表于 |
字数统计: 819字 | 阅读时长 ≈ 4min

MiniumCut

Description

从前有张图。
图里 n 个顶点两两之间有 $n^2$ 种最小割。
告诉你这 $n^2$ 个最小割。
还原出这张图。

Input

第一行一个正整数 n, 表示图的顶点数。
接下来 n 行每行 n 个非负整数, 第 i 行第 j 列的数表示第 i 个点与第 j 个点的最小割。
点的编号从 1 开始。
$v_{ij}$ ≤ $10^5$ 。
保证 $v_{ii}$ = 0。

Output

第一行一个整数 m, 表示图的边数。
接下来每行三个整数 u,v,z。
表示从 u 到 v 存在一条权值为 z 的边。
$1 ≤ u, v ≤ n$
$0 ≤ z ≤ 10^9 $
$m ≤\frac{n(n-1)}{2}$
请注意你给出的图要求联通。
如果无解请输出 −1。
若有多解则输出任意一组解。

Scoring

对于 10% 的数据, n = 2。
对于 100% 的数据, n ≤ 100。

结论题，一张图最多有$n-1$个不同的最小割，并且可以构造成一颗最小割树，最小割树上两点间边的权值的最小值就是他们的最小割，因此本题只需要构造出最小割树就行了。

每次选取一个最小的最小割，然后这个最小割将树分成两部分，然后用并查集将最小割值大于选取值的点对划分到一个集合中，最后必然形成两个无交的集合，如果只有一个那么无解。然后对两个集合递归求解即可。每次选取出来的最小割和对应点对最终构成一颗最小割树。

如果不知道最小割树可以参考CQOI 2016 不同的最小割

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#define N 205
using namespace std;
struct node{int x,y,z;}Edge[N];
set<int>QQ;
int n,G[N][N],tot,F[N];
int GF(int x)
{
	if(F[x]!=x)F[x]=GF(F[x]);
	return F[x];
}
void Merge(int x,int y)
{
	x=GF(x);y=GF(y);
	if(x!=y)F[x]=y;
}
bool Solve(vector<int>Q)
{
	int i,j,k,x,y,Min=1e9,m=Q.size();
	if(m==0||m==1)return 1;
	for(i=0;i<m;i++)
	for(j=0;j<m;j++)if(i!=j)Min=min(Min,G[Q[i]][Q[j]]);
	for(x=0;x<m;x++)
	{
		for(y=0;y<m;y++)if(x!=y&&Min==G[Q[x]][Q[y]])break;
		if(y<m&&x!=y&&Min==G[Q[x]][Q[y]])break;
	}
	x=Q[x];y=Q[y];
	Edge[++tot]=(node){x,y,Min};
	for(i=0;i<m;i++)F[Q[i]]=Q[i];
	for(i=0;i<m;i++)
	for(j=0;j<m;j++)if(G[Q[i]][Q[j]]>Min)Merge(Q[i],Q[j]);
	if(GF(x)==GF(y))return 0;
	k=GF(x);
	vector<int>Q1,Q2;
	for(i=0;i<m;i++)
	{
		if(GF(Q[i])==k)Q1.push_back(Q[i]);
		else Q2.push_back(Q[i]);
	}
	return Solve(Q1)&Solve(Q2);
}
int main()
{
	int i,j,k,x,y;
	vector<int>Q;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		scanf("%d",&x);
		if(i!=j)QQ.insert(x);
		G[i][j]=x;
	}
	if(QQ.size()>n-1)return printf("-1"),0;
	for(i=1;i<=n;i++)Q.push_back(i);
	if(Solve(Q))
	{
		printf("%d\n",n-1);
		for(i=1;i<n;i++)printf("%d %d %d\n",Edge[i].x,Edge[i].y,Edge[i].z);
	}
	else printf("-1");
}