首页 > 代码库 > RQNOJ PID192 梦幻大PK [2017年6月计划 二分图02]
RQNOJ PID192 梦幻大PK [2017年6月计划 二分图02]
PID192 / 梦幻大PK ☆
- 提交你的代码
- 查看讨论和题解
你还木有做过哦
我的状态
查看最后一次评测记录
质量 7
题目评价
质量
7
★★★★★
★★★★☆
★★★☆☆
★★☆☆☆
★☆☆☆☆
50%
0%
25%
0%
25%
★
★
★
★
☆
通过人数 754 / 2273
通过统计
最短耗时
0ms
最小内存
0KB
匹配
题目标签
类型
匹配
题目描述
难得到了生日，正逢上班里面一年一度的梦幻大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 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar();if(c == ‘-‘)x = -x;} 7 const int MAXN = 2000 + 10; 8 9 int n;10 int g[MAXN][MAXN],by[MAXN],lk[MAXN];11 int ans;12 13 int find(int v)14 {15 for(register int i = 1;i <= n;++ i)16 {17 if(!by[i] && (!g[v][i]))18 {19 by[i] = 1;20 if((!lk[i]) || find(lk[i]))21 {22 lk[i] = v;23 return 1;24 }25 }26 }27 return 0;28 }29 30 int main()31 {32 read(n);33 register int m, tmp;34 for(register int i = 1;i <= n;++ i)35 {36 read(m);37 for(register int j = 1;j <= m;++ j)38 {39 read(tmp);40 g[i][tmp] = 1;41 }42 }43 for(register int i = 1;i <= n;++ i)44 {45 memset(by, 0, sizeof(by));46 if(find(i))ans ++;47 }48 printf("%d", ans);49 return 0;50 }
RQNOJ PID192 梦幻大PK [2017年6月计划 二分图02]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。