hdu 4263（有限制的生成树）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4263

思路：将红边和蓝边单独求一次生成树，求的红边最多可以加入的边数cntr，蓝边最多可以加入的边数cntb，只要k满足条件k>=(n-1-cntr)&&k<=cntb，就说明可以生成这样的spanning tree.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1100
int parent[MAXN];
int n,m,k;
struct Edge{
   int u,v;
}B[MAXN*MAXN],R[MAXN*MAXN];

int Find(int x)
{
   if(x==parent[x])
      return parent[x];
   parent[x]=Find(parent[x]);
   return parent[x];
}

bool Union(int u,int v)
{
   int r1=Find(u),r2=Find(v);
   if(r1==r2)return false;
   parent[r1]=r2;
   return true;
}


int main()
{
 //  freopen("1.txt","r",stdin);
   int ansb,ansr,cntb,cntr;
   char str[4];
   while(scanf("%d%d%d",&n,&m,&k),(n+m+k))
   {
      ansb=ansr=cntb=cntr=0;
      for(int i=1;i<=m;i++){
         scanf("%s",str);
         if(str[0]=='B'){
            scanf("%d%d",&B[cntb].u,&B[cntb].v);
            cntb++;
         }else {
            scanf("%d%d",&R[cntr].u,&R[cntr].v);
            cntr++;
         }
      }
      for(int i=1;i<=n;i++)parent[i]=i;
      for(int i=0;i<cntb;i++){
         int u=B[i].u,v=B[i].v;
         if(Union(u,v))ansb++;
      }
      for(int i=1;i<=n;i++)parent[i]=i;
      for(int i=0;i<cntr;i++){
         int u=R[i].u,v=R[i].v;
         if(Union(u,v))ansr++;
      }
      if(k>=(n-1-ansr)&&k<=ansb){
         puts("1");
      }else
         puts("0");
   }
   return 0;
}