首页 > 代码库 > hdu 3635 Dragon Balls 并查集

hdu 3635 Dragon Balls 并查集

2024-11-17 18:30:02   202人阅读

推荐题解：http://www.cppblog.com/cxiaojia/archive/2011/11/04/nyoj431.html

思路：看懂题意后就知道用并查集了。询问的前两个问题都很好解决，有点难度的是第三个问题，龙珠被移动的次数。我用rnk数组统计每颗龙珠移动的次数，路径压缩后，每颗龙珠的父亲就是它所在的城市，如果这颗龙珠所在的城市所有的龙珠被移走的话，这座城市变成一座空城市，所以不会有龙珠再被移动到这座城市，就是说一座城市只能转移一次，假设a所在的城市的所有龙珠移动到了b，合并的时候统计这座城市移动的次数，那么统计龙珠的时候，只要统计它的父亲它的祖父一直到它的老祖，每个长辈的rnk和就是这颗龙珠的移动次数。所以在merge的时候让它父亲的rnk++，Find的时候让它遍历到根节点每次都加上一个长辈的rnk。写完后会感觉到，就是一个裸体的并查集。

 

注意：printf的先从右向左计算  再输出，右边的数受左边的数影响时容易出错。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip>10 #include<climits>11 #define INF 1e1112 #define MAXN 10010 13 using namespace std;14 15 #define _min(a,b) (((a)<(b))?((a):(b)))16 //适用于正负整数17 template <class T>18 inline bool scan_d(T &ret) {19     char c; int sgn;20     if (c = getchar(), c == EOF) return 0; //EOF21     while (c != ‘-‘ && (c<‘0‘ || c>‘9‘)) c = getchar();22     sgn = (c == ‘-‘) ? -1 : 1;23     ret = (c == ‘-‘) ? 0 : (c - ‘0‘);24     while (c = getchar(), c >= ‘0‘&&c <= ‘9‘) ret = ret * 10 + (c - ‘0‘);25     ret *= sgn;26     return 1;27 }28 29 int ball_num[MAXN];30 int fa[MAXN];31 int rnk[MAXN];32 int a, b;33 int T, n, m, k;34 char ch;35 36 int find(int x) {37     if (fa[x] == x) return x;38     int t = fa[x];39     fa[x] = find(fa[x]);40     rnk[x] += rnk[t];41     return fa[x];42 }43 44 void init(int n)45 {46     for (int i = 1; i <= n; ++i) {47         ball_num[i] = 1;48         fa[i] = i;49         rnk[i] = 0;50     }51 }52 53 bool merge(int a, int b)54 {55     int x = find(a);56     int y = find(b);57     if (x == y) return false;58     else {59         ball_num[y] += ball_num[x];60         ball_num[x] = 0;61         fa[x] = fa[y];62         rnk[x] = 1;63     }64     return true;65 }66 67 void process()68 {69     printf("Case %d:\n", ++k);70     scan_d(n); scan_d(m);71     init(n);72     for (int i = 0; i < m; ++i) {73         cin >> ch;74         if (ch == ‘T‘) {75             scan_d(a); scan_d(b);76             merge(a, b);77         }78         else {79             scan_d(a);80             b = find(a);81             printf("%d %d %d\n",b, ball_num[b], rnk[a]);82         }83     }84 }85 86 int main()87 {88     scan_d(T);89     while (T--)90         process();91     //system("pause");92     return 0;93 }

 

hdu 3635 Dragon Balls 并查集


联系
我们