免费道路

Time Limit: 2 Sec Memory Limit: 128 MB

Description

img

Input

img

Output

img

Sample Input

5 7 2
　1 3 0
　4 5 1
　3 2 0
　5 3 1
　4 3 0
　1 2 1
　4 2 1

Sample Output

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

HINT

1<=n<=20000,1<=m<=100000,0<=k<=n-1

Main idea

一种0边，一种1边，求一棵最小生成树并且正好有K条0边，输出其中一种方案。

Solution

显然要搞一棵符合题目的生成树。

每次要加入0边或者1边，直接做肯定不可行，考虑有什么0边是一定要加入的。

只需要输出一种方案，所以我们先加入所有可加的1边，如果图不联通则加入可加入的0边，那么这几条0边在我们所求的方案中是一定需要加入的。

这时候判断一下，如果此时加入的0边数量>K，或者图还是无法联通的话则无解。然后处理完毕前半部分，考虑接下来如何实现。

因为我们要使得图为树并且正好有K条0边，运用贪心，想到了加入0边到K条位置（如果到不了K条则也无解），然后剩下的用1边来填。

验证一下这样做的可行性：由于我们在前半部分使得了可以成为一棵树，那么显然我们在后半部分中每加入一条0边，则在前半部分中一定有一条1边可以替换使得可行（因为前半部分是尽量加入1边）。每次连边判环运用Kruscal即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;

const int ONE=1000001;
const int INF=2147483640;

int n,m,k;
int Edge_k;
int fa[ONE];
int num;
int Choose[ONE];
int ans_num;
int the0;

struct power
{
    int x,y,v;
}a[ONE],Ans_edg[ONE];



int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}

void Un(int a,int b)
{
    int a1=find(a);
    int b1=find(b);
    if(a1!=b1) fa[a1]=b1;
}

int Add_set(int N,int v,int ci)
{
    int kd=0;
    for(int i=1;i<=m;i++)
    {
        if(kd>=N) break;

        if(a[i].v!=v) continue;

        int x=a[i].x,y=a[i].y;
        if(find(x)!=find(y))
        {
            Un(x,y);
            if(ci>=2)    Ans_edg[++ans_num]=a[i];
            if(ci==2)
            {
                Choose[++num]=i;
            }
            Edge_k++;
            kd++;
            if(ci==3) the0++;
        }
        if(Edge_k==n-1) break;
    }
}

int main()
{
    n=get();    m=get();    k=get();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        a[i].x=get();    a[i].y=get();    a[i].v=get();
    }
    Edge_k=0;

    Add_set(INF,1,1);
    Add_set(INF,0,2);

    if(Edge_k<n-1 || num>k)
    {
        printf("no solution\n");
        return 0;
    }

    Edge_k=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=num;i++)
    {
        int x=Choose[i];
        Un(a[x].x,a[x].y);
        Edge_k++;
        if(Edge_k==n-1) break;
    }

    Add_set(k-num,0,3);
    if(the0!=k-num)
    {
        printf("no solution\n");
        return 0;
    }

    Add_set(INF,1,4);
    for(int i=1;i<=ans_num;i++)
    {
        printf("%d %d %d\n",Ans_edg[i].x,Ans_edg[i].y,Ans_edg[i].v);
    }

}