P1330封锁阳光大学（染色法）-创新互联
曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。
阳光大学的校园是一张由 nn 个点构成的无向图，nn 个点之间由 mm 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。
询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。
输入格式第一行两个正整数，表示节点数和边数。 接下来 mm 行，每行两个整数 u,vu,v，表示点 uu 到点 vv 之间有道路相连。
输出格式仅一行如果河蟹无法封锁所有道路，则输出 Impossible，否则输出一个整数，表示最少需要多少只河蟹。
输入 #1复制
3 3 1 2 1 3 2 3
输出 #1复制
Impossible
输入 #2复制
3 2 1 2 2 3
输出 #2复制
1说明/提示
【数据规模】
对于 100\%100% 的数据，1\le n \le 10^41≤n≤104，1\le m \le 10^51≤m≤105，保证没有重边。
呜呜呜，这道题我真真真真真真真没啥思路，于是打开了题解看了看大佬们的想法，学到了一个新的方法，染色法，大佬的思路是这样的：
- 如果一条边两个点一红一蓝，那就是恰好被切断
- 如此看来，所谓占领和不占领其实是等价的。
- 只需要分别尝试两种情况（令这个点是红色或者令这个点是蓝色），看看哪种情况中红点数目最少即可。
- 为什么会Impossible？那是因为，在从第一个点的颜色一直推到所有点的颜色的过程中，有的点会被要求涂上相反的颜色。即当你想把一个点涂成蓝色的时候，却发现它已经是红色了。这就出现无解情况。
- 连通是个永恒的话题。千万不要忘记对不连通的考虑
看了大佬的代码，我真的佩服的五体投地，于是我照葫芦画瓢+自我理解完成了这道题
代码：
#include
using namespace std;
vector
int f=1;
int flag[10005];//-1为没染色，0为蓝色，1为红色
int ans=0;
int dfs(int s,int d)
{
if(f==0)
{
return 0;
}
else
{
int sum=d;
flag[s]=d;
for(int j=0;j
int y=G[s][j];
if(flag[y]==-1)
{
flag[y]=(!d);//这个写法真的很酷的好吧，爱死了
sum=sum+dfs(y,!d);
}
else if(flag[y]==d)
{
f=0;
}
}
return sum;
}
}
int main()
{
int n,m;
cin>>n>>m;
memset(flag,-1,sizeof(flag));
//图的存储
for(int i=1;i<=m;i=i+1)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
//有可能图不连通（好恶心）
for(int i=1;i<=n;i=i+1)
{
if(flag[i]==-1)
{
//分别涂上红色和蓝色；
int a=dfs(i,0);
memset(flag,-1,sizeof(flag));//实现两次遍历并行不悖
int b=dfs(i,1);
ans=ans+min(a,b);
}
if(f==0)
{
break;
}
}
if(f==0)
{
cout<<"Impossbile"<
else
{
cout< }
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：P1330封锁阳光大学（染色法）-创新互联
当前路径：http://myzitong.com/article/hceco.html