最小生成树
最小生成树
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz。
输入输出格式
输入描述:
第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。 接下来 M 行每行包含三个整数 Xi,Yi,Zi ，表示有一条长度为 Zi 的无向边连接结点 Xi,Yi 1≤N≤5000，1≤M≤2×10^5
输出描述:
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入样例#:
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
输出样例#:
复制
7
题目来源
中山大学机试题
#include<bits/stdc++.h> using namespace std; struct edge{ int x, y, z; }; edge s[200005]; int fa[50005]; int cmp(edge s1, edge s2){ return s1.z < s2.z; } int find(int x){ if(fa[x] == x){ return x; } else{ fa[x] = find(fa[x]); return fa[x]; } } int main(){ int n, m; while(cin>>n>>m){ for(int i = 1; i <= n; i ++){//初始化 fa[i] = i; } for(int i = 0; i < m ; i ++){ cin>>s[i].x>>s[i].y>>s[i].z; } // sort(s.begin(), s.end(), cmp); sort(s, s + m, cmp); int num = 0;//边 int sum = 0;//钱 for(int i = 0; i < m ; i ++){ int x = s[i].x; int y = s[i].y; if(find(x) != find(y)){//不联通 int rootx = find(x); int rooty = find(y); fa[rootx] = rooty; sum += s[i].z;//再加钱 num ++; // cout<<sum<<" "<<num<<endl; } if(num == n - 1){//边数够了 break; } } if(num == n - 1){//联通？ cout<<sum<<endl; } else{ cout<<"orz"<<endl; } } }畅通工程
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
输入输出格式
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
输出描述:
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
输入输出样例
输入样例#:
复制
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
输出样例#:
复制
3 ?
题目来源
浙江大学机试题
#include<bits/stdc++.h> using namespace std; struct edge{ int x, y, z; }; edge s[1005]; int fa[1005]; int find(int x){ if(fa[x] == x){ return x; } else{ fa[x] = find(fa[x]); return fa[x]; } } void join(int x, int y){ int rootx = find(x); int rooty = find(y); if(rootx == rooty){ return; } else{ fa[rootx] = rooty; return; } } int cmp(edge s1, edge s2){ return s1.z < s2.z; } int main(){ int m, n; while(cin>>n>>m){ if(n == 0){ break; } for(int i = 1; i <= m; i ++){ fa[i] = i; } for(int i = 0; i < n; i ++){ cin>>s[i].x>>s[i].y>>s[i].z; } sort(s, s + n, cmp); int money = 0, count = 0; for(int i = 0; i < n; i ++){ int x = s[i].x; int y = s[i].y; int rootx = find(x); int rooty = find(y); if(rootx != rooty){//没连通 fa[rootx] = rooty; money += s[i].z; count++; // cout<<count<<endl; if(count == m - 1){ break; } } } if(count == m - 1){ cout<<money<<endl; } else{ cout<<"?"<<endl; } }// }连通图
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
给定一个无向图和其中的所有边，判断这个图是否所有顶点都是连通的。
输入输出格式
输入描述:
每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。
输出描述:
对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。
输入输出样例
输入样例#:
复制
4 3 1 2 2 3 3 2 3 2 1 2 2 3
输出样例#:
复制
NO YES
题目来源
吉林大学机试题
#include<bits/stdc++.h> using namespace std; int fa[10005]; int find(int x){ if(fa[x] == x){ return x; } else{ fa[x] = find(fa[x]); return fa[x]; } } void join(int x, int y){ int rootx = find(x); int rooty = find(y); if(rootx == rooty){ return; } else{ fa[rootx] = rooty; return; } } int main(){ int m, n; while(cin>>n>>m){ for(int i = 1; i <= n; i ++){ fa[i] = i; } int x, y; for(int i = 0; i < m; i ++){ cin>>x>>y; join(x, y); } int root = find(1); int temp = 1; for(int i = 2; i <= n; i ++){ // cout<<find(i)<<endl; if(find(i) != root){ temp = 0; break; } } if(temp == 1){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } }