题解 AT2389 【Poor Turkeys】

· · 题解

【AGC016E】Poor Turkeys 题解

首先记住一句话：留着你是因为以后要炖了你。这句话非常重要，它的思想是题解的核心

我们设状态f_{i,j}表示：如果最后要留下i，那么是否要炖了j。初始值设f_{i,i}=1

如果我们从时间倒流的角度来考虑这个状态，那么当前f数组就表示：如果最后要留下i，那么之前是否要留下j（因为以后要炖了j）。如果我们遇到某个时刻需要在i和j中选择，那么为了留下i，必然要炖了j，那么在此之前就不能让j死了，于是在这之前的时间，j应该受到与i一样的保护，也就是如果某个时刻要在j和k中选择，那肯定炖了k。所以对于每一个i，我们都要从时间倒流的角度去传递这个状态，然后得到完整的状态，然后将满足f_{i,j}=1的点j放入集合S_i中，表示如果要留下i需要炖了哪些东西

考虑一只鸡i怎样才能被留下来。如果存在一个时刻，要在x和y中选择，而此时的状态是f_{i,x}=f_{i,y}=1（也就是说为了留下i，必须留下x和y来挡枪子），可是x和y只能留一个了，那么i就不能被保留下来了。这是结论一

那么我们把一对鸡(i,j)放到一起来考虑一下。假如有一个时刻需要在i和x中选择，接下来又有一个时刻需要在j和x中选择，那么根据上面的思想，之前那个时刻我们会把x炖了，可是为了留下j，我们又不能那么早炖了x，因此如果有那么两个时刻，我们就可以说这一对鸡(i,j)不可能同时留下来

将这个思路拓展一下，假如有一个时刻需要在i和x中选择，接下来又有一个时刻需要在j和y中选择，那么在此之前，x与y应该受到与i和j一样的保护，所以应该当做i和j来看待。假如在上述两个时刻之前，有一个时刻需要在z和x中选择，接下来又有一个时刻需要在z和y中选择，那么鸡(i,j)是不可能留下来的，因为(x,y)不能同时被保护，最后i和j就会有一个不能拉到挡枪的人。

再拓展一下，我们可以得到结论：(i,j)可以留下，当且仅当S_i\cap S_j=\varnothing。这是结论二

按上面提到的两个结论去做就可以了，复杂度O(nm+n^3)，求交集的那个部分可以用bitset优化，但也没什么必要

#include<bits/stdc++.h>
using namespace std;

const int M=100010;
bool stu[410][410];
int n,m,a[M],b[M];
bool cant[410];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",a+i,b+i);
    for(int i=1;i<=n;i++)
    {
        stu[i][i]=1;
        for(int j=m;j>=1;j--)
        {
            bool x=stu[i][a[j]],y=stu[i][b[j]];
            if(x&&y){cant[i]=1;break;}
            else if(x) stu[i][b[j]]=1;
            else if(y) stu[i][a[j]]=1;
        }
    }
    int ans=0;
    for(int i=1;i<n;i++)
    {
        if(cant[i]) continue;
        for(int j=i+1;j<=n;j++)
        {
            if(cant[j]) continue;
            bool flag=1;
            for(int k=1;k<=n;k++)
                if(stu[i][k]&&stu[j][k]) flag=0;
            ans+=flag;
        }
    }
    printf("%d\n",ans);
    return 0;
}