您的位置: 首页  >  IT文章  >  畅通工程,继续畅通工程，畅通工程再续，多种解法 继续畅通工程 畅通工程 畅通工程再续 畅通工程 还是畅通工程

畅通工程,继续畅通工程，畅通工程再续，多种解法 继续畅通工程 畅通工程 畅通工程再续 畅通工程 还是畅通工程

分类: IT文章 • 2022-05-09 21:34:44

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 17822    Accepted Submission(s): 7672


Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。
 

 

Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。
 

 

Output
每个测试用例的输出占一行，输出全省畅通需要的最低成本。
 

 

Sample Input
3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0
 

 

Sample Output
3 1 0

题解：

方法一：克鲁斯卡尔算法；

代码：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 const int MAXN=110;
 5 int sum;
 6 struct Node {
 7     int s,e,d,ol;
 8 };
 9     Node dt[MAXN*MAXN/2];
10     int pre[MAXN];
11 void initial(){
12     memset(pre,0,sizeof(pre));
13     memset(dt,0,sizeof(dt));
14 }
15 int find(int x){
16     return pre[x]= x==pre[x]?x:find(pre[x]);
17 }
18 int cmp(const void *a,const void *b){
19     if( (*(Node *)a).ol != (*(Node *)b).ol)return (*(Node *)b).ol-(*(Node *)a).ol;
20     else return (*(Node *)a).d-(*(Node *)b).d;
21 }
22 void merge(Node a){
23     int f1,f2;
24     if(!pre[a.s])pre[a.s]=a.s;
25     if(!pre[a.e])pre[a.e]=a.e;
26         f1=find(a.s);
27         f2=find(a.e);
28 if(f1!=f2){
29     pre[f1]=f2;
30     if(!a.ol)sum+=a.d;
31 }
32 }
33 int main(){
34     int N,t;
35     while(~scanf("%d",&N),N){
36             initial();sum=0;
37             t= N*(N-1)/2;
38         int i,j;
39             for(i=0;i<t;i++)
40             scanf("%d%d%d%d",&dt[i].s,&dt[i].e,&dt[i].d,&dt[i].ol);
41         qsort(dt,t,sizeof(dt[0]),cmp);
42         for(int i=0;i<t;i++){
43             merge(dt[i]);
44         }
45             printf("%d
",sum);
46     }
47     return 0;
48 }

方法二：prime：

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int INF=0x3f3f3f3f;
 4 const int MAXN=110;
 5 int vis[MAXN],map[MAXN][MAXN],low[MAXN];
 6 int N;
 7 void prime(){
 8     memset(vis,0,sizeof(vis));
 9     for(int i=1;i<=N;i++)low[i]=map[1][i];
10     vis[1]=1;
11     int k,temp,min=0;
12     for(int i=1;i<=N;i++){
13             temp=INF;
14         for(int j=1;j<=N;j++)
15         if(!vis[j]&&temp>low[j])temp=low[k=j];
16 
17         if(temp==INF){
18             printf("%d
",min);
19             break;
20         }
21         min+=temp;
22         vis[k]=1;
23         for(int j=1;j<=N;j++){
24             if(!vis[j]&&low[j]>map[k][j])low[j]=map[k][j];
25         }
26     }
27 }
28 int main(){int a,b,c,d,M;
29         while(~scanf("%d",&N),N){
30                 M=N*(N-1)/2;
31                 memset(map,INF,sizeof(map));
32                 //printf("%d %d
",M,N);
33                // for(int i=0;i<10;i++)for(int j=0;j<10;j++)printf("%d ",map[i][j]);
34         while(M--){
35             scanf("%d%d%d%d",&a,&b,&c,&d);
36             if(d)map[a][b]=map[b][a]=0;
37             else if(c<map[a][b])map[a][b]=map[b][a]=c;
38             }
39             prime();
40         }
41 return 0;
42 }
欢迎参加——每周六晚的BestCoder（有米！）

畅通工程

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 21373    Accepted Submission(s): 9196
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
 
Input
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
 
Output
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
 
Sample Input
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
 
Sample Output
3 ?
 

题解：

方法一：克鲁斯卡尔算法；

代码：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 struct Node {
 5 int s,e,dis;
 6 };
 7 Node road[110];
 8 int pre[110];
 9 int N,M;
10 int cmp(const void *a,const void *b){
11     return *(int *)a-*(int *)b;
12 }
13 int find(int x){
14 return x==pre[x]?x:find(pre[x]);
15 }
16 bool merge(int x,int y){
17 int f1,f2;
18 f1=find(x);f2=find(y);
19 if(f1!=f2){
20     pre[f1]=f2;return true;
21 }
22 return false;
23 }
24 void initial(){memset(pre,0,sizeof(pre));}
25 int main(){
26     while(~scanf("%d%d",&N,&M),N){
27         for(int i=0;i<N;i++)scanf("%d%d%d",&road[i].s,&road[i].e,&road[i].dis);
28         qsort(road,N,sizeof(road[0]),cmp);
29         int num=0;
30         initial();
31         for(int i=0;i<N;i++){
32             if(!pre[road[i].s])pre[road[i].s]=road[i].s;
33             if(!pre[road[i].e])pre[road[i].e]=road[i].e;
34             if(merge(road[i].s,road[i].e))num+=road[i].dis;
35         }int flot=0;
36         for(int i=1;i<=M;i++){
37             if(!pre[i]||i==pre[i])flot++;
38             if(flot>1)break;
39         }
40         if(flot>1)puts("?");
41         else printf("%d
",num);
42     }
43 return 0;}

方法二：prime算法： 

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int INF=0x3f3f3f3f;
 4 const int MAXN=110;
 5 int map[MAXN][MAXN],vis[MAXN],low[MAXN];
 6 int N,M,min;
 7 void prime(){
 8     memset(vis,0,sizeof(vis));//记得初始化
 9     int flot=1,k;
10     for(int i=1;i<=M;i++)
11         low[i]=map[1][i];//初始化low数组，刚开始已选集合{1}与此集合相连的权值为集合low
12     vis[1]=1;//1在集合中visit【1】=1；
13     for(int i=1;i<=M;i++){
14             int temp=INF;//记得初始化；
15         for(int j=1;j<=M;j++){//找最小权值；
16             if(!vis[j]&&temp>low[j]){
17                 temp=low[k=j];
18             }
19         }
20         if(temp==INF){//找不到就判断；
21             if(flot!=M)puts("?");
22             else printf("%d
",min);
23             break;
24         }
25                 min+=temp;
26                 flot++;//代表当前已选集合中的元素个数；
27                 vis[k]=1;
28                 for(int i=1;i<=M;i++){//更新low数组；使其与已选数组相连的权值小；
29                     if(!vis[i]&&low[i]>map[k][i])
30                         low[i]=map[k][i];
31                 }
32         }
33 }
34 int main(){
35     int a,b,d;
36     while(~scanf("%d%d",&N,&M),N){
37             min=0;//刚开始min忘初始化了。。。
38             memset(map,INF,sizeof(map));//INF初始化为0xfffffff就不行，都是-1了
39         //for(int i=0;i<10;i++)for(int j=0;j<10;j++)printf("%d ",map[i][j]);
40        for(int i=0;i<N;i++){
41             scanf("%d%d%d",&a,&b,&d);
42             if(d<map[a][b])//此处不能少。。。
43             map[a][b]=map[b][a]=d;
44         }
45         prime();
46     }
47 return 0;
48 }

畅通工程再续

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 46   Accepted Submission(s) : 20
Problem Description
相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
 
Input
输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。
 
Output
每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.
 
Sample Input
2 2 10 10 20 20 3 1 1 2 2 1000 1000
 
Sample Output
1414.2 oh!
题解：qsort写错了，wa了无数次；也可以设个变量num=1;每加进一个点或者一个树时就num++最后与n比较，相等则连通；
代码一：克鲁斯卡尔
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 #include<string.h>
 5 double distant(int ax,int ay,int bx,int by){
 6     int x=bx-ax,y=by-ay;
 7     double s;
 8     s=x*x+y*y;
 9     s=sqrt(s);
10     return s;
11 }
12 int pre[110];
13 struct Node{
14         int s,e;
15         double d;
16 };
17 Node die[10010];
18 int find(int x){
19     return pre[x]= x==pre[x]?x:find(pre[x]);
20 }
21 double minmoney;
22 int cmp(const void *a,const void *b){
23     if((*(Node *)a).d<(*(Node *)b).d)return -1;
24     else return 1;
25 }
26 void merge(Node a){
27     if(pre[a.s]==-1)pre[a.s]=a.s;
28     if(pre[a.e]==-1)pre[a.e]=a.e;
29     int f1=find(a.s),f2=find(a.e);
30     if(f1!=f2){
31         pre[f1]=f2;
32         minmoney+=a.d;
33     }
34 }
35 void initial(){
36     memset(pre,-1,sizeof(pre));
37     memset(die,0,sizeof(die));
38 }
39 int nx[110],ny[110];
40 int main(){
41         int T,C;
42         scanf("%d",&T);
43         while(T--){minmoney=0;
44         initial();
45        // for(int i=0;i<110;i++)printf("%d",pre[i]);
46             scanf("%d",&C);
47             for(int i=0;i<C;i++){
48                 scanf("%d%d",&nx[i],&ny[i]);
49             }
50             int k=0;
51             for(int i=0;i<C;i++){
52                 for(int j=i+1;j<C;j++){
53                     double dis=distant(nx[i],ny[i],nx[j],ny[j]);
54                     //printf("%lf  ",dis);
55                 if(dis>=10&&dis<=1000){
56                     die[k].s=i;die[k].e=j;
57                     die[k].d=dis;
58                     k++;
59                     }
60                 }
61             }
62             //printf("%d
",k);
63             qsort(die,k,sizeof(die[0]),cmp);
64             for(int i=0;i<k;i++){
65                 merge(die[i]);
66             }
67             int flot=0;
68             for(int i=0;i<C;i++){
69                 if(pre[i]==i||pre[i]==-1)flot++;
70                 //if(flot>1)break;
71             }
72             //printf("%d
",flot);
73             if(flot>1) puts("oh!");
74             else printf("%.1lf
",minmoney*100);
75         }
76     return 0;
77     }

 代码二：

无语，又错了好久，然后发现初始化map出错，对于double数组不能像int那样初始化；

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 const int INF=0x3f3f3f3f;
 5 const int MAXN=110;
 6 int N,vis[MAXN];
 7 double map[MAXN][MAXN],low[MAXN];
 8 double fd(int ax,int ay,int bx,int by){
 9     int x=bx-ax;
10     int y=by-ay;
11     int s=x*x+y*y;
12     return sqrt(s);
13 }
14 void prime(){
15     int flot=1,k;
16     double min=0,temp;
17     memset(vis,0,sizeof(vis));
18     vis[0]=1;
19     for(int i=0;i<N;i++)
20     {low[i]=map[0][i];}
21     //printf("low  %lf 
",low[i]);}
22     for(int i=0;i<N;i++){
23             temp=INF;
24         for(int j=0;j<N;j++){
25             if(!vis[j]&&low[j]<temp)
26                 temp=low[k=j];
27         }
28         // printf("***%d   %lf  ",temp,min);
29         if(temp==INF){
30             if(flot==N)printf("%.1lf
",min*100);
31             else puts("oh!");
32             break;
33         }
34         min+=temp;
35         flot++;
36         vis[k]=1;
37         for(int j=0;j<N;j++){
38             if(!vis[j]&&low[j]>map[k][j])
39                 low[j]=map[k][j];
40         }
41     }
42 }
43 int main(){
44         int T;
45         int dx[MAXN],dy[MAXN];
46         scanf("%d",&T);
47             while(T--){
48                 for(int i=0;i<MAXN;i++)
49                     for(int j=0;j<MAXN;j++)
50                     map[i][j]=INF;
51                 scanf("%d",&N);
52                 for(int i=0;i<N;i++)
53                     scanf("%d%d",&dx[i],&dy[i]);
54                 for(int i=0;i<N;i++)
55                 for(int j=i+1;j<N;j++){
56                     double dis=fd(dx[i],dy[i],dx[j],dy[j]);
57                     //printf("### %d  %d %lf  ",i,j,dis);
58                     if(dis<map[i][j]&&dis>=10&&dis<=1000)
59                         map[i][j]=map[j][i]=dis;
60                 }
61                 /*for(int i = 0; i < N; ++i)
62                     printf("%lf
", map[0][i]);*/
63                 prime();
64             }
65     return 0;
66 }

畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 44528    Accepted Submission(s): 23601

Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ 
 
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。  注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的 当N为0时，输入结束，该用例不被处理。 
 
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。 
 
Sample Input
4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0
 
Sample Output
1 0 2 998
Hint
Hint
Huge input, scanf is recommended.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define mem(x, y) memset(x, y, sizeof(x))
const int MAXN = 1010;
int pre[MAXN];
void init(){
    mem(pre, -1);
}
int find(int x){
    return pre[x] = pre[x] == x?x:find(pre[x]);
}
void merge(){
    int x, y;
    scanf("%d%d", &x, &y);
    if(pre[x] == -1)pre[x] = x;
    if(pre[y] == -1)pre[y] = y;
    int f1 = find(x), f2 = find(y);
//    printf("%d %d
", f1, f2);
    if(f1 != f2)
        pre[f1] = f2;
}
int work(){
    int n, m;
    init();
    scanf("%d", &n);
    if(!n)exit(0);
    scanf("%d", &m);
    while(m--){
        merge();
    }
    int cnt = 0;
//    cout << n << endl;
    for(int i = 1; i <= n; i++){
        if(pre[i] == -1 || pre[i] == i)
            cnt++;
    //    cout << pre[i] << endl;
    }
    return cnt - 1;
}
int main(){
    while(1){
        printf("%d
", work());
    }
    return 0;
}

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 38162    Accepted Submission(s): 17236

Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
 
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。
 
Output
对每个测试用例，在1行里输出最小的公路总长度。
 
Sample Input
3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0
 
Sample Output
3 5
Hint
Hint
Huge input, scanf is recommended.
 
Source
浙大计算机研究生复试上机考试-2006年
 
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define mem(x, y) memset(x, y, sizeof(x))
const int MAXN = 10010;
const int INF = 0x3f3f3f3f;
struct Edge{
    int from, to, next, value;
    void init(int x, int y, int z, int d){
        from = x;
        to = y;
        next = z;
        value = d;
    }
};
Edge edg[MAXN << 1];
int head[MAXN << 1];
int edgnum;
int vis[MAXN];
int d[MAXN];
int N;
void init(){
    mem(head, -1);
    edgnum = 0;
}
void add(int a, int b, int c){
    Edge E;
    E.init(a, b, head[a], c);
    edg[edgnum] = E;
    head[a] = edgnum++;
}
int prim(){
    mem(d, INF);
    mem(vis, 0);
    vis[1] = 1;
    int ans = 0, cnt = 0;
    for(int i = head[1]; i != -1; i = edg[i].next)
        d[edg[i].to] = min(d[edg[i].to], edg[i].value);
    while(true){
        int k = -1;
        for(int i = 1; i <= N; i++){
            if(!vis[i] && (k == -1 || d[i] < d[k]))
                k = i;
        }
        if(k == -1)break;
        ans += d[k];
        vis[k] = 1;
        for(int i = head[k]; i != -1; i = edg[i].next){
            d[edg[i].to] = min(d[edg[i].to], edg[i].value);
        }
    }
    return ans;
}
int main(){
    int a, b, c;
    while(~scanf("%d", &N), N){
        init();
        for(int i = 0; i < N * (N - 1)/2; i++){
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }
        printf("%d
", prim());
    }
    return 0;
}

相关推荐