5-13 畅通工程之最低成本建设问题 (30分)（这个是补上去的7月5号）_综合

5-13 畅通工程之最低成本建设问题 (30分)

某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。

输入格式:

输入的第一行给出城镇数目 $N$ ( $\le 1000$ )和候选道路数目 $M\le 3N$ ；随后的 $M$ 行，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号（从1编号到 $N$ ）以及该道路改建的预算成本。

输出格式:

输出畅通工程需要的最低成本。如果输入数据不足以保证畅通，则输出“Impossible”。

输入样例1:

输出样例1:

输入样例2:

输出样例2:

Impossible

时间限制：400ms
内存限制：64MB
代码长度限制：16kB
判题程序：系统默认
作者：DS课程组
单位：浙江大学

题目判定

这个题就是用的是最小生成树的思想，，，

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define M 0x3f3f3f
using namespace std;

int book[10020];

int b[10002];

struct node
{
int x;
int y;
int z;
}a[1002];

bool cmp(node a,node b)
{
return a.z < b.z;
}

int find(int r)
{
while(r != b[r])
r = b[r];
return r;
}

int meger(int n,int m)
{
int fx = find(n);
int fy = find(m);
if(fx != fy)
{
b[fx] = fy;
return 1;
}
return 0;
}

int main()
{
int n,m,i,j;
scanf("%d %d",&n,&m);
for(i = 0;i < m; i++)
{
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);
}
for(i = 1;i <= n; i++)
{
b[i] = i;
}
sort(a,a+m,cmp);
int sum = 0,su = 0;
for(i = 0;i < m; i++)
{
if(meger(a[i].x,a[i].y) == 1)
{
sum = sum+a[i].z;
su++;
}
if(su == n-1)
break;
}
if(su != n-1)
printf("Impossible\n");
else
printf("%d\n",sum);
}

代码菜鸟，如有错误，请多包涵！！