首页 > 代码库 > URAL 2017 Best of a bad lot 二分图染色 使x集点数最少
URAL 2017 Best of a bad lot 二分图染色 使x集点数最少
题目链接：点击打开链接
题意：
有n个嫌疑犯。[1,n]
第i行表示第i个嫌疑犯说案发时他所在的地名，后面一个数m表示当时他看到m个人，后面m个数表示他看到的人。
找出最小的犯罪团体（即多数人都是好人原则）
若大家都是好人则随便输出一个人当坏人==
思路：
当一个人x被2个不同地方的人u, v看到时，则u v其中一个一定是犯人。
所以u-v建一条边。
然后二分图染色使得x点集点数最少。
先染一个子图，然后把点集少的归成x集就可以了，因为任意两个子图都是互不影响的。
#include<bits/stdc++.h>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if (x>9) pt(x / 10);
putchar(x % 10 + '0');
}
const int N = 450;
vector<int>D[N], G[N];
map<string, int> mp;
int local[N], n;
void input(){
for(int i = 1; i <= n; i++){
D[i].clear(); G[i].clear();
}
mp.clear(); string u; int siz = 1;
for(int i = 1, loc, v; i <= n; i++)
{
cin>>u;
if(mp.count(u)) loc = mp[u];
else mp[u] = loc = siz++;
local[i] = loc;
rd(loc);
while(loc--){
rd(v);
D[v].push_back(i);
}
D[i].push_back(i);
}
}
void build(){
for(int i = 1; i <= n; i++)
for(int j = 0; j < D[i].size(); j++)
for(int k = j + 1; k < D[i].size(); k++)
{
int u = D[i][j], v = D[i][k];
if(local[u]!=local[v])
G[u].push_back(v), G[v].push_back(u);
}
}
int vis[N];
vector<int>col[2], one, ans;
void bfs(int x){
col[0].clear(); col[1].clear();
col[0].push_back(x);
vis[x] = 0;
queue<int>q; q.push(x);
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(vis[v] == -1)
{
vis[v] = !vis[u];
q.push(v);
col[vis[v]].push_back(v);
}
}
}
int mx = col[0].size()<col[1].size()? 0 : 1;
for(int i = 0; i < col[mx].size(); i++)
ans.push_back(col[mx][i]);
}
int main(){
while (~scanf("%d", &n)){
input();
build();
memset(vis, -1, sizeof vis);
ans.clear();
for(int i = 1; i <= n; i++)
if(vis[i] == -1)
bfs(i);
if(ans.size() == 0)ans.push_back(1);
pt(ans.size()); puts("");
for(int i = 0; i < ans.size(); i++)
printf("%d%c", ans[i], i+1==ans.size()? '\n':' ');
}
return 0;
}URAL 2017 Best of a bad lot 二分图染色 使x集点数最少
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。