免費道路 bzoj 3624，bzoj3624

免費道路 bzoj 3624，bzoj3624

免費道路（1s 128MB）roads

【輸入樣例】

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

題解：

主要算法：生成樹；

題意即為求一棵剛好擁有k條鵝卵石路的生成樹

那麼我們先將所有水泥路加入圖中

就可以知道必須要加入的鵝卵石路

將這些邊加入新樹中

接下來再隨意地按樹的結構加入至k條鵝卵石路

並再更加隨意按樹結構至連通

那麼就得到了合法方案

判斷過程中無解的情況：

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);
}