【做题笔记】P1330 封锁阳光大学
2020-02-14 16:01:42来源:博客园 阅读 ()
【做题笔记】P1330 封锁阳光大学
读题易得:对于有边的两个点 \(u,v\) ,能且仅能其中一点对这条边进行封锁。
什么意思呢?假设给这张图上的点进行染色,那么对于上述的两个点 \(u,v\) ,\(u,v\) 必须异色(理解这一点很重要)。
那么,也就是说,在这张图上,如果要把这张图“完全封锁”且两只河蟹不能封锁相邻的两个点,换而言之,把连接一条边的两个点染色,这两个点是异色的,那么整张图上无非也就这两种颜色,答案无非也就是这两种颜色中数目较少那一种的数目。
注意到存在无解的情况,那么是么时候无解呢?想一下,遍历这张图,那么肯定会遇到做过的点。把我们自己想成河蟹,那么重复来到这时相当于给这个点重新染色。 如果我们携带的“颜料”和上一只河蟹是一样的,那么相当于什么都不做;但如果不同,相当于对这个点重新封锁,这就产生了冲突。所以,这时不合法,返回 0 。否则返回 1 。
请注意:这个图可能不是联通的,所以需要设 vis
数组,判断某个点有没有用过,去遍历所有的小连通图。
参考代码:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m,vis[4000010],c[3],head[4000010],tot,_color[4000010];
//_color[u]代表第 u 个点的颜色
//c[]记录两种颜色的数量
struct node
{
int to,nxt;
};
node G[400010];
inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void add(int u,int v)
{
G[++tot]=(node){v,head[u]},head[u]=tot;
G[++tot]=(node){u,head[v]},head[v]=tot;
}
int dfs(int u,int cor)
{
if(vis[u])
{
if(_color[u]==cor)return 1;
return 0;
}
vis[u]=1;
c[_color[u]=cor]++;
int can_do=1;
for(int i=head[u];i&&can_do;i=G[i].nxt)can_do=can_do&&dfs(G[i].to,1-cor);
return can_do;
}
int main()
{
int ans;
n=read(),m=read();
for(int i=1;i<=m;i++){int u=read(),v=read();add(u,v);}
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
c[0]=c[1]=0;
if(dfs(i,0)==0){cout<<"Impossible"<<endl;return 0;}
ans+=min(c[0],c[1]); //注意,这里是加上
}
cout<<ans<<endl;
return 0;
}
原文链接:https://www.cnblogs.com/Nicest1919/p/12309303.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- C++基础 学习笔记五:重载之运算符重载 2020-04-23
- C++基础 学习笔记四:重载之函数重载 2020-04-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash