题解 CF1411C 【Peaceful Rooks】

· · 题解

题意简述

3 1

2 3

只有一个车的话，只要把他移动到对角线上即可

3 2

2 1
1 2

考虑一下怎样移动最优，由于车的数量少于列的数量，我们可以试试用第三行当做缓冲行，先把第一列的车移到第三行，然后把第二列的车移到第二行，再把第三行的车移到第一行

我们可以发现在操作过程中并没有移动每个车的列号，可以想到如果左右移动改变了列，那么相当于多走了一步，似乎并不能更优（当然可能会出现移动列可以直接到对角线上的情况，不过我们先这么猜想，后面再回来证明）

有了这个猜想以后就好做很多，可以用一条边从它当前的行指向它需要去的行（即从它当前的行号位置指向它的列号的那个位置）

对于上面那个图，就构成了一个环，那么我们不能把1节点放到2位置去，因为2正占着2号位置，而2也不能移动，因此需要把1或2移到3位置，然后就只剩另一个节点了，这时候直接把那个节点归位，然后把移出去的节点放回来即可

于是我们有一个猜想：

对于一条链的情况，需要的移动步数就是链的长度。而对于一个环，需要的移动步数就是环的大小+1，这个+1是指某一个节点先要移到缓冲列上的这一步，剩下就是一样了

举例模拟：

5 4

2 3
3 1
1 2
4 5

按照刚才的方式，建立一个有向图:

这样相当于3要移到1位置，1要移到2位置，2要移到3位置，4要移到5位置（相当于就是从行向列发出了一条有向边）

那么这个时候3,1,2构成了一个环，如果我想把3移到1位置，就得把2移到3位置，就得把1移到2位置，就得把3移到1位置……永远都不能移动出来

因此可以按照刚才猜想的规律，随便取出一个节点放到5的位置去，例如拿出3，这样1,2就形成了一条链，2放到3原来的位置，1再放到2原来的位置就归位了，这时候1原来的位置自然也让出来了，让3移回去即可，总步数是节点数+1=4

然后对于4的情况，5因为是空的，因此这个链实际上只有4这一个节点，只需要把4移动过去即可，因此步数为1

所以总步数为5

证明

可行性：显然

最优性：

对于有向图中的一条链，需要移动的步数就是链的长度，因此每个需要移动的节点都只会移动一次，不会有比这个更优秀的方案了。

对于环来说，用我们的方法步数是环的长度+1，破坏这个环是必须的，因为我们不能通过一个环的整体移动得到归位。破坏这个环的最短步数就是1步，然后这个环里面每个节点按我们的方法都只会移动一次，因此对于这个破坏后的环来说最优步数就是环中节点个数，而破坏一个环最优步数是1，因此总共的最优步数仍然是环中节点个数+1

因此我们证明了这个方法的可行性与最优性

实现

可以使用tarjan算法查找环，相当于把这个图分成许多个强连通分量，那么对于节点个数大于1的强连通分量，相当于就是一个环，这时候就把答案加上节点个数+1，对于其他等于1的强连通分量，对答案的贡献就只有1了。

Talk\ is\ cheap,\ show\ you\ the\ code: 
#include<iostream>
#include<cstdio>
#define N 100010
int t,n,m,s,k,hd[N],nxt[N],to[N],st[N],top,low[N],dfn[N],inst[N],vis[N],ans;
void newedge(int u,int v){
    nxt[++k]=hd[u];
    to[k]=v;
    hd[u]=k;
    return;
}void dfs(int x){
    dfn[x]=low[x]=++s;
    st[top++]=x;
    inst[x]=1;
    for(int i=hd[x];i;i=nxt[i]){
        int nex=to[i];
        if(!vis[nex])continue;//vis记录了有车的节点，有的节点上面没有车就不要走
        if(!dfn[nex]){
            dfs(nex);
            low[x]=std::min(low[x],low[nex]);
        }else if(inst[nex])low[x]=std::min(low[x],dfn[nex]);
    }if(low[x]==dfn[x]){
        int cnt=0;
        do{
            cnt++;
            inst[st[top-1]]=0;
        }while(st[--top]!=x);
        if(cnt<=1)ans+=1;//节点个数小于1，说明在链上，只能贡献1
        else ans+=cnt+1;//是一个环，贡献节点个数+1
    }return;
}
int main(){
    scanf("%d",&t);
    start:
    if(t--==0)return 0;
    scanf("%d%d",&n,&m);
    top=s=k=ans=0;
    for(int i=1;i<=n;i++)vis[i]=hd[i]=nxt[i]=to[i]=st[i]=low[i]=dfn[i]=inst[i]=0;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x==y)continue;//已经满足要求，不要加入图中
        newedge(x,y);//从当前行号向列号建一条边，相当于目标是把行号变成列号
        vis[x]=1;//把这个节点标记成有车的节点
    }for(int i=1;i<=n;i++){
        if(vis[i]&&!dfn[i]){//tarjan求强连通分量
            dfs(i);
        }
    }printf("%d\n",ans);
    goto start;
}