最小割树

题目大意：

给定N*N的邻接矩阵,表示i，j的最小割为x

求还原的图

题解：

显然最小割图去掉非割边就变成了树

且树中任意两点间最小边值为x,那么我们就可以构造这棵树

按权值从大到小排序，直接跑最大生成树即可

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=105;
 9 int map[N][N];
10 struct node{
11     int x,y,z;
12 }e[N*N];
13 bool comp(const node &pp,const node &qq){
14     return pp.z>qq.z;
15 }
16 int fa[N];
17 int find(int x){
18     return fa[x]==x?x:fa[x]=find(fa[x]);
19 }
20 struct haha{
21     int x,y,z;
22 }ans[N];
23 int dt=-1;
24 struct LIn{
25     int next,to,dis;
26 }a[N*N*2];
27 int head[N],NUM=0;
28 void init(int x,int y,int z){
29     a[++NUM].next=head[x];
30     a[NUM].to=y;a[NUM].dis=z;
31     head[x]=NUM;
32 }
33 void dfs(int x,int y,int last,int dist){
34     int u;
35     if(x==y){
36         dt=dist;
37         return ;
38     }
39     if(dt!=-1)return ;
40     for(int i=head[x];i;i=a[i].next){
41         u=a[i].to;
42         if(u==last)continue;
43         dfs(u,y,x,min(dist,a[i].dis));
44     }
45 }
46 bool check(int x,int y){
47     dt=-1;
48     dfs(x,y,x,2e8);
49     return dt==map[x][y];
50 }
51 void work()
52 {
53     int n;
54     scanf("%d",&n);
55     for(int i=1;i<=n;i++)
56         for(int j=1;j<=n;j++)
57             scanf("%d",&map[i][j]);
58     for(int i=1;i<=n;i++)
59         for(int j=1;j<=n;j++)
60             if(map[i][j]!=map[j][i]){
61                 printf("-1");
62                 return ;
63             }
64     int num=0;
65     for(int i=1;i<=n;i++)
66         for(int j=i+1;j<=n;j++){
67             e[++num].x=i;e[num].y=j;e[num].z=map[i][j];
68         }
69     for(int i=1;i<=n;i++)fa[i]=i;
70     sort(e+1,e+num+1,comp);
71     int cnt=0;
72     for(int i=1;i<=num;i++){
73         if(find(e[i].x)==find(e[i].y)){
74             if(!check(e[i].x,e[i].y)){
75                 printf("-1");
76                 return ;
77             }
78             continue;
79         }
80         fa[find(e[i].x)]=find(e[i].y);
81         init(e[i].x,e[i].y,e[i].z);init(e[i].y,e[i].x,e[i].z);
82         ans[++cnt].x=e[i].x;ans[cnt].y=e[i].y;ans[cnt].z=e[i].z;
83         if(cnt==n-1)break;
84     }
85     printf("%d
",n-1);
86     for(int i=1;i<=cnt;i++){
87         printf("%d %d %d
",ans[i].x,ans[i].y,ans[i].z);
88     }
89     return ;
90 }
91 
92 int main()
93 {
94     freopen("cut.in","r",stdin);
95     freopen("cut.out","w",stdout);
96     work();
97     return 0;
98 }