首页 > 代码库 > Gym 101149I I - It's the Police
Gym 101149I I - It's the Police
http://codeforces.com/gym/101149/problem/I
考虑下面这个例子
4 3
1 2
1 3
1 4
应该是选 0 0 1 1这样是最优的,我们不选1号,因为如果选1号作为非法分子点,那么2、3、4也不能有警察了,这不行。
那么究竟选呢?
很明显的一个道理是,选出儿子数最小的那个点,作为非法分子点,那么不放警察的地方就变得小了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 2e5 + 20; vector<int>son[maxn]; bool vis[maxn]; void work() { IOS; int n, m; cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; son[u].push_back(v); son[v].push_back(u); } int mi = inf; int id = inf; for (int i = 1; i <= n; ++i) { if (son[i].size() < mi) { mi = son[i].size(); id = i; } } vis[id] = 1; for (int i = 0; i < son[id].size(); ++i) { vis[son[id][i]] = 1; } for (int i = 1; i <= n; ++i) { printf("%d ", !vis[i]); } } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work(); return 0; }
Gym 101149I I - It's the Police
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。