Mutual Training for Wannafly Union #6 E - Summer Trip(并查集)

时间:2022-11-05 18:19:26

题目链接:http://www.spoj.com/problems/IAPCR2F/en/

题目大意:

给m个数字代表的大小,之后n组数据,两两关联,关联后的所有数字为一组,从小到大输出组数以及对应的组数数字和.

解题思路:

很明显一个并查集,5个月前的这场比赛,过三四题的人不少,其实有3题是大众题,这题当时知道是并查集,可是当时对其理解不深,没A掉.现在回头来补题,用数组存储莫名WA,改用vector玄学AC。下次回头来看应该又用不一样的感受吧!

丑代码:

#include <stdio.h>
#include <stdlib.h>
#include <cmath>
#include <cstring>
#include <iostream>
#include<algorithm>
#include <queue>
#include <map>
#include <vector>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
#define maxn 2000
#define LL long long
#define inf 0x3f3f3f3f
//************************************************
int pre[maxn],sum[maxn],num[maxn];
int cmp(int a,int b)
{
return a>b;
}
int find(int x)
{
/*int root,temp;
root=x;
while(root!=pre[root])
root=pre[root];
while(x!=root)
{
temp=pre[x];
pre[temp]=root;
x=temp;
}
return root;*/
return x==pre[x]?x: pre[x]=find(pre[x]);
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy) pre[fx]=fy;
}
int main()
{
int t,m,n,a,b,k=;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
for(int i=; i<=m; i++)
{
scanf("%d",&num[i]);
pre[i]=i;
sum[i]=;
}
for(int i=; i<=n; i++)
{
scanf("%d%d",&a,&b);
join(a,b);
}
for(int i=; i<=m; i++) sum[find(i)]+=num[i];
vector<int>Q;
for(int i=; i<=m; i++)
{
if(sum[i]) Q.push_back(sum[i]);
}
sort(Q.begin(),Q.end());
printf("Case %d: %d\n",k++,Q.size());
for(int i=; i<Q.size(); i++) printf("%d%c",Q[i],i==Q.size()-?'\n':' ');
}
return ;
}