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