# 免费道路 bzoj 3624

2016-12-31 18:51:49来源:cnblogs.com作者:LoseYourTemper人点击

【输入样例】

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

【输出样例】

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

1.所有边加入都无法连通

2.鹅卵石路不足k条

`#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>using namespace std;const int me = 1000233;struct shape{    int x, y, z;};shape a[me], ans[me];int tot, num, cnt;int n, m, k;int fat[me];inline int Get(){    int x = 0;    char c = getchar();    while('0' > c || c > '9') c = getchar();    while('0' <= c && c <= '9')    {        x = (x << 3) + (x << 1) + c - '0';        c = getchar();    }    return x;}int Find(int x){    return (fat[x] != x) ? fat[x] = Find(fat[x]) : x;}int main(){    n = Get(), m = Get(), k = Get();    for(int i = 1; i <= n; ++i) fat[i] = i;    for(int i = 1; i <= m; ++i)    {        a[i].x = Get(), a[i].y = Get(), a[i].z = Get();        if(a[i].z)        {            int u = Find(a[i].x);            int v = Find(a[i].y);            if(u != v) fat[u] = v, ++cnt;        }    }    for(int i = 1; i <= m; ++i)        if(!a[i].z)        {            int u = Find(a[i].x);            int v = Find(a[i].y);            if(u != v)            {                fat[u] = v;                ans[++tot] = a[i];            }        }    if(cnt + tot != n - 1)    {        printf("no solution/n");        return 0;    }    for(int i = 1; i <= n; ++i) fat[i] = i;    for(int i = 1; i <= tot; ++i)    {        int u = Find(ans[i].x);        int v = Find(ans[i].y);        if(u != v) fat[u] = v;    }    num = tot;    if(num != k)        for(int i = 1; i <= m; ++i)            if(!a[i].z)            {                int u = Find(a[i].x);                int v = Find(a[i].y);                if(u != v)                {                    ++num;                    fat[u] = v;                    ans[++tot] = a[i];                    if(num == k) break;                }            }    if(num != k)    {        printf("no solution/n");        return 0;    }    for(int i = 1; i <= m; ++i)        if(a[i].z)        {            int u = Find(a[i].x);            int v = Find(a[i].y);            if(u != v)            {                fat[u] = v;                ans[++tot] = a[i];                if(tot == n - 1) break;            }        }for(int i = 1; i <= tot; ++i)        printf("%d %d %d/n", ans[i].x, ans[i].y, ans[i].z);}`

无相关信息