P1330 封锁阳光大学

提交 28.00k
通过 9.83k
时间限制 1.00s
内存限制 125.00MB
题目提供者 yeszy
历史分数100

提交记录

查看题解

标签

 
查看算法标签
进入讨论版

相关讨论

 
查看讨论

推荐题目

 
查看推荐
 

展开

题目描述

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由 nnn 个点构成的无向图，nnn 个点之间由 mmm 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

输入格式

第一行两个正整数，表示节点数和边数。 接下来 mmm 行，每行两个整数 u,vu,vu,v，表示点 uuu 到点 vvv 之间有道路相连。

输出格式

仅一行如果河蟹无法封锁所有道路，则输出 Impossible，否则输出一个整数，表示最少需要多少只河蟹。

输入输出样例

输入 #1 
3 3
1 2
1 3
2 3
输出 #1 
Impossible
输入 #2 
3 2
1 2
2 3
输出 #2 
1

说明/提示

【数据规模】
对于 100%100\%100% 的数据，1≤n≤1041\le n \le 10^41≤n≤104，1≤m≤1051\le m \le 10^51≤m≤105，保证没有重边。

 

思路

　　根据题意，显然可以根据染色法来求结果。在每个连通子图里，螃蟹的站位要满足相邻的两个点不能是同色，对不同颜色的点计数，取最小值即可。

CODE

 

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e5 + 7;
 47 
 48 int n, m;
 49 int edge[maxn],head[maxn],nxt[maxn];
 50 int cnt = 0;
 51 int used[maxn];
 52 int sum[5];
 53 int color[maxn];
 54 
 55 void add(int u, int v) {
 56     edge[cnt] = v;
 57     nxt[cnt] = head[u];
 58     head[u] = cnt++;
 59 }
 60 
 61 bool dfs(int u, int cl) {
 62     if(used[u]) {
 63         if(color[u] == cl) {
 64             return true;
 65         }
 66         else {
 67             return false;
 68         }
 69     }
 70     used[u] = 1;
 71     sum[color[u] = cl]++;
 72     bool ok = true;
 73     for (int i = head[u]; ~i; i = nxt[i]) {
 74         int v = edge[i];
 75         ok = ok && dfs(v, 1 - cl);
 76     }
 77     //dbg(ok);
 78     return ok;
 79 }
 80 
 81 int main()
 82 {
 83     memset(head,-1,sizeof(head));
 84     scanf("%d %d",&n, &m);
 85     LL ans = 0;
 86     for(int i = 1; i <= m; ++i) {
 87         int u,v;
 88         scanf("%d %d", &u, &v);
 89         add(u,v),add(v,u);
 90     }
 91     for(int i = 1; i <= n; ++i) {
 92         if(used[i])
 93             continue;
 94         sum[0] = sum[1] = 0;
 95         if(!dfs(i,0)) {
 96             puts("Impossible");
 97             return 0;
 98         }
 99         ans += min(sum[0], sum[1]);
100     }
101     cout << ans << endl;
102 
103     return 0;
104 }
View Code