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;
}

Download