【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大佬。

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

但是，仅仅做非重的情况是不行的，考虑如下图例子：

在上图中，非重最小链覆盖的一种最优解为：

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。
如下图，黑边为直接相连边，红边为间接向连边。
第一个图为处理非重最小链覆盖的二分图，第二个图为可重。

这样建图后，对于每个点，它能走到的点在它被选后，都不能选了（十分简明）。

代码

#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);
}