当前位置：首页 > news >正文

畅通工程

news 来源：原创 2024/5/4 18:32:51

题目描述：

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

输入：

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

输出：

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

样例输入：

样例输出：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <cctype>
  6 #include <cstring>
  7 
  8 #include <vector>
  9 #include <deque>
 10 #include <list>
 11 #include <map>
 12 #include <set>
 13 #include <stack>
 14 #include <queue>
 15 #include <algorithm>
 16 #include <string>
 17 
 18 
 19 #define MAXD 99999999
 20 using namespace std;
 21 
 22 
 23 
 24 int g[1000+1][1000+1];
 25 
 26 
 27 int lowcost[1000+1];
 28 
 29 int vis[1000+1];
 30 
 31 
 32 
 33 
 34 
 35 
 36 int main()
 37 {
 38 
 39     int n,m;
 40     int i,j,k;
 41 
 42     while(scanf("%d",&n)!=EOF)
 43     {
 44 
 45         if(n==0)
 46             break;
 47 
 48         for(i=1;i<=n;i++)
 49             for(j=1;j<=n;j++)
 50             {g[i][j]=1;}
 51 
 52 
 53         scanf("%d",&m);
 54 
 55         for(i=0;i<m;i++)
 56         {
 57             int a,b;
 58 
 59             scanf("%d%d",&a,&b);
 60 
 61             g[a][b]=g[b][a]=0;
 62         }
 63 
 64 
 65         for(i=1;i<=n;i++)
 66         {
 67             vis[i]=0;
 68 
 69             lowcost[i]=g[1][i];
 70         }
 71 
 72         vis[1]=1;
 73 
 74         int mincost=0;
 75 
 76         for(i=1;i<n;i++)
 77         {
 78             int temp=MAXD;
 79 
 80             k=-1;
 81 
 82             for(j=1;j<=n;j++)
 83             {
 84                 if(vis[j]==0)
 85                 {
 86                     if(lowcost[j]<temp)
 87                     {
 88                         k=j;temp=lowcost[j];
 89                     }
 90                 }
 91             }
 92 
 93             vis[k]=1;
 94 
 95             mincost+=temp;
 96 
 97 
 98             for(j=1;j<=n;j++)
 99             {
100                 if(vis[j]==0)
101                 {
102                     if(lowcost[j]>g[k][j])
103                     {
104                         lowcost[j]=g[k][j];
105                     }
106                 }
107             }
108         }
109 
110 
111         cout<<mincost<<endl;
112     }
113 
114 
115 
116     return 0;
117 }