CF238C World Eater Brothers

解题报告

CF238C World Eater Brothers解题报告：

更好的阅读体验

题意

• 题意：给定一个$n$个点，$n-1$条边的有向树，求至少翻转多少条边的方向才能让入度为$0$的点数量不超过$2$。
• 数据范围：$1\leqslant n\leqslant 3000$。

分析

这道题题解说的有点不清楚，看了cf上的题解才搞懂这道题。

首先我们可以考虑只有一个入度为$0$的点的情况：直接枚举这个点，然后遍历一遍树就得到了答案，时间复杂度是$O(n^2)$的。

对于有两个入度为$0$的点的情况，我们不难发现这两个入度为$0$的点的路径一定是类似这样的：

1-->2-->3<--4<--5->...
|               |
v               v
...            ...

我们考虑枚举这两个点的路径上的中心点连接的边（如上图$3$连接的边$(2\rightarrow 3)$和$(4\rightarrow 3)$），也就是说枚举一条边，在这条边分成的两个连通块中分别选择一个点作为入度为$0$的点。

具体地，我们假装把这条边当做一个虚点作为根，并做一遍遍历得到以这个虚点为根的答案。

我们根据上图可得两个入度为$0$的点到虚点的路径会反向（虚点代表的边方向不改变），因此我们在遍历的时候在两个连通块里分别选取到达虚点的路径上需要反向的边数量减不需要反向的边的数量最小的点就好了。

时间复杂度：$O(n^2)$。

代码

#include<stdio.h>
#define inf 1000000000
const int maxn=3005,maxm=maxn<<1;
int n,e,ans,minn;
int start[maxn],to[maxm],then[maxm],worth[maxm],f[maxn],tot[maxn],xx[maxm],yy[maxm];
inline int min(int a,int b){
    return a<b? a:b;
}
inline int max(int a,int b){
    return a>b? a:b;
}
inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z;
}
void dfs(int x,int last){
    minn=min(minn,tot[x]);
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(y==last)
            continue;
        tot[y]=tot[x]+(worth[i]==0? -1:1);
        dfs(y,x);
        f[x]+=f[y]+(worth[i]^1);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y,1),add(y,x,0);
    }
    ans=n-1;
    for(int i=1;i<=n;i++)
        for(int j=start[i];j;j=then[j])
            if(worth[j]==1){
                int k=to[j],sum=0;
                for(int p=1;p<=n;p++)
                    f[p]=tot[p]=0;
                dfs(i,0),ans=min(ans,f[i]);
                for(int p=1;p<=n;p++)
                    f[p]=tot[p]=0;
                minn=inf,dfs(i,k);
                sum+=f[i]+minn;
                for(int p=1;p<=n;p++)
                    f[p]=tot[p]=0;
                minn=inf,dfs(k,i);
                sum+=f[k]+minn;
                ans=min(ans,sum);
            }
    printf("%d\n",ans);
    return 0;
}