JDOJ 1019: 电子眼

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。

属于节点选择类的树形DP，点看边的那种。

所以只需要两个状态：

一个是这个点选，一个是这个点不选。分别转移即可。

至于基环树，针对它的处理，参见：

浅谈基环树

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
int f[N];
int F[N],G[N];
int head[N],nxt[N<<1],to[N<<1];
int tot;
void dfs(int x,int fa)
{
    F[x]++;
    for(int i=head[x];i;i=nxt[i])
        if(to[i]!=fa)
        {
            dfs(to[i],x);           
            F[x]+=min(G[to[i]],F[to[i]]);
            G[x]+=F[to[i]];
        }
}
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        f[i]=i;
    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);
                add(y,i);
            }       
        }
    }
    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);
    return 0;
}