题解 P1330 【封锁阳光大学】

· · 题解

安利一波自己的博客

蒟蒻不才，写了一发树形dp过了此题。

思路:

首先，我们如果把这个图当做树来看的话，那么它有可能不止一棵树，所以它有可能是森林。我们可以用并查集来维护每一个连通块，设 root[i] 表示连通块 i 的根节点是哪一个，注意，最开始没有连边的时候，每一个连通块的根都是他自己。

解决完了遍历的问题后，我们设 f[i][0/1] 表示在以i为根的子树上选/不选这个点所需的最少的河蟹数量，则得出转移方程：

f[i][0]=\sum_{v\in son[i]}f[v][1] f[i][1]=\sum_{v\in son[i]}f[v][0] +1

然后我们将每一个联通块跑一遍树形 dp，再将答案累加每一个根放还是不放的最大值，最后输出答案即可。
最后需要注意的一个点，如果 m\geq n 或者遍历的时候遇到了已经访问过的点，那么说明这张图有回路，不可能存在合法答案，输出 Impossible

Code: 
  #include <bits/stdc++.h>
using namespace std;
struct Node
{
    int t;
    int next;
}node[200011];
bool book[10011];
int root[10011],f[10011];
int head[10011],tot=0,dp[10011][2];
int n,m;
void init()
{
    for(int i=1;i<=n;++i)
        f[i]=i,root[i]=i;
}
int getf(int v)
{
    if(f[v]==v) return v;
    else return f[v]=getf(f[v]);
}
void merge(int a,int b)
{
    int t1=getf(a),t2=getf(b);
    if(t1!=t2) f[t2]=t1,root[t2]=root[t1];
}
void add(int x,int y)
{
    node[++tot].t=y;
    node[tot].next=head[x];
    head[x]=tot;
}
void dfs(int f,int fa)
{
    if(book[f]) 
    {
        cout<<"Impossible";
        exit(0);
    }
    book[f]=1;
    dp[f][1]=1;
    bool flag=0;
    for(int i=head[f];i;i=node[i].next)
    {
        int u=node[i].t;
        if(u==fa) continue;
        dfs(u,f);
        dp[f][0]+=dp[u][1];
        dp[f][1]+=dp[u][0];
    }
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout); 
    int ans=0;
    scanf("%d %d",&n,&m); 
    init(); 
    for(int i=1;i<=m;++i) 
    {
        int x,y;
        scanf("%d %d",&x,&y);
        merge(x,y);
        add(x,y);
        add(y,x);
    }
    if(m>=n)
        cout<<"Impossible";
    else
    {
        for(int i=1;i<=n;++i)
            if(!book[i])
            {
                int ta=getf(i);
                dfs(root[ta],0);
                ans+=min(dp[ta][0],dp[ta][1]);
            }
        printf("%d",ans);
    }
    return 0;
}