最小生成树

最小生成树查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb如题给出一个无向图求出最小生成树如果该图不连通则输出orz。输入输出格式输入描述:第一行包含两个整数 N,M表示该图共有 N 个结点和 M 条无向边。 接下来 M 行每行包含三个整数 Xi,Yi,Zi 表示有一条长度为 Zi 的无向边连接结点 Xi,Yi 1≤N≤50001≤M≤2×10^5输出描述:如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。输入输出样例输入样例#:复制4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3输出样例#:复制7题目来源中山大学机试题#includebits/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(cinnm){ for(int i 1; i n; i ){//初始化 fa[i] i; } for(int i 0; i m ; i ){ cins[i].xs[i].ys[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 ; // coutsum numendl; } if(num n - 1){//边数够了 break; } } if(num n - 1){//联通 coutsumendl; } else{ coutorzendl; } } }畅通工程查看题解 查看答案题目描述Time Limit: 1000 msMemory 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 ?题目来源浙江大学机试题#includebits/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(cinnm){ if(n 0){ break; } for(int i 1; i m; i ){ fa[i] i; } for(int i 0; i n; i ){ cins[i].xs[i].ys[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; // coutcountendl; if(count m - 1){ break; } } } if(count m - 1){ coutmoneyendl; } else{ cout?endl; } }// }连通图查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb给定一个无向图和其中的所有边判断这个图是否所有顶点都是连通的。输入输出格式输入描述:每组数据的第一行是两个整数 n 和 m0n1000。n 表示图的顶点数目m 表示图中边的数目。随后有 m 行数据每行有两个值 x 和 y0x, y n表示顶点 x 和 y 相连顶点的编号从 1 开始计算。输入不保证这些边是否重复。输出描述:对于每组输入数据如果所有顶点都是连通的输出YES否则输出NO。输入输出样例输入样例#:复制4 3 1 2 2 3 3 2 3 2 1 2 2 3输出样例#:复制NO YES题目来源吉林大学机试题#includebits/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(cinnm){ for(int i 1; i n; i ){ fa[i] i; } int x, y; for(int i 0; i m; i ){ cinxy; join(x, y); } int root find(1); int temp 1; for(int i 2; i n; i ){ // coutfind(i)endl; if(find(i) ! root){ temp 0; break; } } if(temp 1){ coutYESendl; } else{ coutNOendl; } } }