讀題易得：對于有邊的兩個點 \(u,v\) ，能且僅能其中一點對這條邊進行封鎖，
什么意思呢？假設給這張圖上的點進行染色，那么對于上述的兩個點 \(u,v\) ，\(u,v\) 必須異色（理解這一點很重要），
那么，也就是說，在這張圖上，如果要把這張圖“完全封鎖”且兩只河蟹不能封鎖相鄰的兩個點，換而言之，把連接一條邊的兩個點染色，這兩個點是異色的，那么整張圖上無非也就這兩種顏色，答案無非也就是這兩種顏色中數目較少那一種的數目，
注意到存在無解的情況，那么是么時候無解呢？想一下，遍歷這張圖，那么肯定會遇到做過的點，把我們自己想成河蟹，那么重復來到這時相當于給這個點重新染色， 如果我們攜帶的“顏料”和上一只河蟹是一樣的，那么相當于什么都不做；但如果不同，相當于對這個點重新封鎖，這就產生了沖突，所以，這時不合法，回傳 0 ，否則回傳 1 ，
請注意：這個圖可能不是聯通的，所以需要設 vis 陣列，判斷某個點有沒有用過，去遍歷所有的小連通圖，
參考代碼：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m,vis[4000010],c[3],head[4000010],tot,_color[4000010];
//_color[u]代表第 u 個點的顏色
//c[]記錄兩種顏色的數量
struct node
{
int to,nxt;
};
node G[400010];
inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void add(int u,int v)
{
G[++tot]=(node){v,head[u]},head[u]=tot;
G[++tot]=(node){u,head[v]},head[v]=tot;
}
int dfs(int u,int cor)
{
if(vis[u])
{
if(_color[u]==cor)return 1;
return 0;
}
vis[u]=1;
c[_color[u]=cor]++;
int can_do=1;
for(int i=head[u];i&&can_do;i=G[i].nxt)can_do=can_do&&dfs(G[i].to,1-cor);
return can_do;
}
int main()
{
int ans;
n=read(),m=read();
for(int i=1;i<=m;i++){int u=read(),v=read();add(u,v);}
for(int i=1;i<=n;i++)
{
if(vis[i])continue;
c[0]=c[1]=0;
if(dfs(i,0)==0){cout<<"Impossible"<<endl;return 0;}
ans+=min(c[0],c[1]); //注意，這里是加上
}
cout<<ans<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63280.html
標籤：C++
上一篇：【學習筆記】[圖論]樹的直徑
下一篇：【做題筆記】P1090 合并果子