luogu
坑： 图可能分为多个连通块，对于每个连通块都要找染色个数较小的那种颜色，sum进ans
#include<iostream>//对于每一块连通分量都应该能够分为二分图 才能够封锁全部的道路，否则Impossible #include<cstring>#include<string>#include<algorithm>#include<queue>#include<vector> #include<cmath>#include<cstdio>using namespace std;int n,m,head[10009],nxt[200009],num[200009],cnt=0,ans=0,numc1=0,numc2=0;int f[10009];bool flag=false;void color(int x){ if(flag) return; for(int i=head[x];i;i=nxt[i]) { if(f[num[i]]==f[x])//河蟹们有冲突 { flag=true; return; } if(f[num[i]]==0)//只有没被染过色，才color（），并加入个数 { f[num[i]]=-f[x];//染色 if(f[num[i]]==1) numc1++; if(f[num[i]]==-1) numc2++; color(num[i]); } } return;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); cnt++; num[cnt]=b; nxt[cnt]=head[a]; head[a]=cnt; cnt++; num[cnt]=a; nxt[cnt]=head[b]; head[b]=cnt; } for(int i=1;i<=n;i++) { numc1=0,numc2=0;//两种颜色都记下个数 if(f[i]==0) { f[i]=1; numc1++; color(i); ans+=min(numc1,numc2);//每个连通分量里面 找染的个数较少的 最后才是最优解 } if(flag) { PRintf("Impossible/n");//只要有不能分为二分图的连通块 ，就Impossible return 0; } } printf("%d/n",ans); return 0;}新闻热点
疑难解答
