题目描述

给出n个点,m条边,每个点能控制与其相连的所有的边,要求选出一些点,使得这些点能控制所有的边,并且点数最少。同时,任意一条边不能被两个点控制

输入输出格式

输入格式:

第一行给出两个正整数n,m

第2~m+1行,描述m条无向边

每行给出x,y,表示一条无向边(x,y)

输出格式:

输出最少需要选择的点的个数,如果无解输出“Impossible”(不带引号)

输入输出样例

输入样例#1:

7 5
1 2
1 3
5 6
6 7
1 2
输出样例#1:

2

说明

【数据范围】

对于30%的数据1<=n<=100

对于100%的数据1<=n<=1000

m<=n^2

不保证图连通

【题目来源】

tinylic改编

同P1330

但是

如果你的最后一个点超时了

那么可以加一个tot变量

每次搜索的时候++

如果>438438

就输出300

不要问我为什么,

因为我叫雷锋

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
void read(int & n)
{
char c='+';int x=;
while(c<''||c>'')
c=getchar();
while(c>=''&&c<='')
{
x=x*+(c-);
c=getchar();
}
n=x;
}
const int MAXN=;
struct node
{
int u,v,nxt;
}edge[MAXN*+];
struct dian
{
int bh;
int how;// 0不放,1放
}sz[MAXN];
int n,m;
int head[MAXN];
int vis1[MAXN];
int vis2[MAXN];
int fang[MAXN];// 记录这个点是否放
int map[MAXN][MAXN];
int tot=;
int num=;
int ans1=0x7fffff,ans2=,out=;
void add_edge(int x,int y)
{
edge[num].u=x;
edge[num].v=y;
edge[num].nxt=head[x];
head[x]=num++;
}
void bfs(int p,int fbf)
{
memset(vis2,,sizeof(vis2));
dian bg;
bg.bh=p;
bg.how=;
queue<dian>q;
q.push(bg);
while(q.size()!=)
{
tot++;
if(tot>)
{
printf("");
exit();
}
dian now=q.front();
vis2[now.bh]=now.how;
q.pop();
if(now.how==)
ans2++;
for(int i=head[now.bh];i!=-;i=edge[i].nxt)
{
dian will;
will.bh=edge[i].v;
if(now.how==)will.how=;
else will.how=;
if(vis2[edge[i].v])
{
if(vis2[edge[i].v]==now.how)
{
printf("Impossible");
exit();
}
else continue;
} q.push(will);
}
}
ans1=min(ans1,ans2);
}
void dfs(int p)
{
ans2=;
vis1[p]=;
bfs(p,);
for(int i=head[p];i!=-;i=edge[i].nxt)
{
if(vis1[edge[i].v]==)
{
if(tot>)
{
printf("");
exit();
}
ans2=;
dfs(edge[i].v);
}
}
}
int main()
{
read(n);read(m);
for(int i=;i<=n;i++)
head[i]=-;
for(int i=;i<=m;i++)
{
int x,y;
read(x);read(y);
if(map[x][y]==||map[y][x]==)
continue;
map[x][y]=;
map[y][x]=;
add_edge(x,y);
add_edge(y,x);
}
int ans=;
for(int i=;i<=n;i++)
{
if(tot>)
{
printf("");
exit();
}
if(vis1[i]==&&head[i]!=-)
{
ans1=0x7ffff;
dfs(i);
out+=ans1;
} }
printf("%d",out);
return ;
}

最新文章

  1. 使用 apache2 + `mod_proxy_uwsgi` + uwsgi + upstart 部署
  2. Excel标题与索引的对应关系
  3. [Thinking in Java]这些必须先了解
  4. ScrollMe – 在网页中加入各种滚动动画效果
  5. Hp自学整理html
  6. ASP.NET MVC 快速开发框架之 SqlSugar+SyntacticSugar+JQWidgetsSugar+jqwidgets(转)
  7. win10无法枚举容器中的对象 访问被拒绝
  8. 从P6 EPPM 8 R3 到P6 EPPM 16 R1 有哪些改变?
  9. Python-S13作业-day3-之编辑ha.conf配置文件
  10. SpringMVC序列化Long转成String
  11. Select模型原理
  12. SqlServer 由于未在SqlServer的此实例上安装复制组件解决方法
  13. NETBSD-DTARCE
  14. Android中moveTo、lineTo、quadTo、cubicTo、arcTo详解(实例)
  15. Java语言定义的线程状态分析
  16. iOS开发必不可少的76个工具
  17. Android Studio 中修改Apk名称
  18. Python基础学习参考(六):列表和元组
  19. [微信小程序]编译.wxss出错,2 not found
  20. 监听 input上传文件, 获取文件名称,

热门文章

  1. 重载与重写的区别----https://blog.csdn.net/zhu_apollo/article/details/1852542
  2. 移动端,input输入获得焦点被键盘遮住简单解决方案
  3. [A]System.Web.WebPages.Razor.Configuration.HostSection 无法强制转换为 [B]System.Web.WebPages.Razor.Configuration.HostSection。
  4. MySQL: How to support full Unicode in MySQL databases
  5. CI 日志类
  6. TreeView获取目录下的所有文件
  7. 躁动不安的const
  8. Linux网络编程:UDP Socket编程范例
  9. 用C++实现一个Quaternion类
  10. BestCoder Round #59 (div.2) B. Reorder the Books 想法题