题目大意
给定一个$n(n \le 100)$个点的连通图
不同顶点之间有$n^2$个最小割
现在给定这$n^2$个最小割,让你构造一个图使其满足条件
解题报告
据说这是论文题?
因为任意两点间的最小割可以用最小割树来表示
所以我们考虑构造一个树形结构
因为一条路径上的最小割相当于取$min$,所以流量大的不会影响流量小的
所以我们先按边权从大到小排序
如果当前这条边的两个端点已经在一个连通块内,那么暴力判断是否符合要求
如果不在一个块内,那么连一条边
至于为什么这样是对的,因为已经按权值排序了
如果不在一个连通块内,还不连边,那么最终连通这两块的权值一定大于要求的最小割,所以必须立刻连边
至于已经连边了还冲突的话,因为之前的边都是必要的,所以也没有调整的需要,一定是无解的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 109; const int M = N * N << 1; const int INF = 1e9; int n,tot,head[N],nxt[M],to[M],cost[M],fa[N]; struct Data{ int u,v,val; inline Data() {} inline Data(int a, int b, int c):u(a),v(b),val(c) {} inline bool operator < (const Data &B) const { return val > B.val; } }p[N*N*N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void AddEdge(int u, int v, int c) { static int E = 1; cost[E+1] = cost[E+2] = c; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } int cal(int w, int f, int pur, int mn) { if (w == pur) return mn; for (int i=head[w],tmp;i;i=nxt[i]) { if (to[i] != f) { tmp = cal(to[i], w, pur, min(mn, cost[i])); if (~tmp) return tmp; } } return -1; } int find(int x) {return x==fa[x]? x: fa[x]=find(fa[x]);} int main() { n = read(); for (int i=1,v;i<=n;i++) { fa[i] = i; for (int j=1;j<=n;j++) { if (v=read(), i==j) continue; p[++tot] = Data(i, j, v); } } sort(p+1, p+1+tot); for (int i=1;i<=tot;i++) { int u=p[i].u, v=p[i].v, val=p[i].val; if (find(u) == find(v)) {if(cal(u,u,v,INF)!=val)cout<<-1,exit(0);} else fa[find(u)] = fa[v], AddEdge(u, v, val); } cout<<n-1<<endl; for (int i=2;to[i];i+=2) printf("%d %d %d\n",to[i],to[i+1],cost[i]); return 0; }