NKOJ 5140 大吉大利 晚上吃鸡

问题描述

何老板养了n只鸡(编号1到n)。何老板打算从今天开始，连续m晚都吃鸡。

每晚，何老板会选一对指定编号的鸡出来。若两只鸡都活着，那么他会随便吃掉其中一只；若只有一只活着，另一只之前已经被吃了，就吃还活着那只；若两只鸡都已被吃掉了，当晚就不吃鸡。

何老板想知道，m天后，可能有多少对鸡同时活着？请你帮他算一算。(如果一对鸡存活的概率>0,我们认为他们可能活着)

输入格式

第一行，两个整数n和m

接下来m行，每行两个整数x和y，第i行表示第i天选出的两只鸡的编号。

输出格式

一行，一个整数，表示最后还存活的鸡的对数。

我们来分析一下第xxx鸡能够存活下来的条件。

假设与第xxx鸡配对的鸡按照顺序分别为y1,y2,...,yky_1,y_2,...,y_ky1​,y2​,...,yk​

在xxx与yky_kyk​中，xxx要存活，那么yky_kyk​就要被吃

在xxx与yk−1y_{k-1}yk−1​中，xxx要存活，那么yk−1y_{k-1}yk−1​就要被吃

…

在xxx与y1y_1y1​中，xxx要存活，那么y1y_1y1​就要被吃。

也就是说，如果某只鸡要存活下来，那么与它配对的所有其他鸡都要被吃。

所以我们设立一个状态liv[x][y]=1liv[x][y]=1liv[x][y]=1，表示第xxx只要存活下来，第yyy只鸡必须活着等着为xxx牺牲被吃。

那么第xxx只鸡不能存活的条件呢？

假设第aaa只鸡与第bbb只鸡配对了，并且liv[x][a]==liv[x][b]==1liv[x][a]==liv[x][b]==1liv[x][a]==liv[x][b]==1

也就是说xxx要存货下来，那么aaa和bbb都要存活下来，但是a,ba,ba,b只能存活下来一个，于是在这种情况下第xxx只鸡必死。

接下来讨论求解，也就是哪些对鸡可以存活。

我们假设这对鸡为x,yx,yx,y。

那么这对鸡的存活条件为如果存在liv[x][z]=1liv[x][z]=1liv[x][z]=1，那么liv[y][z]!=1liv[y][z]!=1liv[y][z]!=1

时间复杂度：O(n3+nm)O(n^3+nm)O(n3+nm)

#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define db double#define sg string#define ll long long#define rel(i,x,y) for(ll i=(x);i<(y);i++)#define rep(i,x,y) for(ll i=(x);i<=(y);i++)#define red(i,x,y) for(ll i=(x);i>=(y);i--)#define res(i,x) for(ll i=head[x];i;i=nxt[i])using namespace std;const ll N=405;const ll M=1e5+5;const ll Inf=1e18;const ll Mod=1e9+7;const db Eps=1e-10;ll n,m,ans,a[M],b[M],flg[N],liv[N][N];inline ll read() {ll x=0;char ch=getchar();bool f=0;while(ch>'9'||ch<'0'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return f?-x:x;}int main() {n=read(),m=read();rep(i,1,m) a[i]=read(),b[i]=read();rep(i,1,n) {liv[i][i]=1;red(j,m,1) {ll fa=liv[i][a[j]],fb=liv[i][b[j]];if(fa&&fb) {flg[i]=1;break;} else {if(fa) liv[i][b[j]]=1;if(fb) liv[i][a[j]]=1;}}}rep(i,1,n) if(!flg[i]) rep(j,i+1,n) if(!flg[j]) {ll flag=1;rep(k,1,n) if(liv[i][k]&&liv[j][k]) {flag=0;break ;}if(flag) ans++;}printf("%lld\n",ans);return 0;}

如果觉得《NKOJ 5140 大吉大利 晚上吃鸡》对你有帮助，请点赞、收藏，并留下你的观点哦！