CH6902 Vani和Cl2捉迷藏-布布扣-bubuko.com

描述

Vani和cl2在一片树林里捉迷藏。这片树林里有N座房子，M条有向道路，组成了一张有向无环图。N≤200，M≤30000。
树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。如果从房子A沿着路走下去能够到达B，那么在A和B里的人是能够相互望见的。
现在cl2要在这N座房子里选择K座作为藏身点，同时Vani也专挑cl2作为藏身点的房子进去寻找，为了避免被Vani看见，cl2要求这K个藏身点的任意两个之间都没有路径相连。
为了让Vani更难找到自己，cl2想知道最多能选出多少个藏身点。

输入格式

输入数据的第一行是两个整数N和M。接下来M行，每行两个整数 x,y，表示一条从 x 到 y 的有向道路。

输出格式

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

在第二行输出 K 个空格分开的整数，表示选择的藏身点编号。如果有多个方案，输出任意一个即可。编号的输出顺序任意。

样例输入

样例输出

3
1 3 7

数据范围与约定

对于20% 的数据，N≤10，M<=20。
对于60% 的数据, N≤100，M<=1000。
对于100% 的数据，N≤200，M<=30000，1<=x,y<=N。

本题校验器(SPJ)

01#include <iostream>
02#include <cstdio>
03#include <cstring>
04#include <algorithm>
05#include <vector>
06using namespace std;
07//一些定义
08const int ACCEPT = 0;
09const int WRONG_ANSWER = 1;
10//fstd 标准输出 fout 选手输出 fin 标准输入
11FILE *fstd,*fout,*fin;
12int n, m, ans, val;
13bool v[210], f[210];
14vector<int> ver[210];
15 
16bool dfs(int x) {
17    f[x] = 1;
18    if (v[x]) return true;
19    for (int i = 0; i < ver[x].size(); i++) {
20        int y = ver[x][i];
21        if (f[y]) continue;
22        if (dfs(y)) return true;
23    }
24    return false;
25}
26 
27//执行比较操作。
28bool DoCompare(){
29    fscanf(fin, "%d%d", &n, &m);
30    for (int i = 1; i <= m; i++) {
31        int x, y;
32        fscanf(fin, "%d%d", &x, &y);
33        ver[x].push_back(y);
34    }
35    fscanf(fstd, "%d", &ans);
36    fscanf(fout, "%d", &val);
37    // 答案不对 
38    if (val != ans) return false;
39    for (int i = 1; i <= ans; i++) {
40        int x; fscanf(fout, "%d", &x);
41        // 输出的藏身点不合法或有重复 
42        if (x < 1 || x > n || v[x]) return false;
43        v[x] = 1;
44    }
45    for (int i = 1; i <= n; i++) {
46        if (!v[i]) continue;
47        memset(f, 0, sizeof(f));
48        v[i] = 0;
49        // 能看到别的点 
50        if (dfs(i)) return false;
51        v[i] = 1;
52    }
53    return true;
54}
55 
56int main(int argc, char* argv[])
57{
58    if(argc!=4){
59        printf("参数不足 %d",argc);
60        return -1;
61    }
62 
63    //打开文件
64    if(NULL==(fstd=fopen(argv[1],"r"))){
65        return -1;
66    }
67    if(NULL==(fout=fopen(argv[2],"r"))){
68        return -1;
69    }
70    if(NULL==(fin=fopen(argv[3],"r"))){
71        return -1;
72    }
73 
74    if(DoCompare()){
75        return ACCEPT;
76    }else{
77        return WRONG_ANSWER;
78    }
79}

藏身点个数等于最小路径可重复点覆盖包含的路径条数。只需传递闭包，拆点跑二分图最大匹配，用点数减去它就行了。

CH6902 Vani和Cl2捉迷藏

6902 Vani和Cl2捉迷藏 0x60「图论」例题

描述