首页 > 代码库 > [POI 2008]Mafia

[POI 2008]Mafia

2024-07-16 12:31:03   212人阅读

这题目写了我好长时间，但还是几乎(不要在意细节)一遍 A 了喵~

据说有代码奇短的，Orz 思路巧妙的大爷

想我这种 Brute Force 写写的傻 X 真是代码量飞起来了耶，喵~

 

如果把每个人看成点，每个人要 kill 的人向此人连出一条有向边，那么每个点仅有一条出边和一条入边

经验告诉我们，这就是 环+内向图 的节奏

经验又告诉我，处理这种图要么先暴力搞环，再搞挂在环上的树。要么先搞树，再弄环。

此题显然是后者

 

环+内向图只需要用 bfs 就可以搞出来了，看到写 tarjan 的真是 Orz 

弄出 环 和 树 后，先在树上跑 dp，用 dp[u][0] 表示如果 u 最后被 kill 了，那么以 u 为根子树最少要死几人， dp[u][1] 是 u 存活下来的情况，这是普及组难度的树形dp

再在环上跑 dp ，我们先破环为链，则有3种情况 (我们令在首的人为 A , 在尾的人为 B)

1. A君 最后活着，那 B君 一定被 kill 了

2. A君 最后被 kill 了，B君 存活了或也被 kill 了

3. A君 存活了下来，B君 也存活了下来，然后 B君 kill A君

三种情况要分类讨论

中间过程的状态转移和以上三种情况类似，无非就是讨论 i 君 和 i+1 君 的是否被 kill 的关系  (妈妈说，某个字打出来是不好的喵~)

被 kill 有两种可能:1.被自己的子树中的某君 kill 了  2.被环上的某君 kill 了

这个 dp 也很好想嘛

 

似乎除了难写就没有难度了喵？

 

  1 #include <cstdio>  2 #include <cstring>  3 const int size=1000001;  4 const int inf=size;  5   6 namespace IOspace  7 {  8     inline void assign() {freopen("isaac.in", "r", stdin); freopen("isaac.out", "w", stdout);}  9     inline void close() {fclose(stdin); fclose(stdout);} 10     inline int getint() 11     { 12         register int num=0; 13         register char ch; 14         do ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 15         do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 16         return num; 17     } 18     inline void putint(int num, char ch=‘\n‘) 19     { 20         char stack[15]; 21         register int top=0; 22         if (num==0) stack[top=1]=‘0‘; 23         for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 24         for ( ;top;top--) putchar(stack[top]); 25         if (ch) putchar(ch); 26     } 27 } 28  29 int n; 30 int g[size][2]; 31 int t, a[size]; 32 int f[size], d[size]; 33 int dp[size][2]; 34 bool vis[size], loop[size]; 35  36 struct edge {int point; edge * next;}; 37 edge MEM[size], * PORT=MEM; 38 edge * E[size]; 39 inline edge * newedge(int _point, edge * _next) 40     {edge * ret=PORT++; ret->point=_point; ret->next=_next; return ret;} 41  42 inline int min(int x, int y) {return x<y?x:y;} 43 inline int max(int x, int y) {return x>y?x:y;} 44 inline void add(int & x, int y) {if (x>=inf || y>=inf) x=inf; else x+=y;} 45 inline int search(int); 46 inline int find(int); 47 inline void bfs(int); 48  49 int main() 50 { 51     int ans1=0, ans2=0; 52  53     n=IOspace::getint(); 54     for (int i=1;i<=n;i++) 55     { 56         f[i]=IOspace::getint(), d[f[i]]++; 57         if (f[i]==i) ans2++, vis[i]=1; 58         E[f[i]]=newedge(i, E[f[i]]); 59     } 60  61     for (int i=1;i<=n;i++) if (!d[i]) 62     { 63         vis[i]=1; 64         ans2+=search(i); 65     } 66     for (int i=1;i<=n;i++) if (!vis[i]) 67     { 68         vis[i]=1; 69         ans2+=search(i); 70     } 71  72     memset(vis, 0, sizeof(vis)); 73     for (int i=1;i<=n;i++) if (!vis[i]) 74     { 75         vis[i]=1; 76         ans1+=find(i); 77     } 78  79     IOspace::putint(ans1, ‘ ‘); IOspace::putint(ans2); 80  81     return 0; 82 } 83 inline int search(int x) 84 { 85     int ret=0; 86     for (x=f[x];!vis[x];x=f[x]) vis[x]=1, ret++; 87     return ret; 88 } 89 inline void bfs(int x) 90 { 91     static int l, r, q[size]; 92  93     l=r=0; 94     for (q[r++]=x;l<r; ) 95     { 96         int u=q[l++]; 97         for (edge * i=E[u];i;i=i->next) 98             if (!loop[i->point]) 99             {100                 vis[i->point]=1;101                 q[r++]=i->point;102             }103     }104 105     for (int i=r-1;i>=0;i--)106         if (E[q[i]]==NULL) dp[q[i]][0]=inf;107         else if (E[q[i]]->next==NULL && loop[E[q[i]]->point]) dp[q[i]][0]=((E[q[i]]->point)==q[i])?1:inf;108         else109         {110             for (edge * j=E[q[i]];j;j=j->next)111                 if (!loop[j->point])112                     add(dp[q[i]][1], dp[j->point][0]);113             for (edge * j=E[q[i]];j;j=j->next)114                 if (!loop[j->point])115                     add(dp[q[i]][0], min(dp[j->point][0], dp[j->point][1]));116             add(dp[q[i]][0], 1);117         }118 }119 inline int find(int x)120 {121     int ret=0;122 123     vis[x]=1;124     for (x=f[x];!vis[x];x=f[x]) vis[x]=1;125     for (t=0;!loop[x];x=f[x]) loop[a[t++]=x]=1;126     for (int i=0;i<t;i++) bfs(a[i]);127     if (t==1) return dp[a[0]][0];128     g[0][1]=dp[a[0]][1]; g[0][0]=inf;129     for (int i=1;i<t;i++)130     {131         g[i][0]=min(g[i-1][0], g[i-1][1]);132         add(g[i][0], min(dp[a[i]][0], dp[a[i]][1]+1));133         g[i][1]=g[i-1][0];134         add(g[i][1], dp[a[i]][1]);135     }136     ret=g[t-1][0];137 138     g[0][0]=dp[a[0]][0]; g[0][1]=inf;139     for (int i=1;i<t;i++)140     {141         g[i][0]=min(g[i-1][0], g[i-1][1]);142         add(g[i][0], min(dp[a[i]][0], dp[a[i]][1]+1));143         g[i][1]=g[i-1][0];144         add(g[i][1], dp[a[i]][1]);145     }146     ret=min(ret, min(g[t-1][0], g[t-1][1]));147 148     g[0][0]=dp[a[0]][1]+1; g[0][1]=inf;149     for (int i=1;i<t;i++)150     {151         g[i][0]=min(g[i-1][0], g[i-1][1]);152         add(g[i][0], min(dp[a[i]][0], dp[a[i]][1]+1));153         g[i][1]=g[i-1][0];154         add(g[i][1], dp[a[i]][1]);155     }156     ret=min(ret, g[t-1][1]);157 158     return ret;159 }
因为是考试时写的所以很长也是没办法的事系列

 


联系
我们