Girls and Boys
In the second year of the university somebody started a study on the romantic relations between the students. The relation "romantically involved" is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been "romantically involved". The result of the program is the number of students in such a set.
Input
The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:
the number of students
the description of each student, in the following format
student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ...
or
student_identifier:(0)
The student_identifier is an integer number between 0 and n-1 (n <=500 ), for n subjects.
Output
For each given data set, the program should write to standard output a line containing the result.
Sample Input
7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0
Sample Output
5
2
Source
题目类型：最大点独立集(二分图最大匹配)
算法分析：这里给出n个点和m条边，求解最大的点独立集是多少，这里使用基于网络流的算法会比使用匈牙利算法要简单
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
/************************************************* Author :supermaker Created Time :2016/1/19 20:35:16 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 500 + 66; int match[maxn], vis[maxn]; vector <int> g[maxn]; int n; int dfs (int u) { vis[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i], t = match[v]; if (t < 0 || (!vis[t] && dfs (t))) { match[u] = v; match[v] = u; return 1; } } return 0; } int maxmatch () { int res = 0; memset (match, -1, sizeof (match)); for (int i = 0; i < n; i++) if (match[i] == -1) { memset (vis, 0, sizeof (vis)); res += dfs (i); } return res; } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { for (int i = 0; i < maxn; i++) g[i].clear (); for (int i = 1; i <= n; i++) { int vala, num; scanf ("%d: (%d) ", &vala, &num); int valb; for (int j = 1; j <= num; j++) { scanf ("%d", &valb); g[vala].push_back (valb); } } printf ("%d\n", n - maxmatch ()); } return 0; } |
- « 上一篇：zoj1654
- poj1422：下一篇 »