【日常小测】cut

题目大意

给定一个$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;
}