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
| #include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "queue"
#include "cmath"
#include "vector"
using namespace std;
#define mem(a) memset( a , 0 , sizeof a )
class maxFlow {
public:
typedef long long ll;
std::queue<int> q;
std::vector<int> head, cur, nxt, to, dep;
std::vector<ll> cap;
maxFlow(int _n = 0) { init(_n); }
void init(int _n) {
head.clear();
head.resize(_n + 1, 0);
nxt.resize(2);
to.resize(2);
cap.resize(2);
}
void init() { init(head.size() - 1); }
int add(int u, int v, ll w) {
nxt.push_back(head[u]);
int x = ( head[u] = to.size() );
to.push_back(v);
cap.push_back(w);
return x;
}
int Add(int u, int v, ll w) {
add(u, v, w);
return add(v, u, 0);
}
void del(int x) { cap[x << 1] = cap[x << 1 | 1] = 0; }
bool bfs(int s, int t, int delta) {
dep.clear();
dep.resize(head.size(), -1);
dep[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
ll w = cap[i];
if (w >= delta && dep[v] == -1) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return ~dep[t];
}
ll dfs(int u, ll flow, int t, int delta) {
if (dep[u] == dep[t])
return u == t ? flow : 0;
ll out = 0;
for (int& i = cur[u]; i; i = nxt[i]) {
int v = to[i];
ll w = cap[i];
if (w >= delta && dep[v] == dep[u] + 1) {
ll f = dfs(v, std::min(w, flow - out), t, delta);
cap[i] -= f;
cap[i ^ 1] += f;
out += f;
if (out == flow)
return out;
}
}
return out;
}
ll maxflow(int s, int t) {
ll out = 0;
ll maxcap = *max_element(cap.begin(), cap.end());
for (ll delta = 1ll << int(log2(maxcap) + 1e-12); delta; delta >>= 1) {
while (bfs(s, t, delta)) {
cur = head;
out += dfs(s, 0x7fffffffffffffffll, t, delta);
}
}
return out;
}
ll getflow(int x) const { return cap[x << 1 | 1]; }
} F ;
int n , m , k , s = 200 , t = 201;
int c[26];
int main() {
int T;cin >> T; int kase = 0;
while( T-- ) {
scanf("%d%d",&n,&m);
F.init( 1000 );
scanf("%d",&k);
mem( c );
for( int i = 1 , a ; i <= k ; ++ i ) scanf("%d",&a) , ++ c[a];
for( int i = 1 ; i <= m ; ++ i ) if( c[i] ) F.Add( s , i , c[i] );
for( int i = 1 ; i <= m ; ++ i ) F.Add( i , t , 1 );
for( int i = 2 ; i <= n ; ++ i ) {
scanf("%d",&k); mem( c );
for( int j = 1 , a ; j <= k ; ++ j ) scanf("%d",&a) , ++ c[a];
for( int j = 1 ; j <= m ; ++ j )
if( c[j] > 1 ) F.Add( i + m , j , c[j] - 1 ); else if( !c[j] ) F.Add( j , i + m , 1 );
}
printf("Case #%d: %lld\n",++kase,F.maxflow( s , t ));
}
}
|
