PBCWAYS - Trò chơi di chuyển con tốt
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct Node {
vector<pair<Node*, pair<int,int>* > > ke;
vector<pair<Node*, pair<int,int>* > > ken;
int ind;
};
int m, n, sl;
Node *dau[55][15], *cuoi[55][15];
Node *st, *en;
Node *L[10000];
pair<int,int> *edge[10000];
int ng[10000];
int soluong;
void noi( Node &a, Node &b, int cap) {
pair<int,int> *p = new pair<int,int>(cap,0);
a.ke.push_back(make_pair(&b, p));
b.ken.push_back(make_pair(&a, p));
}
void tang() {
Node *v = en;
++soluong;
while(L[v->ind] != v) {
Node *u = L[v->ind];
if(ng[v->ind]) edge[v->ind]->second--;
else edge[v->ind]->second++;
v = u;
}
}
bool bfs() {
queue<Node*> q;
q.push(st);
memset( L, 0, sizeof(L));
memset( ng, 0, sizeof(ng));
L[st->ind] = st;
while(!q.empty()) {
Node * u = q.front(); q.pop();
for( int kk=0; kk<u->ke.size(); ++kk) {
Node *v = u->ke[kk].first;
pair<int,int> &pii = *u->ke[kk].second;
if(pii.first>pii.second && L[v->ind]==NULL) {
L[v->ind] = u;
edge[v->ind] = &pii;
ng[v->ind] = false;
q.push(v);
}
}
for(int kk=0; kk<u->ken.size(); ++kk) {
Node *v = u->ken[kk].first;
pair<int,int> &pii = *u->ken[kk].second;
if(pii.second>0 && L[v->ind]==NULL) {
L[v->ind] = u;
edge[v->ind] = &pii;
ng[v->ind] = true;
q.push(v);
}
}
if(L[en->ind]!=NULL) {
tang();
return true;
}
}
return false;
}
int main() {
scanf("%d%d", &m, &n);
for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) {
dau[i][j] = new Node();
dau[i][j]->ind = ++sl;
cuoi[i][j] = new Node();
cuoi[i][j]->ind = ++sl;
noi( *dau[i][j], *cuoi[i][j], 1);
}
for(int j=1;j<n;++j) {
for(int i=1;i<=m;++i) {
int c;
scanf("%d", &c);
for(int k=0;k<c;++k) {
int x;
scanf("%d", &x);
noi( *cuoi[i][j], *dau[x][j+1], 1);
}
}
}
st = new Node();
st->ind = ++sl;
for(int i=1;i<=m;++i) noi( *st, *dau[i][1], 1);
en = new Node();
en->ind = ++sl;
for(int i=1;i<=m;++i) noi( *cuoi[i][n], *en, 1);
while(bfs());
cout << soluong << endl;
return 0;
}