题目大意
给定一个$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;
}
Hmm is anyone else encountering problems with the
pictures on this blog loading? I’m trying to find out if
its a problem on my end or if it’s the blog. Any responses
would be greatly appreciated.
I could not resist commenting. Very well written!
Thanks in favor of sharing such a fastidious thought, article is fastidious, thats why i have read it fully
I’m really enjoying the design and layout of
your website. It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit more often. Did you
hire out a developer to create your theme? Excellent work!
First of all I want to say excellent blog! I had a quick question which I’d like to ask if you
do not mind. I was interested to know how you center yourself
and clear your head before writing. I’ve had trouble clearing my thoughts
in getting my thoughts out there. I truly do take pleasure
in writing however it just seems like the first 10 to 15 minutes tend to be lost just trying to figure out how to begin.
Any suggestions or hints? Thanks!
You ought to take part in a contest for one of the greatest sites on the web.
I’m going to highly recommend this website!
I am regular reader, how are you everybody? This piece of writing posted at
this web page is genuinely pleasant.
Greetings! Very useful advice within this post!
It’s the little changes which will make the most important
changes. Thanks for sharing!
fantastic submit, very informative. I ponder why the other specialists of this sector don’t
understand this. You should continue your writing.
I’m sure, you have a great readers’ base already!
you’re actually a excellent webmaster. The site loading speed is incredible.
It kind of feels that you’re doing any unique
trick. In addition, The contents are masterwork. you have done a magnificent
process in this subject!
I’m not that much of a internet reader to be honest but your blogs really nice, keep it up! I’ll go ahead and bookmark your site to come back in the future. Cheers
It’s difficult to find knowledgeable people in this particular subject, but you seem like you know
what you’re talking about! Thanks
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! However,
how could we communicate?
I get pleasure from, result in I found exactly what
I was having a look for. You’ve ended my 4 day lengthy hunt!
God Bless you man. Have a great day. Bye
I do agree with all of the ideas you’ve offered to your post.
They are really convincing and can certainly work. Nonetheless,
the posts are too quick for newbies. May you please extend them
a little from next time? Thank you for the post.
What’s up, I read your blogs daily. Your humoristic style is witty, keep doing
what you’re doing!
Very rapidly this web page will be famous among all blogging users, due to it’s fastidious posts
Nice post. I learn something totally new and challenging on sites I stumbleupon every day.
It’s always helpful to read through content
from other writers and practice a little something from their websites.
Pretty! This has been an incredibly wonderful post.
Many thanks for providing these details.
Hello! Someone in my Facebook group shared this
website with us so I came to take a look. I’m definitely enjoying the information. I’m book-marking
and will be tweeting this to my followers! Outstanding blog and brilliant design and style.
hi!,I really like your writing very a lot! percentage we be in contact more about your post on AOL? I need a specialist on this area to unravel my problem. Maybe that is you! Having a look forward to look you.