洛咕题解 P1330 封锁阳光大学[图的黑白染色,dfs]

  • A+
所属分类:代码笔记 信息技术

题面

可以发现选了一个点后(染黑),他连着的点全都不能选了(染白). 又要求封锁所有道路,所以转化成图的黑白染色问题来做.

  1. #include<cstdio>
  2. #define re register
  3. inline int read()
  4. {
  5.     int s=0,b=1;
  6.     char ch;
  7.     do{
  8.         ch=getchar();
  9.         if(ch=='-') b=-1;
  10.     }while(ch<'0' || ch>'9');
  11.     while(ch>='0' && ch<='9')
  12.     {
  13.         s=s*10+ch-'0';
  14.         ch=getchar();
  15.     }
  16.     return b*s;
  17. }
  18. struct edge{
  19.     int t,w,next;
  20. }e[110000];
  21. int head[11000],cnt=0,n,m;
  22. inline void add(int f,int t,int w)
  23. {
  24.     ++cnt;
  25.     e[cnt].t=t;
  26.     e[cnt].w=w;
  27.     e[cnt].next=head[f];
  28.     head[f]=cnt;
  29. }
  30. int b[11000],c[11000];
  31. int flag,ans,s;
  32. void dfs(int i,int color)
  33. {
  34.     if(flag) return;
  35.     if(b[i])
  36.     {
  37.         if(c[i]!=color) {flag=233;return;}
  38.         //如果i点已染色, 又将染上一个不同的颜色, 则此联通块不可黑白染色.
  39.         else return;
  40.     }
  41.     ++cnt;
  42.     b[i]=1;
  43.     c[i]=color;
  44.     if(color) ++s;//统计黑点数
  45.     for(re int v=head[i];v;v=e[v].next)
  46.         dfs(e[v].t,!color);//把相邻的点都染成不同的颜色
  47.     //由于只要求出一种染色方案, 不需要回溯.
  48. }
  49. int main()
  50. {
  51.     n=read();
  52.     m=read();
  53.     int x,y;
  54.     for(re int i=1;i<=m;++i)
  55.     {
  56.         x=read();
  57.         y=read();
  58.         add(x,y,1);
  59.         add(y,x,1);
  60.     }
  61.     for(re int i=1;i<=n;++i)
  62.     {//图并不保证联通, 所以要分别染色各个联通块.
  63.         if(b[i]) continue;
  64.         flag=0;
  65.         s=0;//s统计此联通块黑点个数
  66.         cnt=0;//cnt用来统计此联通块节点总数
  67.         dfs(i,1);
  68.         if(flag==233){
  69.             printf("Impossible\n");
  70.             return 0;
  71.         }
  72.         ans+=s<(cnt-s)?s:(cnt-s);
  73.         //既然节点i染黑可行,那么黑白互换也可行.取这两种方案中最小的.
  74.     }
  75.     printf("%d\n",ans);
  76.     return 0;
  77. }
xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: