C. Bertown Subway（带权并查集）

题面如下

题意简说

给你 $n$ 个位置
第 $i$ 个位置有一个数 $a_i$
位置 $i$ 可以到达位置 $a_i$
你可以最多改变两个位置的 $a_i$ 的值
问：
最多存在多少对 $(x,y)$ [$x$ 到 $y$, $x与y$可以相等]

题解or思路

我们可以发现路一定是成环的，可能存在多个环。

如果一个环有 $num$ 个点
那么这个环的贡献就是 $num\ast num$ 个方案数
$ans=ans+num\ast num$

如果环数 $\ge 2$
我们可以把最大的两个环拼接成一个大环(通过改变$a_i$的值)
约定：两个最大的环的点数分别是 $ab$
那么贡献应该是减去两环的贡献 + 新大环的贡献
$ans=ans-a\ast a+b\ast b$
$ans=ans+(a+b)\ast (a+b)$

AC代码如下：

int n;
int f[N], num[N];
int find(int x)
{
   return f[x] == x ? x : f[x] = find(f[x]);
}
void solve()
{
   cin >> n;
   vector<int> v;
   for (int i = 1; i <= n; i++)
       f[i] = i, num[i] = 1;
   int ans = 0;
   for (int i = 1; i <= n; i++)
   {
       int tt;
       cin >> tt;
       int a = find(i), b = find(tt);
       if (a != b)
       {

           f[a] = b;
           num[b] += num[a];
       }
       else
       {
           ans += num[a] * num[a];
           v.push_back(num[a]);
       }
   }
   sort(v.begin(), v.end());
   if (v.size() >= 2)
   {
       int a = v.back();
       v.pop_back();
       int b = v.back();
       v.pop_back();

       ans -= (a * a + b * b);
       ans += (a + b) * (a + b);
   }

   cout << ans << 'n';
}

最后

以上就是开放小伙为你收集整理的C. Bertown Subway（带权并查集）的全部内容，希望文章能够帮你解决C. Bertown Subway（带权并查集）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。