| Time Limit: 7000MS | Memory Limit: 65536K | |
| Total Submissions: 9227 | Accepted: 3180 |
Description
Input
Output
Sample Input
3 2 John 0 1 Rose 1 Mary 1 5 4 ACM 1 2 3 ICPC 0 1 Asian 0 2 3 Regional 1 2 ShangHai 0 2 0 0
Sample Output
2 2
Source
1 /************************************************************************* 2 > File Name: poj-2289.jamies_contact_groups.cpp 3 > Author: CruelKing 4 > Mail: 2016586625@qq.com 5 > Created Time: 2019年09月03日 星期二 21时09分58秒 6 ************************************************************************/ 7 /* 8 #include <iostream> 9 #include <sstream> 10 #include <string> 11 #include <cstring> 12 using namespace std; 13 14 const int maxn = 1000 + 5, maxm = 500 + 5, inf = 0x3f3f3f3f; 15 16 int n, m; 17 string str; 18 char name[20]; 19 int linker[maxm][maxn]; 20 bool used[maxm], g[maxn][maxm]; 21 22 bool dfs(int u) { 23 for(int v = 0; v < m; v ++) { 24 if(g[u][v] && !used[v]) { 25 used[v] = true; 26 if(linker[v][0] == 0) { 27 linker[v][++ linker[v][0]] = u; 28 return true; 29 } 30 for(int i = 1; i <= linker[v][0]; i ++) { 31 if(dfs(linker[v][i])) { 32 linker[v][i] = u; 33 return true; 34 } 35 } 36 linker[v][++ linker[v][0]] = u; 37 return true; 38 } 39 } 40 return false; 41 } 42 43 int main() { 44 while(cin >> n >> m && (n || m)) { 45 memset(g, false, sizeof g); 46 for(int i = 0; i < n; i ++) { 47 cin >> name; 48 getline(cin, str); 49 stringstream ss; 50 ss << str; 51 int x; 52 while(ss >> x) 53 g[i][x] = true; 54 } 55 int res = 0; 56 for(int i = 0; i < m; i ++) linker[i][0] = 0; 57 for(int i = 0; i < n; i ++) { 58 memset(used, false, sizeof used); 59 if(dfs(i)) res ++; 60 } 61 int M = 0; 62 for(int i = 0; i < m; i ++) { 63 if(M < linker[i][0]) M = linker[i][0]; 64 } 65 cout << M << endl; 66 } 67 return 0; 68 } 69 */ 70 #include <iostream> 71 #include <sstream> 72 #include <string> 73 #include <cstring> 74 #define mid ((l + r) >> 1) 75 using namespace std; 76 77 const int maxn = 1000 + 5, maxm = 500 + 5, inf = 0x3f3f3f3f; 78 79 int n, m, l, r; 80 string str; 81 char name[20]; 82 int linker[maxm][maxn]; 83 bool used[maxm], g[maxn][maxm]; 84 85 bool dfs(int u) { 86 for(int v = 0; v < m; v ++) { 87 if(g[u][v] && !used[v]) { 88 used[v] = true; 89 if(linker[v][0] < mid) { 90 linker[v][++ linker[v][0]] = u; 91 return true; 92 } 93 for(int i = 1; i <= mid; i ++) { 94 if(dfs(linker[v][i])) { 95 linker[v][i] = u; 96 return true; 97 } 98 } 99 } 100 } 101 return false; 102 } 103 104 int main() { 105 while(cin >> n >> m && (n || m)) { 106 memset(g, false, sizeof g); 107 for(int i = 0; i < n; i ++) { 108 cin >> name; 109 getline(cin, str); 110 stringstream ss; 111 ss << str; 112 int x; 113 while(ss >> x) 114 g[i][x] = true; 115 } 116 /* 117 int res = 0; 118 l = 0, r = maxn << 1; 119 for(int i = 0; i < m; i ++) linker[i][0] = 0; 120 for(int i = 0; i < n; i ++) { 121 memset(used, false, sizeof used); 122 if(dfs(i)) res ++; 123 } 124 cout << res << endl; 125 */ 126 l= 0, r = n; 127 int res; 128 while(l <= r) { 129 res = 0; 130 for(int i = 0; i < m; i ++) linker[i][0] = 0; 131 for(int i = 0; i < n; i ++) { 132 memset(used, false, sizeof used); 133 if(dfs(i)) res ++; 134 } 135 if(n == res) r = mid - 1; 136 else l = mid + 1; 137 } 138 cout << mid + 1 << endl; 139 } 140 return 0; 141 }
poj-2289.jamies contact groups(二分答案 + 二分多重匹配)
原文：https://www.cnblogs.com/bianjunting/p/11456522.html