CodeForces125E MST Company（根限度为k的最小生成树+二分）

悠悠 2022-06-09 10:15 121阅读 0赞

The MST (Meaningless State Team) company won another tender for an important state reform in Berland.

There are *n* cities in Berland, some pairs of the cities are connected by roads. Each road has its price. One can move along any road in any direction. The MST team should carry out the repair works on some set of roads such that one can get from any city to any other one moving only along the repaired roads. Moreover, this set should contain exactly *k* capital roads (that is, the roads that start or finish in the capital). The number of the capital is 1.

As the budget has already been approved, the MST Company will profit by finding the set with minimum lengths of roads.

Input

The first input line contains three integers *n*, *m*, *k* (1 ≤ *n* ≤ 5000;0 ≤ *m* ≤ 105;0 ≤ *k* < 5000), where *n* is the number of cities in the country, *m* is the number of roads in the country, *k* is the number of capital roads in the required set. Then *m* lines enumerate the roads in question. Each road is specified by three numbers *a**i*, *b**i*, *w**i*(1 ≤ *a**i*, *b**i* ≤ *n*; 1 ≤ *w* ≤ 105), where *a**i*, *b**i* are the numbers of cities linked by a road and *w**i* is its length.

Between each pair of cities no more than one road exists. There are no roads that start and finish in one city. The capital's number is 1.

Output

In the first line print the number of roads in the required set. The second line should contain the numbers of roads included in the sought set. If the sought set does not exist, print -1.

Example

Input

4 5 2
    1 2 1
    2 3 1
    3 4 1
    1 3 3
    1 4 2

Output

3
    1 5 2

题解：

题意：

给你n个点，m条边，限度k，让你求一个根（就是1号节点）度数为k的最小生成树，输出边数和选择边的序号，如果没有就输出-1

思路：

我们用克鲁斯卡尔算法先跑一遍最小生成树，看选择的与1相连的边数为多少，如果大于k的话我们就将所有与1相连的边加上一个相同的权值mid，使得这些边可以后一些选择，否则就减去一个mid，使得这些边前一些选择，然后继续跑一遍克鲁斯卡尔，直到找到那个增量为止，因为这个增量加上以后可能有些与1相连的边值相同，那么选的与1相连的边就会超过k，特判一下就行了。。。还有就是要用double来求增量，那么判断相等时就要用一个eps

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    using namespace std;
    #define INF 100861111
    #define ll long long
    #define eps 1e-5
    struct edge
    {
        int f,t;
        double v;
        int id;
        friend bool operator<(edge x,edge y)
        {
            return x.v<y.v;
        }
    }a[100005],b[100005];//a为排序后的原始数组，b为与1相连的边加上增量后的数组
    int p[10005];//存与1相连的边的号
    int n,m,k;
    int choose[100005];//存选择的边的号
    int pre[5005];
    int find(int x)
    {
        if(x!=pre[x])
            pre[x]=find(pre[x]);
        return pre[x];
    }
    int kl(int tag)//tag为0表示普通克鲁斯卡尔，为1表示求与1相连的边数为k的最小生成树
    {
        int i,j,d1,d2;
        sort(b+1,b+m+1);
        for(i=1;i<=n;i++)
            pre[i]=i;
        int ans=0,tot=0;
        for(i=1;i<=m;i++)
        {
            d1=find(b[i].f);
            d2=find(b[i].t);
            if(d1!=d2)
            {
                if(tag)//tag为1时加上特判
                {
                    if(b[i].f==1&&ans>=k)
                        continue;
                }
                pre[d2]=d1;
                choose[tot]=b[i].id;
                tot++;
                if(b[i].f==1)
                {
                    ans++;
                }
            }
            if(tot>=n-1)
                break;
        }
        return ans;
    }
    int main()
    {
        int i,j,x,y,ans=0,u,v,s=0;
        double l,r,mid;
        memset(num,0,sizeof(num));
        scanf("%d%d%d",&n,&m,&k);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%lf",&a[i].f,&a[i].t,&a[i].v);
            a[i].id=i;
            if(a[i].f>a[i].t)
                swap(a[i].f,a[i].t);
            if(a[i].f==1)//记录1的度数
                ans++;
        }
        if(ans<k||(n>1&&k==0)||m<n-1)//不符合的情况
        {
            printf("-1\n");
            return 0;
        }
        sort(a+1,a+m+1);
        for(i=1;i<=m;i++)
        {
            if(a[i].f==1)
            {
                p[s]=i;
                s++;
            }
        }
        l=-100000.0,r=100000.0;//设置二分左右边界
        int t;
        while(r-l>eps)
        {
            mid=(l+r)/2.0;
            for(i=1;i<=m;i++)
            {
                b[i]=a[i];
            }
            for(i=0;i<s;i++)
            {
                b[p[i]].v+=mid;
            }
            t=kl(0);
            if(t<k)
                r=mid-1;
            else
            {
                if(fabs(l-mid)<eps)//排除一直循环的情况
                    break;
                l=mid;
            }
        }
        for(i=1;i<=m;i++)
        {
            b[i]=a[i];
        }
        for(i=0;i<s;i++)
        {
            b[p[i]].v+=l;
        }
        t=kl(1);//找到增量后再跑一遍
        printf("%d\n",n-1);
        if(k!=0)
            printf("%d",choose[0]);
        for(i=1;i<n-1;i++)
            printf(" %d",choose[i]);
        if(k!=0)
        printf("\n");
        return 0;
    }