修路问题

1248762042

畅通工程
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

Input
测试输入包含若干测试用例。每个测试用例的第1行给出一个正整数和一个非负整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。

Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。

输入示例
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
输出示例
1
0
2
998

jhq999

输入示例和题目不符，N在哪？M在哪？才明白原来是4个示例

jhq999

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. void roadoutput(int (*road)[3],int m,int n)
   
5. {
   
6.         int i=0,j=0,count=0;
   
7.         for (i = 1; i <= n; i++)//找出没通路的
   
8.         {
   
9.                 for (j = 0; j < m; j++)
   
10.                 {
    
11.                         if (i==road[j][0]||i==road[j][1])
    
12.                         {
    
13.                                 break;;
    
14.                         }
    
15.                 }
    
16.                 if (j==m)
    
17.                 {
    
18.                         count++;
    
19.                 }
    
20.         }
    
21.         for (i = 0; i < m; i++)//把互通的找出来算成一个孤立的城镇
    
22.         {
    
23.                 if (!road[i][2])
    
24.                 {
    
25.                         road[i][2]=1;
    
26.                         count++;
    
27. 
    
28.                         for (j = i+1; j < m; j++)
    
29.                         {
    
30.                                 if (!road[j][2])
    
31.                                 {
    
32.                                         if ((road[i][0]==road[j][0])||(road[i][1]==road[j][0])\
    
33.                                                 ||(road[i][0]==road[j][1])||(road[i][1]==road[j][1]))
    
34.                                         {
    
35.                                                 road[j][2]=1;
    
36.                                         }
    
37.                                 }
    
38.                         }
    
39.                 }
    
40.         }
    
41. 
    
42.         printf("%d\n",count-1);//孤立的城镇互通最少的路的条数是孤立的城镇数量-1
    
43.        
    
44. 
    
45. }
    
46. 
    
47. int main()
    
48. {
    
49. 
    
50.         int i=0,j=0,n=0,m=0;
    
51.         while (1)
    
52.         {
    
53.                 scanf("%d",&n);
    
54.                 if (!n)
    
55.                 {
    
56.                         break;
    
57.                 }
    
58.                 scanf("%d",&m);
    
59.                 int (*road)[3]=(int(*)[3])malloc(m*3*sizeof(int));
    
60.                 for (i = 0; i <m; i++)
    
61.                 {
    
62.                         scanf("%d %d",&road[i][0],&road[i][1]);
    
63.                         road[i][2]=0;
    
64.                         fflush(stdin);
    
65.                 }
    
66.                 roadoutput(road,m,n);
    
67.                 free(road);
    
68. 
    
69.         }
    
70.         return 0;
    
71. }

复制代码

1. 10 4
   
2. 1 2
   
3. 3 4
   
4. 5 6
   
5. 9 10
   
6. 5
   
7. 10 6
   
8. 1 2
   
9. 1 3
   
10. 2 3
    
11. 4 5
    
12. 8 9
    
13. 9 10
    
14. 4
    
15. 4 2
    
16. 1 3
    
17. 4 3
    
18. 1
    
19. 3 3
    
20. 1 2
    
21. 1 3
    
22. 2 3
    
23. 0
    
24. 5 2
    
25. 1 2
    
26. 3 5
    
27. 2
    
28. 999 0
    
29. 998
    
30. 0

复制代码

learner-ray

1. #include<stdio.h>
   
2. 
   
3. void RoadNum(void);        
   
4. 
   
5. int main(void)
   
6. {
   
7.         RoadNum();
   
8.        
   
9.         return 0;
   
10. }
    
11. 
    
12. void RoadNum(void)        //该函数用来实现修路问题，整体思想为n个城镇至少需要n-1条有效路径。m是现存的路径，需要判断里面是否有无效路径，比如同时存在1 2 2 1。
    
13. {
    
14.         int n, m;         // n为城镇数量，m 为现存路径。
    
15.         int count = 0; //用来统计m中的无效路径。
    
16.         int i, k;         //用来循环
    
17.         int j= 0;        //用来存储还需要几条路。
    
18.         int road[100]; // 将还需要几条路存储在road数组中。
    
19.        
    
20.         printf("请输入城镇和道路信息：\n");
    
21.         while (1)
    
22.         {
    
23.                 count = 0;        //辅助统计现有多少条路。
    
24.                 scanf("%d", &n);
    
25.                 if (n == 0) // 设置循环终止条件，输入0结束。
    
26.                 {
    
27.                         break;
    
28.                 }
    
29.                 scanf("%d", &m);
    
30.                
    
31.                 struct Exist         // 每一条路是两个城镇来表示，因此定义了一个结构体来表示。
    
32.                 {
    
33.                         int t1;
    
34.                         int t2;
    
35.                 };
    
36.                
    
37.                 struct Exist exi[m];         // 现存m条路因此定义了一个exi[m]的数组，来存放。
    
38.                
    
39.                 for (i = 0; i < m; i++)                //输入城镇和道路信息；
    
40.                 {
    
41.                         scanf("%d%d", &(exi[i].t1), &(exi[i].t2));
    
42.                         if (exi[i].t1 > n || exi[i].t2 > n) //假如5个城镇的话，用1，2，3，4，5来表示，输入的数字不能超过5，否则报错。
    
43.                         {
    
44.                                 printf("输入错误\n");
    
45.                                 return;
    
46.                         }
    
47.                 }
    
48.                
    
49.                 for (i = 0; i < m; i++) // 无效路径的判断。
    
50.                 {
    
51.                         for (k = i+1; k < m; k++)
    
52.                         {
    
53.                                 if ((exi[i].t1 == exi[k].t1 && exi[i].t2 == exi[k].t2) || (exi[i].t1 = exi[k].t2 && exi[i].t2 == exi[k].t1))
    
54.                                 {
    
55.                                         count++;
    
56.                                         break; //非常重要，防止重复计数。
    
57.                                 }
    
58.                         }
    
59.                 }
    
60.                
    
61.                 road[j++] = (n-1) - (m-count);         // n-1为需要的路径，m-count为现有的有效路径。
    
62.         }
    
63.        
    
64.         printf("输出结果\n");
    
65.        
    
66.         for (i = 0; i < j; i++)
    
67.         {
    
68.                 printf("%d\n", road[i]);
    
69.         }
    
70.        
    
71.         return;
    
72. }

复制代码

结果显示：
请输入城镇和道路信息：
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
输出结果
1
0
2
998

--------------------------------
Process exited after 11.71 seconds with return value 0
请按任意键继续. . .

1248762042

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. typedef struct ufset *UFset;
   
6. typedef struct ufset
   
7. {
   
8.         int *parent;
   
9.         int *root;
   
10. }UFS;
    
11. 
    
12. UFset UFinit(int size)
    
13. {
    
14.         UFset U = new ufset;
    
15.         U->parent = new int[size+1];
    
16.         U->root = new int[size+1];
    
17.         for (int e = 1; e <= size; e++)
    
18.         {
    
19.                 U->parent[e] = 1;
    
20.                 U->root[e] = 1;
    
21.         }
    
22.         return U;
    
23. }
    
24. 
    
25. int UFfind(int e, UFset U)
    
26. {
    
27.         int i, j = e;
    
28.         while ( !U->root[j] )
    
29.         {
    
30.                 j = U->parent[j];
    
31.         }
    
32.         while ( j != e )
    
33.         {
    
34.                 i = U->parent[e];
    
35.                 U->parent[e] = j;
    
36.                 e = i;
    
37.         }
    
38.         return j;
    
39. }
    
40. 
    
41. int UFunion(int i, int j, UFset U)
    
42. {
    
43.         if (i == j) return i;
    
44.         if (U->parent[i] < U->parent[j])
    
45.         {
    
46.                 U->parent[j] += U->parent[i];
    
47.                 U->root[i] = 0;
    
48.                 U->parent[i] = j;
    
49.                 return j;
    
50.         }
    
51.         else {
    
52.                 U->parent[i] += U->parent[j];
    
53.                 U->root[j] = 0;
    
54.                 U->parent[j] = i;
    
55.                 return i;
    
56.         }
    
57. }
    
58. 
    
59. void UFfree(UFset U)
    
60. {
    
61.         delete [] U->parent;
    
62.         delete [] U->root;
    
63.         delete U;
    
64. }
    
65. 
    
66. void uni(int x, int y, UFset uf)
    
67. {
    
68.         int a = UFfind(x, uf),
    
69.                 b = UFfind(y, uf);
    
70.         UFunion(a, b, uf);
    
71. }
    
72. 
    
73. int main()
    
74. {
    
75.         int N, M, index1, index2, count;
    
76.        
    
77.         UFset uf;
    
78.        
    
79.         while (true)
    
80.         {
    
81.                 count = 0;
    
82.                 cin >> N;
    
83.                 if ( N == 0 ) break;
    
84.                 cin >> M;
    
85.                
    
86.                 uf = UFinit(N);
    
87.                
    
88.                 for (int i = 0; i < M; i++)
    
89.                 {
    
90.                         cin >> index1 >> index2;
    
91.                         uni(index1, index2, uf);
    
92.                 }
    
93.                 for (int i = 1; i <= N; i++)
    
94.                 {
    
95.                         int j = UFfind(i, uf);
    
96.                         if ( i == j ) count++;
    
97.                 }
    
98.                 cout << count - 1 << endl;
    
99.                
    
100.                 UFfree(uf);
     
101.         }
     
102. }

复制代码

1248762042

1248762042 发表于 2021-11-16 12:22

我自己写出来了