RQNOJ PID192 梦幻大PK [2017年6月计划二分图02]

PID192 / 梦幻大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 #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 }

View Code

RQNOJ PID192 梦幻大PK [2017年6月计划 二分图02]

RQNOJ PID192 梦幻大PK [2017年6月计划二分图02]