2012 ACM/ICPC Asia Regional Online Warmu 部分代码和数据
总结见：http://blog.csdn.net/woshi250hua/article/details/7908090
1002代码：
#include <stdio.h>#include <string.h>#define MIN 1100#define MAX 1000000struct node { int v,kind; node *next;}tree[MAX*2],*head[MIN];int ptr,n,m,k,flag;int fa[MIN],rank[MIN];void Initial() { ptr = flag = 0; memset(head,NULL,sizeof(head)); for (int i = 1; i <= n; ++i) fa[i] = i,rank[i] = 1;}void AddEdge(int x,int y,int kind) { tree[ptr].v = y,tree[ptr].kind = kind; tree[ptr].next = head[x],head[x] = &tree[ptr++];}int Getfa(int x) { int r = x,q; while (r != fa[r]) r = fa[r]; while (r != x) { q = fa[x]; fa[x] = r; x = q; } return r;}int Solve() { int i,j; int mmax = 0,mmin = 0; node *p; for (i = 1; i <= n; ++i) { p = head[i]; while (p != NULL) { if (p->kind) { int u = i,v = p->v; int ta = Getfa(u),tb = Getfa(v); if (ta != tb) fa[ta] = tb,mmax++; } p = p->next; } } for (i = 1; i <= n; ++i) fa[i] = i,rank[i] = 1; for (i = 1; i <= n; ++i) { p = head[i]; while (p != NULL) { if (p->kind == 0) { int u = i,v = p->v; int ta = Getfa(u),tb = Getfa(v); if (ta != tb) fa[ta] = tb,mmin++; } p = p->next; } } mmin = n - 1 - mmin; //printf("%d %d\n",mmin,mmax); if (mmin <= k && mmax >= k) return 1; else return 0;}int main(){ int i,j; while (scanf("%d%d%d",&n,&m,&k),n+m+k) { Initial(); for (i = 1; i <= m; ++i) { int b,c; char s[2]; scanf("%s %d%d",s,&b,&c); AddEdge(b,c,s[0]=='B'); AddEdge(c,b,s[0]=='B'); } int flag = Solve(); printf("%d\n",flag); }}