免费道路 bzoj 3624

免费道路

【输入样例】

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 = ;

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 = ;

    char c = getchar();

    while('' > c || c > '') c = getchar();

    while('' <= c && c <= '')

    {

        x = (x << ) + (x << ) + c - '';

        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 = ; i <= n; ++i) fat[i] = i;

    for(int i = ; 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 = ; 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 - )

    {

        printf("no solution\n");

        return ;

    }

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

    for(int i = ; 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 = ; 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 ;

    }

    for(int i = ; 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 - ) break;

            }

        }for(int i = ; i <= tot; ++i)

        printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].z);

}

巴特西

免费道路 bzoj 3624

最新文章

热门文章