P2323 [HNOI2006]公路修建问题

题目描述

输入输出格式

输入格式：

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

输出格式：

---

思路：

二分答案

然后把每条能加的大边都加上，然后加小边

但在洛谷的题解中，没有采用二分答案而直接先处理k条大边，再处理小边的做法我认为是有问题的，欢迎证明或证伪。

---

Code：

#include <cstdio>

#include <algorithm>

const int N=10010;

const int M=20010;

struct node

{

    int u,v,w,id;

    bool friend operator <(node n1,node n2)

    {

        return n1.w<n2.w;

    }

}e1[M],e2[M];

int n,k,m;

void init()

{

    scanf("%d%d%d",&n,&k,&m);

    for(int i=1;i<m;i++)

    {

        scanf("%d%d%d%d",&e1[i].u,&e1[i].v,&e1[i].w,&e2[i].w);

        e2[i].u=e1[i].u;e2[i].v=e1[i].v;

        e1[i].id=e2[i].id=i;

    }

    std::sort(e1+1,e1+m);

    std::sort(e2+1,e2+m);

}

int f[N];

std::pair <int,int> ans[N];

int Find(int x){return f[x]=f[x]==x?x:Find(f[x]);}

void Merge(int x,int y){f[Find(y)]=Find(x);}

bool check(int len)

{

    for(int i=1;i<=n;i++) f[i]=i;

    int e=0,we=0;

    for(int i=1;i<m;i++)

    {

        if(e1[i].w>len) break;

        int u=e1[i].u,v=e1[i].v;

        if(Find(u)!=Find(v))

        {

            Merge(u,v);

            ans[++e].first=e1[i].id;

            ans[e].second=1;

            we++;

        }

    }

    for(int i=1;i<m;i++)

    {

        if(e2[i].w>len) break;

        int u=e2[i].u,v=e2[i].v;

        if(Find(u)!=Find(v))

        {

            Merge(u,v);

            ans[++e].first=e2[i].id;

            ans[e].second=2;

        }

    }

    return e==n-1&&we>=k;

}

void work()

{

    int l=1,r=30000;

    while(l<r)

    {

        int mid=l+r>>1;

        if(check(mid))

            r=mid;

        else

            l=mid+1;

    }

    check(l);

    printf("%d\n",l);

    std::sort(ans+1,ans+n);

    for(int i=1;i<n;i++)

        printf("%d %d\n",ans[i].first,ans[i].second);

}

int main()

{

    init();

    work();

    return 0;

}

---

2018.8.2