[AGC016E]Poor Turkeys

题目大意：

有\(n(n\le400)\)只火鸡，编号为\(1\)到\(n\)，有\(m(m\le10^5)\)个人，每人指定了两只火鸡\(x\)和\(y\)。

1. 若\(x\)和\(y\)都活着，那么这个人将会等概率地随机吃掉一只。
2. 若\(x\)和\(y\)恰好活着一只，那么这个人将会吃掉活着的这只。
3. 若\(x\)和\(y\)都已经死亡，那么只好什么都不做。

求有多少个\((i,j)(1\le i<j\le n)\)满足存在至少一种吃鸡方案使得在最终时刻第\(i\)只火鸡和第\(j\)只火鸡都还活着。

思路：

用bitset维护若第\(i\)只火鸡活着，则哪些鸡一定要牺牲的集合\(S_i\)。

维护\(S_i\)时，倒序枚举\(m\sim 1\)，对于当前的\(x,y\)：

1. 若\(|\{x,y\}\bigcap S_i|=0\)，则\(x,y\)都可以存活；
2. 若\(|\{x,y\}\bigcap S_i|=1\)，则\(x,y\)都不能存活；
3. 若\(|\{x,y\}\bigcap S_i|=2\)，则\(i\)本身都不能存活。

最后枚举\(i,j\)，若\(S_i\bigcup S_j=\varnothing\)，则两只鸡可以同时存活。

时间复杂度\(\mathcal O(\frac{n^2m+n^3}\omega)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<bitset>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=401,M=1e5+1;

bool die[N];

int x[M],y[M];

std::bitset<N> b[N];

int main() {

	const int n=getint(),m=getint();

	for(register int i=1;i<=m;i++) {

		x[i]=getint(),y[i]=getint();

	}

	int ans=0;

	for(register int i=1;i<=n;i++) {

		b[i][i]=true;

		for(register int j=m;j>=1;j--) {

			if(b[i][x[j]]&&b[i][y[j]]) b[i].set();

			if(b[i][x[j]]) b[i][y[j]]=true;

			if(b[i][y[j]]) b[i][x[j]]=true;

		}

		for(register int j=1;j<i;j++) {

			if((b[i]&b[j]).count()==0) ans++;

		}

	}

	printf("%d\n",ans);

	return 0;

}