题目链接:http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11464&courseid=132

题目:

修路
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB
 
Problem 11464 : No special judgement
Problem description
  在X国家,有n个城市,只有在城市才有加油站,现在国王决定修一些道路来使这n个城市链接起来,使得任意二个城市可以互相到达。由于经济危机,现在国王只有y元用来修路。由于只有在城市里才有加油站,所以当一条道路太长的时候,车辆由于油量不够,不同在这两个城市间互相到达。所以国王要求每条道路不能太长,即使得修的道路中最长的道路最短。现在问你最长的道路的长度。
Input
  包含多组数据,每组数据第一行为一个数n m 和y,表示n个城市和m条可以修的道路,y元的修路费2<=n<=10000 1<=m<=100000,1<=y<=100000。
接下来m行每行有四个整数u v c d 表示该道路链接城市u和v 修路的费用为c长度为d。
1<=u,v<=n   1<=d<=100000  1<=c<=10
Output
  对于每组数据,输出一个整数,表示修路中的最长的道路的长度,如果修的道路不能任意二个城市可以互相到达 则输出 -1。
Sample Input
3 2 10
1 2 2 1
1 3 2 5 3 3 10
1 2 5 2
2 1 6 1
1 3 5 1 3 2 100
1 2 1 1
1 2 2 2
Sample Output
5
2
-1

思路:题意为在满足费用y的情况下,将所有的城市连起来,并且使选择的所有道路中,最长的那一条最短,故可以枚举最长道路的长度,然后检验在这种长度内的道路能否符合国王的要求,找到一个最小值即为答案,其中枚举过程采用二分优化,检验过程用并查集,代码如下~。

代码如下:

 #include "stdio.h"
#include "string.h"
#include "stdlib.h" #define N 110000 struct node{
int x,y;
int dist,cost;
}a[N]; int cmp(const void *a,const void *b)
{
struct node *c = (node *)a;
struct node *d = (node *)b;
return c->cost - d->cost;
} int set[N]; int find(int x) //找根节点
{
return set[x]==x?x:set[x]=find(set[x]);
} int n,m,y; bool Pudge(int k) //判断函数,判断以k为最长道路(y为最大费用)的要求下能否建成。
{
int i;
int num = ;
int sum = ;
int fa,fb;
for(i=; i<=n; ++i)
set[i] = i;
for(i=; i<m; ++i)
{
if(a[i].dist>k) continue;
fa = find(a[i].x);
fb = find(a[i].y);
if(fa==fb) continue;
num++;
sum += a[i].cost;
set[fa] = fb;
if(num==n-)
{
if(sum<=y)
return true;
return false;
}
}
return false;
} int main()
{
int i;
int r,l,mid;
while(scanf("%d %d %d",&n,&m,&y)!=EOF)
{
r = ;
l = ;
for(i=; i<m; ++i)
{
scanf("%d %d %d %d",&a[i].x,&a[i].y,&a[i].cost,&a[i].dist);
r = r>a[i].dist?r:a[i].dist;
}
qsort(a,m,sizeof(a[]),cmp);
if(!Pudge(r)) { printf("-1\n"); continue; } //若道路取最大值的情况下,仍然建不了道路,输入-1;
while(l!=r) //二分验证
{
mid = (l+r)/;
if(Pudge(mid))
r = mid;
else
l = mid+;
}
printf("%d\n",l);
}
return ;
}
05-08 08:00