https://ac.nowcoder.com/acm/contest/3007/I

题中给定的图必定是一棵树    

容易发现,如果将输入的N(N-1)个距离看做N(N-1)条无向边的话,那么如果数据合法,原树就是这张新图的最小生成树。
证明:由于边权是非负的,可以考虑Kruskal算法的过程,每一次引入的边都是尽可能短的,所以一定是树中的边,通过简单的归纳即证。
 
 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
int n,m,s,cnt;
struct edge{
int from,to,w;
bool operator < (const edge &b) const{
return w < b.w;
}
}e[maxn*maxn];
struct node{
int u,v,w;
bool operator < (const node &b) const{
return w<b.w;
}
};
struct Node{
vector<int> v;
vector<int> w;
}g[maxn];
int fa[maxn],dis[maxn][maxn];
vector<node> ans;
int get(int x){
if(x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
void merge(int x,int y){
int u = get(x),v = get(y);
if(u == v) return;
fa[u] = v;
}
void kruskal(){
sort(e+,e++m);
for(int i = ;i<=n;i++) fa[i] = i;
for(int i = ;i<=m;i++){
int x = get(e[i].from );
int y = get(e[i].to );
if(x == y) continue;
merge(x,y);
ans.push_back({e[i].from,e[i].to,e[i].w});
}
}
void addedge(int x,int y,int c){
e[cnt].from = x,e[cnt].to = y,e[cnt].w = c;
cnt++;
}
int vis[maxn],siz[maxn];
void dfs(int cur,int pos){//只需求出一个点到各个点的最小距离即可进行判断
vis[cur] = ;
siz[cur] = pos;
for(int i = ;i<g[cur].v.size();i++){
int v = g[cur].v[i];
if(!vis[v]) dfs(v,pos+g[cur].w[i]);
}
}
int main(){
cin>>n;
m = n*(n-),cnt = ;;
for(int i = ;i<=n;i++){
for(int j = ;j<=n;j++){
cin>>dis[i][j];
if(i == j) continue;
addedge(i,j,dis[i][j]);
}
}
kruskal();
for(int i = ;i<ans.size();i++){//建一个新图
node t = ans[i];
g[t.u].v.push_back(t.v);
g[t.v].v.push_back(t.u);
g[t.u].w.push_back(t.w);
g[t.v].w.push_back(t.w);
}
for(int i = ;i<=n;i++){
if(g[i].v.size() == ) {
s = i;break;
}
}
dfs(s,);
for(int i = ;i<=n;i++){
if(siz[i]!=dis[s][i]){
cout<<"No";return ;
}
}
sort(ans.begin(),ans.end());
cout<<"Yes"<<endl;
for(int i = ;i<ans.size();i++){
cout<<ans[i].w<<endl;
}
return ;
}

最新文章

  1. 创建Windows Azure内部负载均衡器
  2. .net mvc web api 返回 json 内容,过滤值为null的属性
  3. Java基础之扩展GUI——使用对话框创建文本元素(Sketcher 4 creating text elements)
  4. hosts代理
  5. Java开发 Eclipse使用技巧(转)
  6. 软件工程随堂小作业—— 寻找“水王”(C++)
  7. Chapter10:泛型算法
  8. C++经典面试题
  9. 加载jar文件输出class和method
  10. C#反射(一) 【转】
  11. IQ调制、整形滤波器与星座映射
  12. Unity5权威讲解
  13. 理解Twisted与非阻塞编程
  14. PHP环境搭建(20161014)
  15. 01_Struts2概述及环境搭建
  16. 通过 Azure Pipelines 实现持续集成之docker容器化及自动化部署
  17. SuperSocket 案例
  18. sqoop 使用
  19. CentOS 7 命令行安装TeamViewer
  20. MT【234】正方形染色(二)

热门文章

  1. fastJson&amp;edis
  2. winForm学习 2019年4月11日
  3. IIS6的文件解析漏洞
  4. Java学习之String、StringBuffer、StringBuilder
  5. vue_day01
  6. es5和es6中如何处理不确定参数
  7. [MongoDB]MongoDB的ObjectId组成
  8. linux--工具参考篇
  9. 纪中21日c组T2 2117. 【2016-12-30普及组模拟】台风
  10. 用记事本编辑HTML文件后保存代码全堆在一起了,记事本打开html文件格式乱了