【JZOJ】3423. Vani和Cl2捉迷藏

Description

Time Limits: 1000 ms Memory Limits: 262144 KB
vani和cl2在一片树林里捉迷藏……

这片树林里有N座房子,M条有向道路,组成了一张有向无环图。

树林里的树非常茂密,足以遮挡视线,但是沿着道路望去,却是视野开阔。如果从房子A沿着路走下去能够到达B,那么在A和B里的人是能够相互望见的。

现在cl2要在这N座房子里选择K座作为藏身点,同时vani也专挑cl2作为藏身点的房子进去寻找,为了避免被vani看见,cl2要求这K个藏身点的任意两个之间都没有路径相连。

为了让vani更难找到自己,cl2想知道最多能选出多少个藏身点?

Input

第一行两个整数N,M。

接下来M行每行两个整数x、y,表示一条从x到y的有向道路。

Output

一个整数K,表示最多能选取的藏身点个数。

Sample Input

4 4

1 2

3 2

3 4

4 2

Sample Output

2

Data Constraint

对于20% 的数据,N≤10,M<=20。

对于60% 的数据, N≤100,M<=1000。

对于100% 的数据,N≤200,M<=30000,1<=x,y<=N。

思路

初读题,没啥思路,以为是图论瞎搞题,开始回想学过的各种图论知识。

(几个小时过去了。。。。)

引入最小链覆盖:

从有向无环图(DAG)中选出若干点不相交的链,使得这些链覆盖所有的点,并且链的条数最小。链的定义是一条连续路径,并且不经过重复的点。

设没有用到的边是黑色边,用到的边是彩色边。那么一条彩色边对应一个连出去的点。由于链的个数是没有连出去的点的数量,因此我们只需要最大化彩色边个数a。答案即是n-a。

建立两个n个点的点集X和Y,如果原图中存在一条边A->B,就在X中的A向Y中的B连边,跑最大匹配就能找到最大彩色边个数。这是对的,是因为X中对应的是只有一条边连出去,而Y对应的是只有一条边连过来。因此一个点最多连进去一次,连出去一次。

以上已经很详尽的描述了非重(即不相交的情况下)的最小链覆盖的如何做。
感谢pechpo大佬。

很明显这道题就是在最小链覆盖的情况下,在每条链上任挂一个点。

但是,仅仅做非重的情况是不行的,考虑如下图例子:
【JZOJ】3423. Vani和Cl2捉迷藏
在上图中,非重最小链覆盖的一种最优解为:

1:1->3->4->6;
2:2;
3:5;

然而,可重最小链覆盖的一种最优解为:

1:1->3->4->6
2:2->3->4->5

即问题转化为将非重最小链覆盖变为可重最小链覆盖。
考虑N很小(N<=200),且无环,可以预处理出各个点的联通关系。
对于两个点i,j。若i能走到j,则在二分图中X部i连向Y部j。
如下图,黑边为直接相连边,红边为间接向连边。
第一个图为处理非重最小链覆盖的二分图,第二个图为可重。
【JZOJ】3423. Vani和Cl2捉迷藏

【JZOJ】3423. Vani和Cl2捉迷藏
这样建图后,对于每个点,它能走到的点在它被选后,都不能选了(十分简明)。

代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=205;
int N,M,cnt,Ans,t[MAXN][MAXN];
int vis[MAXN*2],match[MAXN*2];
vector<int>P[MAXN];
int dfs(int u){
	int size=P[u].size();cnt++;
	for(int i=0;i<size;i++){
		int v=P[u][i];
		if(vis[v])continue;
		vis[v]=1;dfs(v);
		for(int j=1;j<=N;j++)
			t[u][j]=max(t[u][j],t[v][j]);
	}
}
void Init(){
	for(int i=1;i<=N;i++){
		int size=P[i].size();
		for(int j=0;j<size;j++)
			t[i][P[i][j]]=1;
	}
	while(cnt!=N){
		int Root=0;
		for(int i=1;i<=N;i++)
			if(!vis[i]){Root=i;break;}
		vis[Root]=1;dfs(Root);
	}
	for(int i=1;i<=N;i++)P[i].clear();
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			if(t[i][j])P[i].push_back(j+N);
	memset(vis,0,sizeof(vis));
}
int Dfs(int u){
	int size=P[u].size();
	for(int i=0;i<size;i++){
		int v=P[u][i];
		if(vis[v])continue;
		vis[v]=1;
		if(match[v]==-1||Dfs(match[v])){
			match[v]=u;
			match[u]=v;
			return 1;
		}
	}
	return 0;
}
int main(){
	scanf("%d%d",&N,&M);
	for(int i=1,x,y;i<=M;i++){
		scanf("%d%d",&x,&y);
		P[x].push_back(y);
	}
	Init();
	memset(match,-1,sizeof(match));
	for(int i=1;i<=N;i++){
		memset(vis,0,sizeof(vis));
		Ans+=Dfs(i);
	}
	printf("%d\n",N-Ans);
}
上一篇:“快的打车”创始人陈伟星的新项目招人啦,高薪急招Java服务端/Android/Ios 客户端研发工程师/ mysql DBA/ app市场推广专家,欢迎大家加入我们的团队! - V2EX


下一篇:vue 之 用Element ui 写一个简单的后台界面