题解CF1411C Peaceful Rooks

烟羽灵灵 · 2021-08-27 15:20:43 · 题解

题目大意

在 n*n 的象棋棋盘中，有 m 个车，每个车坐标为 (x_i,y_i) ，求出把每个车都移动到棋盘的主对角线（主对角线上点的坐标特点：横纵坐标相等）需要的最短次数 ans 。

题目分析

在象棋中，我们知道车走直线，所以想让 ans 最小，就要把车移到对应行或列的对角线上。那么在没有冲突且没有车原来就在对角线上的情况下，只需要移动 m 步就可以达到要求。

但是，任意两个车都不能在同一行或者同一列上，所以在本题中，当我们要把一个车移到对角线上时，就要先判断一下目标点所对应的列有没有车，如果有，则需先把那个车移走，然后再把待移动的车移到对角线上去。

那么，如何判断冲突呢？在这里，我们可以通过建图的方式来解决。我们把每个车的横纵坐标之间连边，如果有环，则说明会有冲突， ans 就要 +1 。有几个环，就有几个冲突，最后的 ans 就要加上环的数量。

计算环则可以通过并查集来实现。在加边时，如果目标的两个点已经在同一连通块，则加边后一定会形成一个环。所以只需要每次加边时记录一下就可了。

还有一点，如果有点本来就在对角线上，则无需移动， ans 也要随之 -1 。

总结一下， ans = m + 环数 - 对角线上点数。

代码实现

多组数据，每次不要忘记初始化。

#include <iostream>
using namespace std;
int n,m,t,x,y,fa[100010],ans;
int find(int x){
    if(x==fa[x])
        return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        ans=m;
        for(int i=1;i<=n;++i)
            fa[i]=i;
        for(int i=1;i<=m;++i){
            cin>>x>>y;
            if(x==y){
                --ans;
                continue;
            }
            if(find(x)==find(y))
                ++ans;
            else
                fa[x]=y;
        }
        cout<<ans<<endl;
    }
    return 0;
}