COCI2014/2015 Contest#1 D MAFIJA【基环树最大独立点集】

T1725 天黑请闭眼

Online Judge：COCI2014/2015 Contest#1 D MAFIJA（原题）

Label：基环树，断环+树形Dp，贪心+拓扑

题目描述

最近天黑请闭眼在 C国十分流行！游戏里有两个身份,一个是杀手，另一个是平民。杀手知道哪些人是杀手，而平民对此一无所知。现在为了知道谁是杀手，参与游戏的每个人都指证了一个人为杀手，可以确定的是，杀手一定会指证平民，而平民指证的人有可能是杀手，也有可能是平民。给出每位玩家指证的人,请找出游戏中最多可能的杀手个数。

输入

第一行包括一个整数N,表示玩家个数.玩家分别被编号为1~N.

接下来N行,每行一个整数，其中第K行的数表示编号为K的玩家所指证为杀手的玩家编号。

对每组测试点输出一行，如果满足条件输出Yes否则输出No。

输出

输出仅一行，表示最多可能的杀手个数。

样例

Input

Output

Hint

100%的数据 N<=500000.

题解

虽然题目给的是有向边，但其实相当于双向边。且对于边\((u,v)\)，只需要保证两者间至多只有一个杀手。

证明：

对于有向边u->v，根据题意只存在以下取法\((u=1,v=0)，(u=0,v=1)，(u=0,v=0)\)；

对于有向边v->u，类似的只存在以下取法\((v=0,u=1),(v=0,u=0),(v=1,u=0)\)

整理分析得，不论该边方向如何，相连的两点间最多只能取1个杀手。

题目就变成了求基环树上的最大独立集。

做法一

联想起一道类似的经典树形Dp题目——没有上司的舞会.

相比，这道题是一棵基环树，多了一个环，而且图也可能不连通。但有一个重要的发现：每个连通的块内，都有且仅有一个环。

考虑基环树的常见套路——断环，然后转为树形问题解决。

Q1:怎么断环？

利用并查集维护点与点的连通情况，把合并前就已经在同一集合的边记录下来。到时候dfs时，避开这条边即可。

Q2:断环后怎么搞？

断环后就形成了一棵普通的树，直接树形Dp即可（就是上面那道的做法）。但注意，我们记录的断掉的边\((u,v)\)这两者不能同时取杀手。如何较方便的解决？直接分别以\(u,v\)为树根dfs两遍即可，最后将\(max(dp[u][0],dp[v][0])\)累计到答案（因为可能会有多个连通的块）。

整个算法的时间复杂度为\(O(N)\)。

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

inline int read(){

    int x=0;char c=getchar();

    while(c<'0'||c>'9')c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();

    return x;

}

struct edge{

	int to,nxt;

}e[2*N];

int n,head[N],cnt;

inline void link(int u,int v){

	e[++cnt].to=v,e[cnt].nxt=head[u];

	head[u]=cnt;

}

int tot,fa[N],u[N],v[N],id[N];

inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int dp[N][2];

void dfs(int x,int f,int ban){

	dp[x][0]=0,dp[x][1]=1;

	for(int i=head[x];i;i=e[i].nxt){

		int y=e[i].to;

		if(y==f||i==ban||i==ban-1)continue;

		dfs(y,x,ban);

		dp[x][0]+=max(dp[y][0],dp[y][1]);

		dp[x][1]+=dp[y][0];

	}

}

int main(){

	n=read();

	for(int i=1;i<=n;i++)fa[i]=i;

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

		int to=read();

		link(i,to);link(to,i);

		int A=find(i),B=find(to);

		if(A==B){//去除环上的某条边

			u[++tot]=i,v[tot]=to,id[tot]=2*i;

		}

		else fa[A]=B;

	}

	int ans=0;

	for(int i=1;i<=tot;i++){

		dfs(u[i],0,id[i]);

		int tmp1=dp[u[i]][0];

		dfs(v[i],0,id[i]);

		int tmp2=dp[v[i]][0];

		ans+=max(tmp1,tmp2);

	}

	printf("%d\n",ans);

}

做法二

关于求基环树(也适用于普通树)上的最大独立点集（不带权值），有这样一个贪心方案。

对于某个入度为0的点\(x\)（这里我们重新将边视作单向边），它指向\(to[x]\)，那么显然是将\(to[x]\)染黑较优，所以可以用类似拓扑的dfs去给点打标记，最后计个数。

#include<bits/stdc++.h>

using namespace std;

const int N=500010;

int n,ans=0,to[N],ing[N];

bool mark[N];

void dfs(int x,int w){

	if(mark[x])return;

	mark[x]=1;

	if(w)ans++;

	ing[to[x]]--;

	if(ing[to[x]]==0||w==1)dfs(to[x],!w);

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%d",&to[i]),ing[to[i]]++;

	for(int i=1;i<=n;i++)if(!ing[i])dfs(i,1);

	for(int i=1;i<=n;i++)if(!mark[i])dfs(i,0);

	printf("%d\n",ans);

}

两者的时间复杂度都是\(O(N)\)的，但相较之下第一种断环+树形dp的做法更具推广性，适用于点带权的情况——比如下面几道题:

[ZJOI2008]骑士

HDU4830 Party

巴特西

COCI2014/2015 Contest#1 D MAFIJA【基环树最大独立点集】

T1725 天黑请闭眼

题目描述

输入

输出

样例

题解

做法一

做法二

最新文章

热门文章