何老板养了n只鸡(编号1到n)。何老板打算从今天开始，连续m晚都吃鸡。每晚，何老板会选一对指定编号的鸡出来。若两只鸡都活着，那么他会随便吃掉其中一只；若只有一只活着，另一只之前已经被吃了，就吃还活着那只；若两只鸡都已被吃掉了，当晚就不吃鸡。何老板想知道，m天后，可能有多少对鸡同时活着？请你帮他算一算。(如果一对鸡存活的概率>0,我们认为他们可能活着)
第一行，两个整数n和m接下来m行，每行两个整数x和y，第i行表示第i天选出的两只鸡的编号。
一行，一个整数，表示最后还存活的鸡的对数。
3 11 2
2
4 31 23 42 3
1
3 21 21 2
0
10 108 92 84 64 97 82 81 83 43 42 7
5
2≤N≤4001≤M≤10^5
样例1说明：如果第1晚吃2，那么(1,3)这对鸡还活着如果第1晚吃1，那么(2,3)这对鸡还活着
样例2说明：(1, 4) 这对鸡活着，如果采用的是下列吃鸡方式：第1晚吃2号鸡第2晚吃3号鸡第3晚没得吃
分析 从后向前讨论，讨论假如某只鸡不死需要的条件。 那么要保证与它在一起的鸡都死亡，即之前未死。 1 // 2 #include<stdio.h> 3 #include<bits/stdc++.h> 4 using namespace std; 5 int a[100005],b[100005],dead[405],Liveset[405][405]; 6 int n,m,ans; 7 int main() 8 { 9 cin>>n>>m; 10 for(int i=1;i<=m;i++)cin>>a[i]>>b[i]; 11 for(int i=1;i<=n;i++) 12 { 13 Liveset[i][i]=1; 14 for(int j=m;j>0;j--) 15 { 16 int x=Liveset[i][a[j]]; 17 int y=Liveset[i][b[j]]; 18 if(x&&y) 19 { 20 dead[i]=true; 21 break; 22 } 23 else 24 { 25 if(x)Liveset[i][b[j]]=1; 26 if(y)Liveset[i][a[j]]=1; 27 } 28 } 29 } 30 for(int i=1;i<+n;i++) 31 { 32 if(dead[i])continue; 33 for(int j=i+1;j<=n;j++) 34 { 35 if(dead[j])continue; 36 int tmp=1; 37 for(int k=1;k<+n;k++) 38 { 39 if(Liveset[i][k]&&Liveset[j][k]) 40 { 41 tmp=0; 42 break; 43 } 44 } 45 ans+=tmp; 46 } 47 } 48 cout<<ans; 49 } 50 51 52
转载于:https://www.cnblogs.com/CXYscxy/p/11058870.html
相关资源：数据结构—成绩单生成器