P1330 封锁阳光大学
2018-06-17 22:24:58来源:未知 阅读 ()
题目描述
曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定封锁阳光大学,不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图,N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁,当某个点被封锁后,与这个点相连的道路就被封锁了,曹就无法在与这些道路上刷街了。非常悲剧的一点是,河蟹是一种不和谐的生物,当两只河蟹封锁了相邻的两个点时,他们会发生冲突。
询问:最少需要多少只河蟹,可以封锁所有道路并且不发生冲突。
输入输出格式
输入格式:第一行:两个整数N,M
接下来M行:每行两个整数A,B,表示点A到点B之间有道路相连。
输出格式:仅一行:如果河蟹无法封锁所有道路,则输出“Impossible”,否则输出一个整数,表示最少需要多少只河蟹。
输入输出样例
【输入样例1】 3 3 1 2 1 3 2 3 【输入样例2】 3 2 1 2 2 3
【输出样例1】 Impossible 【输出样例2】 1
说明
【数据规模】
1<=N<=10000,1<=M<=100000,任意两点之间最多有一条道路。
好吧,表示本蒟蒻不懂什么叫黑白染色,所以题解基本看不懂。。
但是我同时用BFS+DFS也AC了
思路:
因为各个点不一定相连
所以我们枚举一边所有的点,对于每个没有访问过的点跑一边DFS,
在DFS的过程中同时访问与该点相连的点,
然后在每次DFS的过程中进行DFS,
算出在该联通分量中,从该点出发,需要放置的数量
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<queue> 7 using namespace std; 8 void read(int & n) 9 { 10 char c='+';int x=0; 11 while(c<'0'||c>'9') 12 c=getchar(); 13 while(c>='0'&&c<='9') 14 { 15 x=x*10+(c-48); 16 c=getchar(); 17 } 18 n=x; 19 } 20 const int MAXN=10101; 21 struct node 22 { 23 int u,v,nxt; 24 }edge[MAXN*10+101]; 25 struct dian 26 { 27 int bh; 28 int how;// 0不放,1放 29 }sz[MAXN]; 30 int n,m; 31 int head[MAXN]; 32 int vis1[MAXN]; 33 int vis2[MAXN]; 34 int fang[MAXN];// 记录这个点是否放 35 int num=1; 36 int ans1=0x7fffff,ans2=0,out=0; 37 void add_edge(int x,int y) 38 { 39 edge[num].u=x; 40 edge[num].v=y; 41 edge[num].nxt=head[x]; 42 head[x]=num++; 43 } 44 void bfs(int p,int fbf) 45 { 46 memset(vis2,0,sizeof(vis2)); 47 dian bg; 48 bg.bh=p; 49 bg.how=1; 50 queue<dian>q; 51 q.push(bg); 52 while(q.size()!=0) 53 { 54 dian now=q.front(); 55 vis2[now.bh]=now.how; 56 q.pop(); 57 if(now.how==1) 58 ans2++; 59 for(int i=head[now.bh];i!=-1;i=edge[i].nxt) 60 { 61 dian will; 62 will.bh=edge[i].v; 63 if(now.how==1)will.how=2; 64 else will.how=1; 65 if(vis2[edge[i].v]) 66 { 67 if(vis2[edge[i].v]==now.how) 68 { 69 printf("Impossible"); 70 exit(0); 71 } 72 else continue; 73 } 74 75 q.push(will); 76 } 77 } 78 ans1=min(ans1,ans2); 79 } 80 void dfs(int p) 81 { 82 ans2=0; 83 vis1[p]=1; 84 bfs(p,1); 85 for(int i=head[p];i!=-1;i=edge[i].nxt) 86 { 87 if(vis1[edge[i].v]==0) 88 { 89 ans2=0; 90 dfs(edge[i].v); 91 } 92 } 93 } 94 int main() 95 { 96 read(n);read(m); 97 for(int i=1;i<=n;i++) 98 head[i]=-1; 99 for(int i=1;i<=m;i++) 100 { 101 int x,y; 102 read(x);read(y); 103 add_edge(x,y); 104 add_edge(y,x); 105 } 106 int ans=0; 107 for(int i=1;i<=n;i++) 108 { 109 if(vis1[i]==0&&head[i]!=-1) 110 { 111 ans1=0x7ffff; 112 dfs(i); 113 out+=ans1; 114 } 115 116 } 117 printf("%d",out); 118 return 0; 119 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【做题笔记】P1330 封锁阳光大学 2020-02-14
- 洛谷 P5506 封锁 2019-08-16
- 洛谷P1330 封锁阳光大学 2019-08-16
- P1330 封锁阳光大学 DFS+染色 2018-06-27
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