P1418 选点问题
2024-09-02 17:31:37
题目描述
给出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 ;
}
最新文章
- 使用 apache2 + `mod_proxy_uwsgi` + uwsgi + upstart 部署
- Excel标题与索引的对应关系
- [Thinking in Java]这些必须先了解
- ScrollMe – 在网页中加入各种滚动动画效果
- Hp自学整理html
- ASP.NET MVC 快速开发框架之 SqlSugar+SyntacticSugar+JQWidgetsSugar+jqwidgets(转)
- win10无法枚举容器中的对象 访问被拒绝
- 从P6 EPPM 8 R3 到P6 EPPM 16 R1 有哪些改变?
- Python-S13作业-day3-之编辑ha.conf配置文件
- SpringMVC序列化Long转成String
- Select模型原理
- SqlServer 由于未在SqlServer的此实例上安装复制组件解决方法
- NETBSD-DTARCE
- Android中moveTo、lineTo、quadTo、cubicTo、arcTo详解(实例)
- Java语言定义的线程状态分析
- iOS开发必不可少的76个工具
- Android Studio 中修改Apk名称
- Python基础学习参考(六):列表和元组
- [微信小程序]编译.wxss出错,2 not found
- 监听 input上传文件, 获取文件名称,
热门文章
- 重载与重写的区别----https://blog.csdn.net/zhu_apollo/article/details/1852542
- 移动端,input输入获得焦点被键盘遮住简单解决方案
- [A]System.Web.WebPages.Razor.Configuration.HostSection 无法强制转换为 [B]System.Web.WebPages.Razor.Configuration.HostSection。
- MySQL: How to support full Unicode in MySQL databases
- CI 日志类
- TreeView获取目录下的所有文件
- 躁动不安的const
- Linux网络编程:UDP Socket编程范例
- 用C++实现一个Quaternion类
- BestCoder Round #59 (div.2) B. Reorder the Books 想法题