思路：我也不知道叫什么树，但是构造过程能理解。
我们可以将先将边按降序排序，那么就用kruskaer构造生成树。构造好的生成树也就是满足条件的图，因为点i，j的最大流量就是生成树上点i到点j的路径上的最小权值边。
但如果存在f[i][j]<min(f[i][k],f[k][j])，那么这图就是不存在的。
#include<set> #include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pb push_back #define mp make_pair #define Maxn 110 #define Maxm 200010 #define LL __int64 #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 100000 #define lowbit(x) (x&(-x)) #define clr(x,y) memset(x,y,sizeof(x)) #define Mod 1000000007 using namespace std; int f[Maxn][Maxn],ans[Maxn][Maxn],fa[Maxn],n; struct Edge{ int u,v,val; int operator <(const Edge &temp) const{ return val>temp.val; } }p[Maxn*Maxn]; int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; } bool merg(int a,int b) { int x=find(a); int y=find(b); if(x==y) return false; fa[x]=y; return true; } bool OK() { int i,j,k; for(k=1;k<=n;k++){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(i==j||j==k||i==k) continue; if(f[i][j]<min(f[i][k],f[k][j])) return false; } } } return true; } int main() { int i,j,cnt; while(scanf("%d",&n)!=EOF){ clr(ans,0); cnt=0; for(i=1;i<=n;i++){ ans[i][i]=-1; fa[i]=i; for(j=1;j<=n;j++){ scanf("%d",&p[++cnt].val); f[i][j]=p[cnt].val; p[cnt].u=i,p[cnt].v=j; } } if(!OK()){ printf("NO "); continue; } printf("YES "); sort(p+1,p+cnt+1); for(i=1;i<=cnt;i++){ if(merg(p[i].u,p[i].v)) ans[p[i].u][p[i].v]=ans[p[i].v][p[i].u]=p[i].val; } for(i=1;i<=n;i++){ printf("%d",ans[i][1]); for(j=2;j<=n;j++){ printf(" %d",ans[i][j]); } printf(" "); } } return 0; }