CodeForces-884C Bertown Subway 题解

首先分析题目,按照题目条件可以推断出这个铁路最后是又许许多多的环构成的,于是我们只要找出所有环的站点数,然后将两个最大的环合并,然后依次将各个环的平方相加,就可以得到结果了。

当然,首先是上暴力。

#include<bits\stdc++.h>

using namespace std;
int station[100002]={0},team[100002]={0},n,ans;

bool cmp(int a,int b)
{
    return a>b;
}


int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		int target_station;
		cin>>target_station;
		if(station[i] && station[target_station])
		{
			//两个都是有所属域的了
			if(station[i]!=station[target_station])
			{
				//把 station[target_station]那一组都给杀了
				int need_for_treatment=station[target_station];
				for(int j=1;j<=100000;j++) if(station[j]==need_for_treatment)station[j]=station[i];
				team[station[i]]+=team[need_for_treatment];
				team[need_for_treatment]=0;
			}
		}
		else if(station[i] || station[target_station])
		{
			//只有一个有主人 
			int target_group=max(station[i],station[target_station]);
			station[target_station]=target_group;
			station[i]=target_group;
			team[target_group]++;				
		}
		else
		{
			//都tm没域
			int target_group;
			for(int j=1;j<=100000;j++)
			{
				if(!team[j])
				{
					target_group=j;
					break;
				}
			}
			station[target_station]=target_group;
			station[i]=target_group;
			team[target_group]++;	
			if(target_station!=i)team[target_group]++;		
		}
	}
	sort(team,team+100001,cmp);
	team[1]+=team[0];
	for(int i=1;i<=100000;i++)
	{
		if(!team[i])break;
		ans+=team[i]*team[i];
	}
	cout << ans << endl;
	return 0;
}

可是这个代码炸了,第九个点TLE。于是我加了一个flag,记录当前刚刚被删除的team下标,这样循环寻找空白team时可以省点时间。
加完以后,我的代码在第十个点TLE。这离AC还很远。
于是,我想到了使用并查集,经过一番修改,代码如下。

#include<bits\stdc++.h>

using namespace std;
long long team[100002]={0},n;
long long ans;

int pre[100002];
int find(int x)			//查找根节点
{ 
    int r=x;
    while (pre[r]!=r) r=pre[r];	//返回根节点 r
    int i=x,j;
    while(i!=r)			//路径压缩
    {
         j=pre[i]; 		//在改变上级之前用临时变量  j 记录下他的值 
         pre[i]=r; 		//把上级改为根节点
         i=j;
    }
    return r;
}
 
 
void join(int x,int y)
{
    int fx=find(x),fy=find(y);	//判断x y是否连通,
    if(fx!=fy)			//如果已经连通,就不用管了
        pre[fx]=fy; 		//如果不连通,就把它们所在的连通分支合并起,
}

bool cmp(int a,int b)
{
	return a>b;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++)pre[i]=i;
	for(int i=1;i<=n;i++)
	{
		int target_station;
		cin>>target_station;
		join(i,target_station); 
	}
	for(int i=1;i<=n;i++)
	{
		while(1) if(pre[i]!=pre[pre[i]])pre[i]=pre[pre[i]];else break;
		team[pre[i]]++;
	}
	sort(team,team+n+1,cmp);
	team[1]+=team[0];
	for(int i=1;i<=100000;i++)
	{
		if(!team[i])break;
		ans+=team[i]*team[i];
	}
	cout << ans << endl;
	return 0;
}

提交上去时,AC了,耗时46ms,比暴力快很多很多很多很多………………………………

留下你的评论呗...

电子邮件地址不会被公开。 必填项已用*标注