LA 2038 Strategic game（最小点覆盖，树形dp，二分匹配）

题意即求一个最小顶点覆盖。

对于没有孤立点的图G=(V,E)，最大独立集+最小顶点覆盖= V。（往最大独立集加点）

问题可以变成求树上的最大独立集合。

每个结点的选择和其父节点选不选有关，

dp(u,1)表示父节点选，这时u不可选，

dp(u,0)表示父节点不选，这时u可选可不选。

#include<bits/stdc++.h>

using namespace std;

const int maxn = ;

int meo[maxn][];

int vis[maxn][], clk;

int hd[maxn],nx[maxn<<],to[maxn<<],ec;

void add(int u,int v)

{

    to[ec] = v;

    nx[ec] = hd[u];

    hd[u] = ec++;

}

int dp(int u,int a = ,int f = -)//a表示父节点选不选

{

    if(vis[u][a] == clk) return meo[u][a];

    vis[u][a] = clk;

    int &re = meo[u][a];

    re = ;

    int pick = ;

    for(int i = hd[u]; ~i; i = nx[i]){

        int v = to[i];

        if(v == f) continue;

        if(!a){

            pick += dp(v,,u);

        }

        re += dp(v,,u);

    }

    if(!a) re = max(re,pick);

    return re;

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int n;

    while(~scanf("%d",&n)){

        memset(hd,-,sizeof(hd)); ec = ;

        for(int i = ; i < n; i++){

            int u,sn; scanf("%d:(%d)",&u,&sn);

            while(sn--){

                int v;scanf("%d",&v);

                add(u,v); add(v,u);

            }

        }

        clk++;

        printf("%d\n",n-dp());

    }

    return ;

}

最小点覆盖还可以用二分匹配来做

关键代码，下面可以适合无向图，如果用有向图的算法一个匹配会算两次。

int link[maxn];

int vis[maxn], clk;

bool aug(int u)

{

    if(vis[u] == clk) return false;

    vis[u] = clk;

    for(int i = hd[u]; ~i; i = nx[i]){

        int v = to[i];

        if(!~link[v] || aug(link[v])){

            link[v] = u;

            link[u] = v;

            return true;

        }

    }

    return false;

}

int Hungary(int n)

{

    memset(link,-,sizeof(link));

    int ans = ;

    for(int i = ; i < n; i++){

        if(link[i]<){

            clk++;

            if(aug(i)) ans++;

        }

    }

    return ans;

}

也可以直接dp求最小点覆盖集合，

f[u][p]表示以u为根的树最小点覆盖，p表示选不选u。

当选u的时候，子结点可选可不选，

当不选u的时候，子结点都选。

（实际上存在在某些结点只选一个子节点的最优解的情况，但是这样做并不会丢解）

int f[maxn][],vis[maxn],clk;

void dfs(int u = ,int fa = -)

{

    vis[u] = clk;

    f[u][] = ; f[u][] = ;

    for(int i = hd[u]; ~i; i = nx[i]){

        int v = to[i];

        if(v == fa) continue;

        if(vis[v] != clk) dfs(v,u);

        f[u][] += min(f[v][],f[v][]);

        f[u][] += f[v][];

    }

}

巴特西

LA 2038 Strategic game（最小点覆盖，树形dp，二分匹配）

最新文章

热门文章