免费道路 bzoj 3624

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

第七城市

免费道路(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);}

 

第七城市

相关文章

    无相关信息

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台