洛谷P1330 封锁阳光大学

题目描述

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

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

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

输入输出格式

输入格式

第一行：两个整数N，M

接下来M行：每行两个整数A，B，表示点A到点B之间有道路相连。

输出格式

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

INPUT & OUTPUT’s examples

Input’s eg #1

Output’s eg #1

1	Impossible

Input’s eg #2

1
2
3

3 2
1 2
2 3

Output’s eg #2

分析

绝对的一道搜索好题，乍一看似乎无法下手，但我们仔细思考一下，代码还是很好写的。

直接枚举肯定枚举不完（这就是暴力比正解更难写的原因），因为方案很多。

首先显然这是一张不连通的图，所以我们把它拆成几个连通子图分别处理。

那么我们再读一遍题，把题目中两个重要的条件抽象的分析一遍。

1、每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了。

2、当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

把它抽象成图的概念：

那么也就是说，要使得每一条边都被封锁：

每一条边相连的两个点中，至少有一个被选中。
每一条边相连的两个点中，不能同时被选中。

那么可以推断出一个结论：

每一条边连接的两个点中，有且只有一个会被选中。

因为我们把整一张图拆成几个连通子图，可以考虑染色法，即把相邻的点都染成不同的颜色。

可以得出，在一张连通图上，只有三种染色结果，要么染成一种颜色，要么染成另一种颜色，要么就是impossible。

那么，我们对于每一张连通子图染一遍色，最后加起来取min即可。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<string>
#include<algorithm>
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
using namespace FastIO;
/* definitions */
const int MAXN = 1e6+10;
int n,m,cnt;
struct Node{
	int next,to;
};
Node Sun[MAXN];
int head[MAXN],Color[MAXN],num[2];
bool visited[MAXN];
/* functions */
inline int min(int a,int b){
	return (a>b)?b:a;
}
inline void Add_Edge(int from,int to){
	Sun[++cnt].to=to;
	Sun[cnt].next=head[from];
	head[from]=cnt;
}
inline bool DFS(int p,int color){
	if(visited[p]){
		if(Color[p]==color)return true;
		return false;
	} 
	visited[p]=true;
	num[Color[p]=color]++;
	bool ans=true;
	for(int i=head[p];i!=0&&ans;i=Sun[i].next){
		ans=ans&&DFS(Sun[i].to,1-color);
	}
	return ans;
}
inline void INIT(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		Add_Edge(a,b);
		Add_Edge(b,a);
	}
}
inline void work(){
	return;
}
int main(int argc,char *argv[]){
	work();
	INIT();
	int res=0;
	for(int i=1;i<=n;i++){
		if(visited[i])continue;
		num[0]=num[1]=0;
		if(!DFS(i,0)){
			printf("Impossible\n");
			return 0;
		} 
		else{
			res+=min(num[1],num[0]);
		}
	}
	printf("%d\n",res);
	return 0;
}

洛谷P1330题解