- 1
- /**
- 2 * poj.org
- 3 * Problem#1274
- 4 * Accepted
- 5 * Time:16ms
- 6 * Memory:1980k
- 7 */
- 8#include 9#include 10#include 11#include 12#include 13#include 14#include 15#include 16#include 17#include < set > 18#include 19#include 20#include 21#include 22 using namespace std;
- 23 typedef bool boolean;
- 24#define smin(a, b)(a) = min((a), (b)) 25#define smax(a, b)(a) = max((a), (b)) 26#define INF 0xfffffff 27 template 28 inline boolean readInteger(T & u) {
- 29 char x;
- 30 int aFlag = 1;
- 31
- while (!isdigit((x = getchar())) && x != ' - ' && ~x);
- 32
- if (! (~x)) return false;
- 33
- if (x == ' - ') {
- 34 aFlag = -1;
- 35 x = getchar();
- 36
- }
- 37
- for (u = x - '0'; isdigit((x = getchar())); u = u * 10 + x - '0');
- 38 ungetc(x, stdin);
- 39 u *= aFlag;
- 40
- return true;
- 41
- }
- 42 ///map template starts
- 43 typedef class Edge {
- 44 public: 45 int end;
- 46 int next;
- 47 int cap;
- 48 int flow;
- 49 Edge(const int end = 0, const int next = 0, const int cap = 0, const int flow = 0) : end(end),
- next(next),
- cap(cap),
- flow(flow) {}
- 50
- }
- Edge;
- 51 52 typedef class MapManager {
- 53 public: 54 int ce;
- 55 int * h;
- 56 Edge * edge;
- 57 MapManager() {}
- 58 MapManager(int points, int limit) : ce(0) {
- 59 h = new int[(const int)(points + 1)];
- 60 edge = new Edge[(const int)(limit + 1)];
- 61 memset(h, 0, sizeof(int) * (points + 1));
- 62
- }
- 63 inline void addEdge(int from, int end, int cap, int flow) {
- 64 edge[++ce] = Edge(end, h[from], cap, flow);
- 65 h[from] = ce;
- 66
- }
- 67 inline void addDoubleEdge(int from, int end, int cap) {
- 68 addEdge(from, end, cap, 0);
- 69 addEdge(end, from, cap, cap);
- 70
- }
- 71 Edge & operator[](int pos) {
- 72
- return edge[pos];
- 73
- }
- 74 inline int reverse(int pos) { //反向边
- 75
- return (pos & 1) ? (pos + 1) : (pos - 1);
- 76
- }
- 77 inline void clear() {
- 78 delete[] edge;
- 79 delete h;
- 80 ce = 0;
- 81
- }
- 82
- }
- MapManager;
- 83 84#define m_begin(g, i)(g).h[(i)] 85#define m_end(g, i)(g).edge[(i)].end 86#define m_next(g, i)(g).edge[(i)].next 87#define m_cap(g, i)(g).edge[(i)].cap 88#define m_flow(g, i)(g).edge[(i)].flow 89 ///map template ends
- 90 91 int n,
- m;
- 92 int t;
- 93 MapManager g;
- 94 95 inline boolean init() {
- 96
- if (!readInteger(n)) return false;
- 97 readInteger(m);
- 98 t = n + m + 1;
- 99 g = MapManager(t + 1, (n + 1) * (m + 1) * 2);
- 100
- for (int i = 1, a, b; i <= n; i++) {
- 101 readInteger(a);
- 102
- while (a--) {
- 103 readInteger(b);
- 104 g.addDoubleEdge(i, b + n, 1);
- 105
- }
- 106
- }
- 107
- for (int i = 1; i <= n; i++) 108 g.addDoubleEdge(0, i, 1);
- 109
- for (int i = 1; i <= m; i++) 110 g.addDoubleEdge(i + n, t, 1);
- 111
- return true;
- 112
- }
- 113 114 boolean * visited;
- 115 int * divs;
- 116 queue < int > que;
- 117 118 inline boolean getDivs() {
- 119 memset(visited, false, sizeof(boolean) * (t + 1));
- 120 divs[0] = 1;
- 121 visited[0] = true;
- 122 que.push(0);
- 123
- while (!que.empty()) {
- 124 int e = que.front();
- 125 que.pop();
- 126
- for (int i = m_begin(g, e); i != 0; i = g[i].next) {
- 127 int & eu = g[i].end;
- 128
- if (!visited[eu] && g[i].flow < g[i].cap) {
- 129 divs[eu] = divs[e] + 1;
- 130 visited[eu] = true;
- 131 que.push(eu);
- 132
- }
- 133
- }
- 134
- }
- 135
- return visited[t];
- 136
- }
- 137 138 int blockedflow(int node, int minf) {
- 139
- if (node == t || minf == 0) return minf;
- 140 int f,
- flow = 0;
- 141
- for (int i = m_begin(g, node); i != 0; i = m_next(g, i)) {
- 142 int & e = g[i].end;
- 143
- if (divs[e] == divs[node] + 1 && visited[e] && (f = blockedflow(e, min(minf, g[i].cap - g[i].flow))) > 0) {
- 144 flow += f;
- 145 g[i].flow += f;
- 146 g[g.reverse(i)].flow -= f;
- 147 minf -= f;
- 148
- if (minf == 0) return flow;
- 149
- }
- 150
- }
- 151
- return flow;
- 152
- }
- 153 154 inline int maxflow() {
- 155 visited = new boolean[(const int)(t + 1)];
- 156 divs = new int[(const int)(t + 1)];
- 157 int res = 0;
- 158
- while (getDivs()) {
- 159 res += blockedflow(0, INF);
- 160
- }
- 161
- return res;
- 162
- }
- 163 164 inline void solve() {
- 165 int res = maxflow();
- 166 cout << res << endl;
- 167
- }
- 168 169 inline void clear() {
- 170 delete[] visited;
- 171 delete[] divs;
- 172 g.clear();
- 173
- }
- 174 175 int main() {
- 176
- while (init()) {
- 177 solve();
- 178 clear();
- 179
- }
- 180
- return 0;
- 181
- }
来源: