公路修建问题

题目描述

输入输出格式

输入格式：

在实际评测时，将只会有m-1行公路

输出格式：

输入输出样例

输入样例#1：

4 2 5

1 2 6 5

1 3 3 1

2 3 9 4

2 4 6 1

输出样例#1：

6

1 1

2 1

4 1

题解

看到要求路径中花费最大的一条边花费最小,最小值最大?马上二分

二分什么?二分出一个最大花费,只有小于等于这个花费的边才加进来,那么怎么验证?

二分出的这个花费依然要保证这个图联通,也就是一棵树

我们可以使用并查集,维护集合的连通性

两次for循环,第一次只选一级公路,并统计个数

第二次只选二级公路

最后判断所选一级公路的条数是不是大于等于题目所给的k值,除此之外还要判断图是否联通,为什么?,因为到后面二分值越来越小,选的边越来越少,不一定保证图联通,所以最后我们还要判断一下边的条数是不是等于n-1

这道题还可以用最小生成树做,个人感觉麻烦一些

#include
    
     #define in(i) (i=read())using namespace std;int read() {  int ans=0,f=1; char i=getchar();  while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}  while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+(i^48),i=getchar();  return ans*f;}struct node {    int x,y,v,w;}a[20010];struct tq {    int id,p;}ans[20010],as[20010];int n,k,m,l,r=30010,tot,sum;int fa[10010];int find(int x) {    if(fa[x]!=x) fa[x]=find(fa[x]);    return fa[x];}bool check(int mid) {    int cnt=0;    for(int i=1;i<=m;++i) {        if(a[i].v<=mid) {            int fx=find(a[i].x),fy=find(a[i].y);            if(fx!=fy) fa[fx]=fy,cnt++,ans[++tot].id=i,ans[tot].p=1;        }    }    for(int i=1;i<=m;++i) {        if(a[i].v>mid && a[i].w<=mid) {            int fx=find(a[i].x),fy=find(a[i].y);            if(fx!=fy) fa[fx]=fy,ans[++tot].id=i,ans[tot].p=2;        }    }    return ((cnt>=k)&&tot==n-1);}int main(){    in(n);in(k);in(m);--m;    for(int i=1;i<=m;++i) in(a[i].x),in(a[i].y),in(a[i].v),in(a[i].w);    while(l
     
      >1;tot=0;        if(check(mid)) {            r=mid; sum=tot;            for(int i=1;i<=sum;++i)                as[i].id=ans[i].id,as[i].p=ans[i].p;        }        else l=mid+1;    }    printf("%d\n",r);    for(int i=1;i<=sum;++i) printf("%d %d\n",as[i].id,as[i].p);}
     
    

博主蒟蒻,随意转载.但必须附上原文链接