首页 > 代码库 > P1418 选点问题（黑白染色）
P1418 选点问题（黑白染色）
P1418 选点问题
题目描述
给出n个点，m条边，每个点能控制与其相连的所有的边，要求选出一些点，使得这些点能控制所有的边，并且点数最少。同时，任意一条边不能被两个点控制
输入输出格式
输入格式：
第一行给出两个正整数n，m
第2~m+1行，描述m条无向边
每行给出x,y，表示一条无向边(x,y)
输出格式：
输出最少需要选择的点的个数，如果无解输出“Impossible”（不带引号）
输入输出样例
输入样例#1：
7 51 21 35 66 71 2
输出样例#1：
2
说明
【数据范围】
对于30%的数据1<=n<=100
对于100%的数据1<=n<=1000
m<=n^2
不保证图连通
【题目来源】
tinylic改编
黑白染色问题，与封锁阳光大学一样，代码都没改一改。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 const int MAXN = 10100; 6 struct Edge{ 7 int to,nxt; 8 }e[200100]; //双向边乘2 9 int col[MAXN],head[MAXN];10 bool vis[MAXN],flag = true; 11 int n,m,cnt,ans,ans1,ans2;12 13 void add(int u,int v)14 {15 ++cnt;16 e[cnt].to = v;17 e[cnt].nxt = head[u];18 head[u] = cnt;19 }20 21 void dfs(int u,int c)22 {23 vis[u] = true;24 if (c==1) col[u]=2, ans2++;25 else if (c==2) col[u] = 1, ans1++;26 for (int i=head[u]; i; i=e[i].nxt)27 {28 int v = e[i].to;29 if (vis[v]) //不能写成if(vis[i]&&col[u]==col[v]),影响到else的执行 30 {31 if (col[v]==col[u])32 flag = false;33 }34 else dfs(v,col[u]);35 }36 }37 int main()38 {39 scanf("%d%d",&n,&m);40 for (int x,y,i=1; i<=m; ++i)41 {42 scanf("%d%d",&x,&y);43 add(x,y);44 add(y,x);45 }46 for (int i=1; i<=n; ++i)47 if (!vis[i])48 {49 ans1 = ans2 = 0;50 dfs(i,1);51 if (flag) ans += min(ans1,ans2);52 else break;53 }54 if (flag) printf("%d",ans);55 else printf("Impossible");56 return 0;57 }
P1418 选点问题（黑白染色）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。