电子眼-树型DP

1019: 电子眼

Time Limit: 1 Sec Memory Limit: 64 MB

Description

中山市石一个环境优美、气候宜人的小城市。因为城市的交通并不繁忙，市内的道路网很稀疏。准确地说，中山市有N条马路和N个路口，每条马路连接两个路口，每两个路口之间最多只有一条马路。作为一条交通网络，显然每两个路口之间都是可达的。为了更好地管理中山市的交通，市长决定在一些路口加装电子眼，用来随时监视路面情况。这些装在路口的电子眼能够监视所有连接到这个路口的马路。现在市长想知道最少需要在多少个路口安装电子眼才能监视所有的马路。市长已经把所有的路口都编上了1～N的号码。给你中山市的地图，你能帮忙吗？

Input

输入文件第1行包括一个数字N(1<=N<=100000)，表示中山市的路口数。接下来N行，第i+1行的第一个数字ki表示有ki条马路与路口i相连，后面紧跟着ki个数字，表示与路口i直接相连的路口。

Output

输出最少需要安装电子眼的数量。

Sample Input

3 2 2 3 2 1 3 2 1 2

Sample Output

分析：经典的树型DP，每点有两种状态，安装电子眼或不安装电子眼记为F[i]（装）G[i]（不装）

　　　若装电子眼，其子可装亦可不装，即

　　　　F[i]=∑min(F[son],G[son])

　　　若不装电子眼，其子必须装，即

　　　　G[i]=∑F[son]

　　若该题为N个点 N-1条边，则已完毕

　　但该题存在一个环，使得该图不是树

　　处理方法为：将环的一条边删去，强制以这条删去的边所连的两个点为根跑DP（环的判定方法为并查集）

　　注意：答案不能为两个G的最小值，因为此时删去的边不能被监控到

代码如下：

#include<stdio.h>
#include<cstring>
#define N 100001
int n;
int f[N];
int F[N],G[N];//点 不点 
int head[N],nxt[2*N],to[2*N];
int tot=0;
int min(int x,int y){return x<y?x:y;}
void dfs(int p,int from)
{
F[p]++;
    for(int i=head[p];i;i=nxt[i])
    {
        if(to[i]!=from)
        {
        dfs(to[i],p);           
        F[p]+=min(G[to[i]],F[to[i]]);
        G[p]+=F[to[i]];
        }
    }       
      
}
void restart()
{
    for(int i=1;i<=n;i++)
    f[i]=i;
}
int find(int x)
{
    if(f[x]==x)
    return x;
    else
    {
        int fx=find(f[x]);
        return f[x]=fx;
    }
}
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
       
    to[++tot]=x;
    nxt[tot]=head[y];
    head[y]=tot; 
}
int main()
{
    scanf("%d",&n);
    restart();
    int p1,p2;
    for(int i=1;i<=n;i++)
    {   
    int x,y;
    scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            scanf("%d",&y);
            int fi=find(i);
            int fy=find(y);
            if(fi==fy)
            p1=i,p2=y;
            else{
            f[fi]=fy;
            add(i,y);
            }       
        }
    }
    dfs(p1,0);
    int G1=G[p1],F1=F[p1];
    memset(G,0,sizeof(G));
    memset(F,0,sizeof(F));
    dfs(p2,0);
    int G2=G[p2],F2=F[p2];
    int a1=min(G1,F2);
    int a2=min(G2,F1);  
    int ans=min(a1,a2);
    if(a1==G1&&a2==G2)
    ans=min(F1,F2);
    printf("%d",ans);
}