首页 > ACM题库 > HDU-杭电 > HDU 2860-Regroup-并查集-[解题报告]HOJ
2014
02-17

HDU 2860-Regroup-并查集-[解题报告]HOJ

Regroup

问题描述 :

When ALPC42 got to a panzer brigade, He was asked to build software to help them regroup the battalions or companies.
As the tradition of army, soldiers are rated according his or her abilities, taking the rate as an integer. The fighting capacity of a company is determined by the soldier in this company whose rate is lowest. Now the recruits those rated are coming and join to their companies according to the order form HQ.
With the coming of new recruits, a big regroup action reached, asking to merge some companies into one. The designation of a company, however, will not be canceled, but remain for memorialize what the company is done, means the designation of the company is still exist, but the company is gone, so it is unable to ask recruits to join this company, or merge the company into others.
A strange thing is, the orders sometimes get wrong, send newbie to a company which is already merged into another, or mentioned some only-designation-existed companies. Such order could be rejected.
The brigadier wants to know every change of each order, so the program should able to report the status of every order, telling whether it is accept, and can query the fighting capacity of specified company. (To simplify, companies are numbered from 0 to n-1

输入:

There may be several test cases.
For each case, the integers in first line, n, k, m, telling that there are n companies, k soldiers already, and m orders needs be executed. (1<=n ,k ,m<=100000).
Then k lines with two integers R and C for each, telling a soldier with rate R is now in company C
Then m lines followed, containing 3 kinds of orders, in upper case:
  AP x y
A recruit with ability rate x were asked to join company y. (0<=x<2^31, 0<=y<n)

  MG x y
Company x and company y is merged. The new company is numbered as x. (0<=x, y<n)

  GT x
Report the fighting capacity of company x. (0<=x<n)

输出:

There may be several test cases.
For each case, the integers in first line, n, k, m, telling that there are n companies, k soldiers already, and m orders needs be executed. (1<=n ,k ,m<=100000).
Then k lines with two integers R and C for each, telling a soldier with rate R is now in company C
Then m lines followed, containing 3 kinds of orders, in upper case:
  AP x y
A recruit with ability rate x were asked to join company y. (0<=x<2^31, 0<=y<n)

  MG x y
Company x and company y is merged. The new company is numbered as x. (0<=x, y<n)

  GT x
Report the fighting capacity of company x. (0<=x<n)

样例输入:

5 5 10
5 0
5 1
5 2
5 1
5 0
GT 0
GT 3
AP 3 3
GT 3
GT 4
MG 3 4
GT 4
MG 1 3
GT 4
GT 1

样例输出:

Lowest rate: 5.
Company 3 is empty.
Accept
Lowest rate: 3.
Company 4 is empty.
Accept
Company 4 is a part of company 3.
Accept
Company 4 is a part of company 1.
Lowest rate: 3.

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

思路:多了一个记录每个集合最小值的value数组而已,然后判断的时候小心一点就可以了。

#include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 using namespace std;
 #define MAXN 100000+100
 int parent[MAXN];
 int value[MAXN];
 int n,m,k;
 
 void Initiate()
 {
     memset(value,-1,(n+2)*sizeof(int));
     for(int i=0;i<n;i++)parent[i]=i;
     while(k--){
         int u,v;
         scanf("%d%d",&u,&v);
         if(value[v]==-1||u<value[v])value[v]=u;
     }
 }
 
 
 int Find(int x)
 {
     if(x==parent[x])
         return x;
     parent[x]=Find(parent[x]);
     return parent[x];
 }
 
 int main(){
     char str[11];
     int u,v;
     while(~scanf("%d%d%d",&n,&k,&m))
     {
         Initiate();
         while(m--){
             scanf("%s",str);
             if(str[0]=='A'){
                 scanf("%d%d",&u,&v);
                 if(parent[v]!=v){ puts("Reject");continue;}
                 puts("Accept");
                 if(value[v]==-1||u<value[v])value[v]=u;
             }else if(str[0]=='M'){
                 scanf("%d%d",&u,&v);
                 if(parent[u]!=u||parent[v]!=v||u==v){
                     puts("Reject");
                     continue;
                 }
                 puts("Accept");
                 parent[v]=u;
                 if(value[v]!=-1&&(value[u]==-1||value[u]>value[v])){
                     value[u]=value[v];
                 }
             }else {
                 scanf("%d",&u);
                 if(parent[u]==u&&value[u]!=-1)printf("Lowest rate: %d.\n",value[u]);
                 else if(parent[u]==u&&value[u]==-1)printf("Company %d is empty.\n",u);
                 else printf("Company %d is a part of company %d.\n",u,Find(u));
             }
         }
         puts("");
     }
     return 0;
 }

 

解题参考:http://www.cnblogs.com/wally/archive/2013/06/09/3129326.html


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。