首页 > 代码库 > 洛谷 P1330 封锁阳光大学
洛谷 P1330 封锁阳光大学
题目描述
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在与这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入输出格式
输入格式：
第一行：两个整数N，M
接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。
输出格式：
仅一行：如果河蟹无法封锁所有道路，则输出“Impossible”，否则输出一个整数，表示最少需要多少只河蟹。
输入输出样例
输入样例#1：
【输入样例1】3 31 21 32 3【输入样例2】3 21 22 3
输出样例#1：
【输出样例1】Impossible【输出样例2】1
说明
【数据规模】
1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。
1 /* 2 比较明显的染色问题 3 但是对边染色比较麻烦 4 所以我们换一个角度来考虑 5 先dfs遍历一遍 求出深度 6 再dfs第二遍判断 7 如果染了一个奇数点 那么所有奇数点都染完才能封锁大学 8 偶数同理 9 */10 #include<cstdio>11 #include<vector>12 #include<cstring>13 #include<iostream>14 #define MAXN 1001015 using namespace std;16 vector<int> v[MAXN];17 vector<int> e;18 int n,m,x,y,depth[MAXN],cnt,tot;19 bool vis[MAXN],f;20 inline void read(int&x) {21 x=0;int f=1;char c=getchar();22 while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}23 while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}24 x=x*f;25 }26 inline void dfs(int x) {27 vis[x]=true;28 for(int i=v[x].size()-1;i>=0;i--) {29 int V=v[x][i];30 if(!vis[V]) {31 depth[V]=min(depth[V],depth[x]+1);32 dfs(V);33 }34 }35 return;36 }37 inline void dfs2(int x) {38 if(!f) return;39 if(depth[x]%2) cnt++;40 else tot++;41 for(int i=v[x].size()-1;i>=0;i--) {42 int V=v[x][i];43 if(depth[x]%2==depth[V]%2) {f=false;return;}44 else 45 if(depth[V]>depth[x])46 dfs2(V);47 }48 return;49 }50 int main() {51 read(n);read(m);52 for(int i=1;i<=m;i++) {53 read(x);read(y);54 v[x].push_back(y);55 v[y].push_back(x);56 }57 memset(depth,127/3,sizeof depth);58 depth[1]=0;59 for(int i=1;i<=n;i++) {60 if(!vis[i]) {61 depth[i]=0;62 dfs(i);63 e.push_back(i);64 }65 }66 int ans=0;67 for(int i=e.size()-1;i>=0;i--) {68 int V=e[i];69 f=true;cnt=0;tot=0;70 dfs2(V);71 if(!f) {72 printf("Impossible\n");73 return 0;74 }75 ans=ans+min(tot,cnt);76 }77 printf("%d\n",ans);78 return 0;79 }
洛谷 P1330 封锁阳光大学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。