• luogu P1330 封锁阳光大学


    P1330 封锁阳光大学


    题目描述

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

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

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


    输入输出格式

    输入格式:

     第一行:两个整数N,M

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

    输出格式:

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


    输入输出样例

    输入样例#1:
    3 3
    1 2
    1 3
    2 3
    
    输出样例#1:
    Impossible
    
    输入样例#2:
    3 2
    1 2
    2 3
    
    输出样例#2:
    1

    说明

    【数据规模】

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


    以为很难来着……结果就是个黑白染色

    坑点在于图不一定联通,所以要每个点都检查一遍有没有搜过

    染完色返回min(黑点个数,白点个数)

    顺带一提BFS大法好

    #include<iostream>
    #include<cstdio>
    #include<queue>
    using namespace std;
    const int N=10009,M=100009;
    struct edge{int to,nex;}e[M<<1];
    int n,m,cnt,p[N],ans;
    bool vis[N],col[N],flag;
    void add(int u,int v){
        e[++cnt]=(edge){v,p[u]};
        p[u]=cnt;
    }
    queue<int>q;
    int bfs(int s)
    {
        int re=0,tot=0;
        q.push(s);
        while(!q.empty())
        {
            ++tot;
            int x=q.front();q.pop();vis[x]=1;
            for(int i=p[x];i;i=e[i].nex)
            {
                int v=e[i].to;
                if(vis[v]){
                    if(col[v]==col[x]){flag=0;return 0;}
                }
                else{
                    if(!col[x]){++re;col[v]=1;}
                    else col[v]=0;
                    q.push(v);
                }
            }
        }
        return min(re,tot-re); 
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);add(b,a);
        }
        for(int i=1;i<=n;++i)
        {
            flag=1;
            if(!vis[i])ans+=bfs(i);
            if(!flag){cout<<"Impossible"<<endl;return 0;}
        }
        cout<<ans<<endl;
    }
    fsygdx

    by:wypx


  • 相关阅读:
    python 自动化之路 day 10 协程、异步IO、队列、缓存
    MySQ binlog三种模式
    文件存储之-内存文件系统tmpfs
    Linux 系统结构详解
    服务端高性能数据库优化演变细节案例
    滴滴研发笔记题,亮灯问题
    linux screen 命令详解
    Linux之在CentOS上一次艰难的木马查杀过程
    python 自动化之路 day 09 进程、线程、协程篇
    redis
  • 原文地址:https://www.cnblogs.com/ck666/p/7630093.html
一二三 - 开发者的网上家园