首页 > 代码库 > luogu P1418 选点问题
luogu 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改编
黑白染色，有多个联通块
#include<cstdio>#include<queue>#include<cstdlib>using namespace std;#define N 100003struct node{ int v,next;}edge[N*10];int head[N],n,m;int num=0;int vis[N];void add_edge(int x,int y){ edge[++num].v=y,edge[num].next=head[x];head[x]=num;}int ans,ans1,ans2;void dfs(int x){ if(vis[x]==1)ans1++; else if(vis[x]==2)ans2++; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].v; if(vis[x]==vis[v]) { puts("Impossible");exit(0); } if(!vis[v]) { vis[v]=3-vis[x]; dfs(v); } }}int main(){ scanf("%d%d",&n,&m); int a,b; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } for(int i=1;i<=n;i++) { if(!vis[i]) { vis[i]=1; ans1=ans2=0; dfs(i); ans+=min(ans1,ans2); } } printf("%d\n",ans); return 0;}
luogu P1418 选点问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。