题意大概是这样的：
有一些保全公司，每个公司的能力值是由里面能力值最低的士兵决定的，公司与公司之间可以相互合并。如果一个公司被合并，那么为了纪念这个公司，这个公司的称号仍然存在（就是不能再向添加新兵和把这个公司在合并一次）。操作有时候会出现错误，比如向被合并的公司添加新兵。公司编号为0~n-1。输入每次操作的结果。
AP r c 是向公司c里面添加一个能力值为r的新兵。
MG x y 公司x与公司y合并，新的公司编号为x。
如果操作合理输出Accept，不合理输出Reject。
GT t 查询公司t
公司没有人输出Company t is empty.
公司被合并过输出Company t is a part of company z.
否则输出公司的能力值Lowest rate: ?.
不合理的情况
①已被合并过的公司再次合并。
②向被合并的公司合并。
③向被合并过得公司添加新人。
④自己与自己合并 ∑(っ °Д °;)っ
开一个是否被合并过的数组vis，战斗力fight，再根据操作去维护。我感觉我这个写的太顺了，一遍过。。。。。。
还有就是每组数据有空行，小心PE。
#include <iostream> #include <cstdio> #include <algorithm> #define LL long long #define MAX 100010 using namespace std; int tree[MAX]; bool vis[MAX]; LL fight[MAX]; void makeSet(int x) { vis[x]=false; tree[x]=x; fight[x]=0x3f3f3f3f; } int findSet(int x) { if(x!=tree[x]) tree[x]=findSet(tree[x]); return tree[x]; } bool Union(int x,int y) { if(vis[y]||x==y||vis[x]) return false; int fx=findSet(x); int fy=findSet(y); tree[fy]=fx; vis[fy]=true; fight[fx]=min(fight[fx],fight[fy]); fight[fy]=0; return true; } bool add(LL x,int c) { if(vis[c]) return false; fight[c]=min(fight[c],x); return true; } int main(void) { int n,m,k; while(scanf("%d%d%d",&n,&k,&m)!=EOF) { for(int i=0;i<MAX;i++) makeSet(i); LL r; int c,x,y,t; for(int i=0;i<k;i++) { scanf("%d%d",&r,&c); add(r,c); } while(m--) { string s; cin>>s; if(s=="AP") { scanf("%lld%d",&r,&c); if(add(r,c)) printf("Accept\n"); else printf("Reject\n"); } if(s=="MG") { scanf("%d%d",&x,&y); if(Union(x,y)) printf("Accept\n"); else printf("Reject\n"); } if(s=="GT") { scanf("%d",&t); if(fight[t]==0x3f3f3f3f) { printf("Company %d is empty.\n",t); continue; } if(findSet(t)!=t) { printf("Company %d is a part of company %d.\n",t,findSet(t)); continue; } else { printf("Lowest rate: %lld.\n",fight[t]); continue; } } } cout<<endl; } return 0; }
原文：http://www.cnblogs.com/ramzey/p/6338085.html