P1330 封锁阳光大学 DFS+染色
2018-06-27 09:42:44来源:博客园 阅读 ()
题目链接:https://www.luogu.org/problemnew/show/P1330
这个题有意思,如果能想到染色,就会很简单,但若想不到就很麻烦
要想把一条边封锁,就必须且只能占据这条边连接的两个点中的一个,于是,使用两种颜色进行染色,使相邻的两个点的颜色不同,
如果从一个点出发染色,还能再回到这个点,并且染的颜色与第一次染的颜色不同,就意味着无法封锁所有道路
如果可以,所有同一种颜色的位置表示一种河蟹的分布方法,也就是说在图中同时有两种分布方法,我们选择其中染色数少的那一种
如果图不是连通的,那在每一次DFS时,需要重置染色数
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 10005; 4 vector<int> G[maxn]; 5 int used[maxn]; 6 int col[maxn]; 7 int white,black; 8 9 bool dfs(int t,int color){ 10 if(used[t]){ 11 if(color == col[t]) 12 return true; 13 else 14 return false; 15 } 16 else{ 17 used[t] = 1; 18 col[t] = color; 19 if(color) 20 black++; 21 else 22 white++; 23 bool ans = true; 24 for(int i=0;i<G[t].size();++i){ 25 ans = dfs(G[t][i],1-color); 26 if(!ans) 27 break; 28 } 29 return ans; 30 } 31 } 32 33 int main() 34 { 35 int n,m,sum = 0; 36 cin>>n>>m; 37 for(int i=0;i<m;++i){ 38 int a,b; 39 cin>>a>>b; 40 G[a].push_back(b); 41 G[b].push_back(a); 42 } 43 bool ans; 44 for(int i=1;i<=n;++i){ 45 white = black = 0; 46 if(!used[i]) 47 ans = dfs(i,0); 48 if(!ans) 49 break; 50 sum += min(white,black); 51 } 52 if(!ans) 53 cout<<"Impossible"; 54 else 55 cout<<sum; 56 return 0; 57 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【做题笔记】P1330 封锁阳光大学 2020-02-14
- 洛谷 P5506 封锁 2019-08-16
- 洛谷P1330 封锁阳光大学 2019-08-16
- P1330 封锁阳光大学 2018-06-17
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