封锁阳光大学

题目描述

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

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

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

输入输出格式

输入格式：

第一行：两个整数N，M

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

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#1：复制

Impossible

输入样例#2：复制

输出样例#2：复制

说明

【数据规模】

1<=N<=10000，1<=M<=100000，任意两点之间最多有一条道路。

　　分析：

　　思路非常巧妙的一道图论题，也是理解染色问题的一道好题。

　　首先，题目并没有保证是一个连通图，但经过分析也可以知道，只要每个子连通图都满足要求即可。重点在于，题目要求每一条边的连个端点必须有且仅有一个端点被占。那么实际上也就等效于，任意两个相邻的点必须被染成不同的颜色。那么思路有了就好做了，直接深搜或者广搜都行，遍历每个子连通图判断是否可以按照该原则染色即可。具体看代码。

　　Code：

#include<bits/stdc++.h>

using namespace std;

const int N=1e4+;

const int M=1e5+;

bool vis[N];

int n,m,head[N],size,col[N],sum[],ans;

struct Node{int to,next;}edge[M<<];

inline int read()

{

    char ch=getchar();int num=;bool flag=false;

    while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

    while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

    return flag?-num:num;

}

inline void add(int x,int y)

{

    edge[++size].to=y;

    edge[size].next=head[x];

    head[x]=size;

}

inline bool dfs(int u,int color)

{

    if(vis[u]){

        if(col[u]==color)return true;

        return false;}

    vis[u]=true;sum[col[u]=color]++;

    bool flag=true;

    for(int i=head[u];i!=-;i=edge[i].next){

        flag=flag&&dfs(edge[i].to,-color);}

    return flag;

}

int main()

{

    memset(head,-,sizeof(head));

    memset(vis,false,sizeof(vis));

    n=read();m=read();int x,y;

    for(int i=;i<=m;i++){

        x=read();y=read();

        add(x,y);add(y,x);}

    for(int i=;i<=n;i++){

        if(vis[i])continue;

        sum[]=sum[]=;

        if(!dfs(i,)){

            printf("Impossible");

            return ;}

        ans+=min(sum[],sum[]);}

    printf("%d",ans);

    return ;

}

巴特西

洛谷P1330 封锁阳光大学 [图论，染色]

封锁阳光大学

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章