「RQNOJ191」梦幻大PK
题目描述
难得到了生日，正逢上班里面一年一度的梦幻大PK，分2组对拼。但是由于某种原因，参加PK的第1组中有些人不能和第2组人PK。可能是因为等级、互克、相生等关系。于是，南瓜（为鄙班中队长 and 团支书）想要确定最多要多少次PK。十分惋惜，因为鄙人的大名在学校大黑板上挂了2个月（就是全国1=而已拉）了。于是就来 found 鄙人。但是鄙人正准备着自己的生日，于是只好把这个难题交付各位OIers了。十分遗憾，南瓜小姐的统计上有点问题，使问题变的复杂了点。（2组人数相同）
输入格式第1行，一个数，N。接下来N行，其中第i行第1个数M，表示第1组第i个人不能和第2组的M个人PK。然后M个数，表示第1组第i个人与第2组哪M个人不能PK。（注：这M个数或许会有重复）。
数据范围：0<=M<N<=1000。其他输入的数不超过1000。
输出格式一个数，表示最多能举行多少场PK。代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<iostream> #include<cstring> using namespace std; int n,m,x; int ans=0; int y[1001],lk[1001],g[1001][1001]; bool find(int v) { for(int i=1;i<=n;i++) if(!g[v][i]&&!y[i]) { y[i]=1; if(!lk[i]||find(lk[i])){lk[i]=v;return 1;} } return 0; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>m; for(int j=1;j<=m;j++) { cin>>x; g[i][x]=1; } } for(int i=1;i<=n;i++) { memset(y,0,sizeof(y)); if(find(i))ans++; } cout<<ans; return 0; } |
计数器 9787280
OI 课件=>
OI 课件=>
这为什么匈牙利过不了最后几个点