洛谷P1330 封锁阳光大学(二分图染色)
2024-09-08 01:41:03
P1330 封锁阳光大学
题目描述
曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图,N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,曹就无法在与这些道路上刷街了。非常悲剧的一点是,河蟹是一种不和谐的生物,当两只河蟹封锁了相邻的两个点时,他们会发生冲突。
询问:最少需要多少只河蟹,可以封锁所有道路并且不发生冲突。
输入输出格式
输入格式:
第一行:两个整数N,M
接下来M行:每行两个整数A,B,表示点A到点B之间有道路相连。
输出格式:
仅一行:如果河蟹无法封锁所有道路,则输出“Impossible”,否则输出一个整数,表示最少需要多少只河蟹。
输入输出样例
输入样例#1:
【输入样例1】
3 3
1 2
1 3
2 3 【输入样例2】
3 2
1 2
2 3
输出样例#1:
【输出样例1】
Impossible 【输出样例2】
1
说明
【数据规模】
1<=N<=10000,1<=M<=100000,任意两点之间最多有一条道路。
/*
暴力二分图染色
我写的dfs 分层染色
最后统计答案 两种颜色的较小值
注意 可能不是连通图
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100100 using namespace std;
int n,m,cnt,num,ans;
int head[maxn],col[maxn],tot[maxn],vis[maxn];
struct node
{
int u,v,next;
}e[maxn<<]; inline int init()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} inline void add(int u,int v)
{
e[++num].v=v;
e[num].next=head[u];
head[u]=num;
} bool dfs(int now,int c)
{
vis[now]=true;col[now]=c;tot[c]++;
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].v;
if(vis[v]&&col[v]==col[now]) return false;
else if(!vis[v])
{
bool flag=dfs(v,(c+)&);
if(!flag) return false;
}
}
return true;
} int main()
{
int x,y;
n=init();m=init();
for(int i=;i<=m;i++)
{
x=init();y=init();
add(x,y);add(y,x);
}
for(int i=;i<=n;i++)
{
if(!vis[i])
{
tot[]=tot[]=;
int flag=dfs(i,);
if(!flag)
{
printf("Impossible\n");
return ;
}
else ans+=min(tot[],tot[]);
}
}
printf("%d\n",ans);
return ;
}
最新文章
- maven权威指南学习笔记(二)&mdash;&mdash;安装、运行、获取帮助
- 使用Enyim.Caching访问阿里云的OCS
- MySQL 创建用户 与 授权
- Maximum Value(哈希)
- 安装linux操作系统--浪潮服务器
- Android常用系统广播
- Hibernate 中createQuery与createSQLQuery
- LightOJ_1038 Race to 1 Again
- 使用shell/python获取hostname/fqdn释疑(转)
- php学习笔记——文件(1)
- Android开发艺术2之Activity的启动模式
- 关于理解python类的小题
- access denied for user &#39;root&#39;@&#39;localhost&#39;(using password:YES) FOR WINDOWS
- AOP统一处理Web请求日志
- OO第一次blog
- spring cloud 实践之hystrix注意事项
- Realtime Multi-Person 2D Pose Estimation using Part Affinity Fields(翻译)
- JavaBean 和 pojo 的区别
- file: /SourceCache/IOKitUser_Sim/IOKitUser-920.1.11/hid.subproj/IOHIDEventQueue.c, line: 512
- Struts在Web.xml中的配置及Struts1和Struts2的区别
热门文章
- TestNG套件测试(二)
- ubuntu中mysql忘记密码如何修改
- fiddler培训
- git 连接github.com 并配置密钥
- Mac安装virtualwrapper时报错No module named virtualenvwrapper
- vue中axios设置
- reading/writing files in Python
- led1,1s取反,led2计数10次取反
- 洛谷 2048 BZOJ 2006 [NOI2010]超级钢琴
- 利用tempalte.js模版引擎渲染页面,作对应的数据处理