湖北工程建设信息网站,丹阳网站建设开发,网站功能介绍是什么,怎么样找回网站密码P1038 -- 隧道 时间限制#xff1a;1000MS 内存限制#xff1a;65536KB Description 一座小镇正在着手建造自己的地铁线路网。小镇坐落在许多小岛上#xff0c;小岛之间通过隧道或者桥梁连接。地铁就在这些已有的桥梁和隧道的基础上建成。由于地铁主要是在地下#xf…P1038 -- 隧道 时间限制1000MS 内存限制65536KB Description 一座小镇正在着手建造自己的地铁线路网。小镇坐落在许多小岛上小岛之间通过隧道或者桥梁连接。地铁就在这些已有的桥梁和隧道的基础上建成。由于地铁主要是在地下所以桥梁用得越少越好。小镇的居民希望能够仅通过地铁就能在任意两座小岛之间往返旅行。幸运的是我们有足够多的隧道和桥梁来满足这个要求所以不需要建造新的隧道或桥梁。你的任务是计算需要构建这样一个地铁线路网最少需要用到几座桥梁。 Input Format 输入包括KM1行第一行包括三个数N(1≤N≤10000)K(1≤K≤12000)M(1≤M≤12000)。其中N为小岛数量K为隧道数量M为桥梁数量以下K行每行有两个数表示相应的隧道连接的小岛的编号再往下M行每行用同样的方式描述一座桥梁。 Output Format 输出仅包括一个数即最少需要用到的桥梁数。 Sample Input 6 3 4
1 2
2 3
4 5
1 3
3 4
4 6
5 6 Sample Output 2 【题解】 本题其实有很多地方是无用的 “幸运的是我们有足够多的隧道和桥梁来满足这个要求” 这句话保证了我们肯定能够将这些小岛联通。 那么我们只要并查集搞定隧道然后再找出有几个根即可搞定了根本不需要读入m和后面的桥梁。 代码如下 1 #includebits/stdc.h2 using namespace std;3 int pre[10010],r[10010];4 int findset(int x){5 int rx;6 while(pre[r]!r) rpre[r];7 int ix,j;8 while(i!r) {9 jpre[i];
10 pre[i]r;
11 ij;
12 }
13 return r;
14 }
15 int main() {
16 int n,k;
17 scanf(%d%d%*d,n,k);
18 for (int i1;in;i) pre[i]i;
19 while(k--) {
20 int a,b,f1,f2;
21 scanf(%d%d,a,b);
22 f1findset(a);
23 f2findset(b);
24 if(f1!f2) pre[f1]f2;
25 }
26 int cnt0;
27 for (int i1;in;i) if(pre[i]i) cnt;
28 printf(%d\n,cnt-1);
29 return 0;
30 } View Code 转载于:https://www.cnblogs.com/TonyNeal/p/fzyzoj1038.html
