小C的独立集

wjh15101051's space

卧薪尝胆，厚积薄发。

小C的独立集

Date: Sat Dec 01 08:28:49 CST 2018

In Category: NoCategory

Description：

求一个边仙人掌的最大独立集。

$1\leqslant n\leqslant 50000$

Solution：

像SHOI仙人掌图那样用一个类似 $tarjan$ 的做法，跳过环上的 $DP$ ，只 $DP$ 子树，然后把环找出来做一遍ZJOI骑士那样的序列 $DP$ 就行了。

注意在环上只进入不转移，即：


void dp(int k)

{

	dfn[k] = low[k] = ++tot;

	f[k][1] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		if(dfn[e[i].to] == 0)

		{

			fa[e[i].to] = k;

			dp(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

			if(low[e[i].to] > dfn[k])

			{

				f[k][0] += max(f[e[i].to][0],f[e[i].to][1]);

				f[k][1] += f[e[i].to][0];

			}

		}

		else

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		if(fa[e[i].to] != k && dfn[e[i].to] > dfn[k])

		{

			solve(e[i].to,k);

		}

	}

	return;

}

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define MAXM 60010

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int f[MAXN][2],g[MAXN][2];

int fa[MAXN];

int circ[MAXN];

void solve(int ed,int rt)

{

	circ[0] = 0;

	for(int i = ed;i != fa[rt];i = fa[i])circ[++circ[0]] = i;

	int l = circ[0];

	int ans0,ans1;

	g[circ[1]][0] = f[circ[1]][0];

	g[circ[1]][1] = f[circ[1]][1];

	for(int i = 2;i <= l;++i)

	{

		g[circ[i]][0] = max(g[circ[i - 1]][0],g[circ[i - 1]][1]) + f[circ[i]][0];

		g[circ[i]][1] = g[circ[i - 1]][0] + f[circ[i]][1];

	}

	ans0 = g[circ[l]][0];

	g[circ[l]][0] = f[circ[l]][0];

	g[circ[l]][1] = f[circ[l]][1];

	for(int i = l - 1;i >= 1;--i)

	{

		g[circ[i]][0] = max(g[circ[i + 1]][0],g[circ[i + 1]][1]) + f[circ[i]][0];

		g[circ[i]][1] = g[circ[i + 1]][0] + f[circ[i]][1];

	}

	ans1 = g[circ[1]][0];

	f[rt][0] = ans0;f[rt][1] = ans1;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

void dp(int k)

{

	dfn[k] = low[k] = ++tot;

	f[k][1] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		if(dfn[e[i].to] == 0)

		{

			fa[e[i].to] = k;

			dp(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

			if(low[e[i].to] > dfn[k])

			{

				f[k][0] += max(f[e[i].to][0],f[e[i].to][1]);

				f[k][1] += f[e[i].to][0];

			}

		}

		else

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		if(fa[e[i].to] != k && dfn[e[i].to] > dfn[k])

		{

			solve(e[i].to,k);

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dp(1);

	cout << max(f[1][0],f[1][1]) << endl;

	return 0;

}

In tag: DP-仙人掌DP

wjh15101051