M_sea

洛谷1330 封锁阳光大学
题目描述曹是一只爱刷街的老曹,暑假期间,他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹,感到不爽。河蟹决定...
扫描右侧二维码阅读全文
17
2018/07

洛谷1330 封锁阳光大学

题目描述

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

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

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

传送门

算法

简单的Dfs(或者叫做二分图染色?)。

首先对每一个子连通图进行染色,之后统计出染成黑色的数量和染成白色的数量,取最小值加入答案中即可。

在对每一个子图Dfs时,可以顺便统计出子图中的节点数。那么Dfs完后统计出黑色数,用总结点数减黑色数就是白色数。

注意:双向边图不一定联通

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

struct Edge { int v,nxt; };
Edge e[500010];
int head[50010],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int n,m,sum;
bool vis[50010];
int color[50010];

inline void Dfs(int u,int c) {
    if (color[u]!=-1&&color[u]!=c) { puts("Impossible"); exit(0); }
    if (color[u]==c) return;
    vis[u]=1; color[u]=c; sum++;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        Dfs(v,c^1);
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;i++) {
        int a=read(),b=read();
        addEdge(a,b);
        addEdge(b,a);
    }
    int ans=0;
    for (re int i=1;i<=n;i++)
        if (!vis[i]) {
            memset(color,-1,sizeof(color));
            sum=0; Dfs(i,1); int t=0;
            for (re int i=1;i<=n;i++) t+=(color[i]==1);
            ans+=min(t,sum-t);
        }
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 46 PM

发表评论