题解 P1330 【封锁阳光大学】

· · 题解

扬中夏令营Day0的晚上练手写一道题。还比较顺利吧...

思路：

这就是个染色问题。把图上的点染成红色和蓝色。要求：同一条边上的两个点颜色不能一样。

解释一下：不妨红色对应河蟹占领而蓝色对应没有占领。

上面两种情况是不行的。

这种情况是可以的。

对吧？

如此看来，所谓占领和不占领其实是等价的。

在一个连通图中，令任意一个点是红色或者蓝色，那么整张图的颜色应该已经确定了。为了让红色的点最少，只需要分别尝试两种情况（令这个点是红色或者令这个点是蓝色），看看哪种情况中红点数目最少即可。

为什么会Impossible？那是因为，在从第一个点的颜色一直推到所有点的颜色的过程中，有的点会被要求涂上相反的颜色。即，当你想把一个点涂成蓝色的时候，却发现它已经是红色了。这就出现无解情况。

在下面的代码里，你会看到一个叫dfs的函数。它的功能是：令i的颜色是s（s∈{0,1}），返回i所在的连通图用了颜色1的点数。

是的。连通是个永恒的话题。千万不要忘记对不连通的考虑。在下面的代码里，我使用了一个循环来解决这个问题。注意被染过色的点不需要继续遍历。

对color2数组的解释：因为我太笨了，实在不知道怎么样才能让dfs(i,0)和dfs(i,1)并行不悖。


#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<set>
using namespace std;

vector<int> g[10000+10];

int color[10000+10];
int color2[10000+10];
int n, m;
bool ok;
int dfs(int i, int s){
    if (!ok) return 0;
    int sum=s;
    color[i]=s;
    for (int j=0; j<g[i].size(); j++){
        int v=g[i][j];
        if (color[v]==-1){
            color[v]=(!s);
            sum+=dfs(v, !s);
        } else if (color[v]==s)  ok=false;

    }

    return sum;
}
int main(){

    cin>>n>>m;
    for (int i=0; i<m; i++){
        int u, v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    memset(color, -1, sizeof(color));
    ok=true;
    int one=0;
    int ans=0;
    for (int i=1; i<=n; i++){
        if (color[i]==-1){
            memcpy(color2, color, sizeof(color));
            int a=dfs(i,0);
            memcpy(color, color2, sizeof(color));
            int b=dfs(i,1);
            ans+=min(a,b);

        }
        if (!ok) break;
    }
    if (!ok){
        cout<<"Impossible"<<endl;
    } else {
        cout<<ans<<endl;
    }

    return 0;
}