P1330封锁阳光大学（染色法）-创新互联

题目描述

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

成都创新互联公司从2013年创立，是专业互联网技术服务公司，拥有项目成都网站建设、做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元什邡做网站,已为上家服务,为什邡各地企业和个人服务,联系电话:18982081108

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

输出 #1复制

Impossible

输入 #2复制

3 2
1 2
2 3

输出 #2复制

说明/提示

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

思路：

呜呜呜，这道题我真真真真真真真没啥思路，于是打开了题解看了看大佬们的想法，学到了一个新的方法，染色法，大佬的思路是这样的：

如果一条边两个点一红一蓝，那就是恰好被切断
如此看来，所谓占领和不占领其实是等价的。
只需要分别尝试两种情况（令这个点是红色或者令这个点是蓝色），看看哪种情况中红点数目最少即可。
为什么会Impossible？那是因为，在从第一个点的颜色一直推到所有点的颜色的过程中，有的点会被要求涂上相反的颜色。即当你想把一个点涂成蓝色的时候，却发现它已经是红色了。这就出现无解情况。
连通是个永恒的话题。千万不要忘记对不连通的考虑

看了大佬的代码，我真的佩服的五体投地，于是我照葫芦画瓢+自我理解完成了这道题

代码：

#include
using namespace std;
vectorG[10005];
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://cdxtjz.cn/article/hceco.html

P1330封锁阳光大学（染色法）-创新互联

其他资讯