PBCWAYS - Trò chơi di chuyển con tốt
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int M = 50, N = 10, INF = 1e9;
vector<pair<int, int> > g[2*(M*N+1)];
vector<int> c, f;
int m, n;
void addEdge(int u, int v, int lim) {
g[u].push_back(make_pair(v, c.size()));
g[v].push_back(make_pair(u, c.size()+1));
c.push_back(lim); c.push_back(0);
f.push_back(0); f.push_back(0);
}
int maxflow(int s, int t, int n) {
int maxf = 0;
while(true) {
vector<pair<int, int> > tr (n, make_pair(INF, INF));
queue<int> q; q.push(s); tr[s] = make_pair(-1, -1);
while(!q.empty()) {
int u = q.front(); q.pop();
if(u == t) break;
TR(g[u], it) {
int v = it->first, e = it->second;
if(c[e] - f[e] > 0 && tr[v].first == INF)
tr[v] = make_pair(u, e), q.push(v);
}
}
if(tr[t].first == INF) break;
int delta = INF;
for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first)
delta = min(delta, c[tr[v].second] - f[tr[v].second]);
for(int u = tr[t].first, v = t; u != -1; v = u, u = tr[u].first) {
f[tr[v].second] += delta;
f[tr[v].second ^ 1] -= delta;
}
maxf += delta;
}
return maxf;
}
void enter() {
cin >> m >> n;
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
addEdge(n*i+j, n*i+j+m*n, 1);
for(int j = 0; j < n-1; ++j) {
for(int i = 0; i < m; ++i) {
int k; cin >> k;
while(k-- > 0) {
int u; cin >> u; --u;
addEdge(n*i+j+m*n, n*u+j+1, 1);
}
}
}
for(int i = 0; i < m; ++i) {
addEdge(2*m*n, n*i, 1);
addEdge(n*(i+1)-1+m*n, 2*m*n+1, 1);
}
}
int main() {
ios::sync_with_stdio(false);
enter();
cout << maxflow(2*m*n, 2*m*n+1, 2*(m*n+1)) << '\n';
return 0;
}