(luogu1330)封锁阳光大学

发表于 | 分类于 ，

思路:

由题意易得, 只有给出的图是二分图时才有解

若该图为二分图, 将所有河蟹放在二分图的某一侧即可封锁全部道路

每次给二分图染色后将答案加上本次染色点最少一侧的点数

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
using namespace std;
const int Mn(10050),Mm(100050);
inline int _min(int x,int y) { return x<y ? x : y; }
struct edge
{
    int e,nt;
}ed[Mm<<1]; //边表
int vs[Mn],ec(0);
void adde(int s,int e)  //加边
{
    ed[++ec].e=e; ed[ec].nt=vs[s];
    vs[s]=ec;
    ed[++ec].e=s; ed[ec].nt=vs[e];
    vs[e]=ec;
}
int cnc[3],col[Mn]; //某个颜色一侧的点数, 被染成的颜色(0代表未染色)
bool dfs(int x,int c) //二分图染色
{
    col[x] = c; ++cnc[c];
    for(int i(vs[x]);i;i=ed[i].nt)
    {
        edge& e(ed[i]);
        if(col[e.e]==c) return false; //如果边的两端颜色相同则表明该图不是二分图
        if(!col[e.e] && !dfs(e.e,3-c))   return false;
    }
    return true;
}
int main()
{
    int n,m;  //如题
    scanf("%d%d",&n,&m);
    for(int i(1);i<=m;++i)
    {
        int si,ei;  //边的两端点
        scanf("%d%d",&si,&ei);
        adde(si,ei);
    }
    int ans(0),isa(1);  //答案, 是否有解
    for(int i(1);i<=n;++i)
        if(!col[i])
        {
            cnc[1] = cnc[2] = 0;
            if(dfs(i,1))
                ans += _min(cnc[1],cnc[2]); //将当前答案加上点最少一侧的点数
            else
            { isa = 0; break; }
        }
    if(!isa)    cout << "Impossible";
    else        cout << ans;
    return 0;
}