【POI 每日题解 #4】 [POI2008]MAF-Mafia

[POI2008]MAF-Mafia

很容易看出是拓扑 但不容易想出来怎么做【可能是我太菜

首先 入度为零的人是肯定死不了的

接着 我们分成环和链分析

对于一个链

最多的情况就是顺着一个个开枪 最后剩一个( (n - 1) -> (n), (n - 2) ->(n - 1) …… )

最少的情况就是死一半（1->2, 3->4……）

对于一个环

它和链基本上一样

区别在于从任何一个人开始都不会影响结果

这个性质很有用

因为当有环接在链上时

最多的情况下环上的点会全部挂掉

 void bfs(){

     for(int i = ; i <= n; i++)

         if(!ind[i]){

             q[++ans1] = i;

             ans2++;

         }

     for(int i = ; i <= ans1; i++){

         int fro = aim[q[i]];

         if(vis[fro]) continue;

         ind[aim[fro]]--;

         vis[fro] = ;

         otd[aim[fro]] = ;

         if(!ind[aim[fro]]) q[++ans1] = aim[fro];

     }//删链过程 非常重要！

     for(int i = ; i <= n; i++)

         if(!vis[i] && ind[i]){

             int len = , flag = ;

             for(int j = i; !vis[j]; j = aim[j]){

                 vis[j] = ;

                 len++;

                 flag |= otd[j];

             }

             //printf("%d %d\n", flag, len);

             ans1 += (len >> );

             if(len >  && !flag) ans2++;

         }

 }

关键部分