首页 > ACM题库 > HDU-杭电 > HDU 4263-Red/Blue Spanning Tree-并查集-[解题报告]HOJ
2015
05-23

HDU 4263-Red/Blue Spanning Tree-并查集-[解题报告]HOJ

Red/Blue Spanning Tree

问题描述 :

Given an undirected, unweighted, connected graph, where each edge is colored either blue or red, determine whether a spanning tree with exactly k blue edges exists.

输入:

There will be several test cases in the input. Each test case will begin with a line with three integers:
n m k
Where n (2≤n≤1,000) is the number of nodes in the graph, m (limited by the structure of the graph) is the number of edges in the graph, and k (0≤k<n) is the number of blue edges desired in the spanning tree.
Each of the next m lines will contain three elements, describing the edges:
c f t
Where c is a character, either capital ‘R’ or capital ‘B’, indicating the color of the edge, and f and t are integers (1≤f,tn, tf) indicating the nodes that edge goes from and to. The graph is guaranteed to be connected, and there is guaranteed to be at most one edge between any pair of nodes.
The input will end with a line with three 0s.

输出:

There will be several test cases in the input. Each test case will begin with a line with three integers:
n m k
Where n (2≤n≤1,000) is the number of nodes in the graph, m (limited by the structure of the graph) is the number of edges in the graph, and k (0≤k<n) is the number of blue edges desired in the spanning tree.
Each of the next m lines will contain three elements, describing the edges:
c f t
Where c is a character, either capital ‘R’ or capital ‘B’, indicating the color of the edge, and f and t are integers (1≤f,tn, tf) indicating the nodes that edge goes from and to. The graph is guaranteed to be connected, and there is guaranteed to be at most one edge between any pair of nodes.
The input will end with a line with three 0s.

样例输入:

3 3 2
B 1 2
B 2 3
R 3 1
2 1 1
R 1 2
0 0 0

样例输出:

1
0

并查集的应用

先算出用红边去构成生成树最多用x1条,那么蓝边最少就用n-1-x1;

再算出用蓝边去构成生成树最多用x2条,那么蓝边最多就用x2;

然后判断k是否介于之间即可

#include<cstdio>
#include<cstring>
#define N 1010
using namespace std;
int c1,c2;
int f1[N],f2[N];
int n,m,k;
void init(){
    int i;
    c1=c2=0;
    for(i=1;i<=n;i++)
        f1[i]=f2[i]=i;
}
int find(int u,int *f){
    if(f[u]==u)return u;
    return f[u]=find(f[u],f);
}
void Union(int u,int v,int &c,int *f){
    int pu=find(u,f);
    int pv=find(v,f);
    if(pu!=pv){
        f[pu]=pv;
        c++;
    }
}
int main(){
    char s[10];
    int u,v;
    int i;
    while(scanf("%d %d %d",&n,&m,&k)){
        if(n==0 && m==0 && k==0)break;
        init();
        for(i=1;i<=m;i++){
            scanf("%s %d %d",&s,&u,&v);
            if(s[0]=='R')
                Union(u,v,c1,f1);
            else
                Union(u,v,c2,f2);
        }
        if(n-1-c1<=k && c2>=k) printf("1\n");
        else printf("0\n");
    }
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/waitfor_/article/details/7982546