PBCWAYS - Trò chơi di chuyển con tốt
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 55
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
const int INF=(int)1e9+7;
class DinicFlow {
private:
vector<int> dist,head,q,work;
vector<int> capa,flow,next,point;
int n,m;
public:
DinicFlow() {
n=0;m=0;
}
DinicFlow(int n,int _m) {
this->n=n;
this->m=0;
dist=vector<int>(n+7);
head=vector<int>(n+7,-1);
q=vector<int>(n+7);
work=vector<int>(n+7);
int m=2*_m;
capa=vector<int>(m+7);
flow=vector<int>(m+7,0);
next=vector<int>(m+7);
point=vector<int>(m+7);
}
void addedge(int u,int v,int c1,int c2) {
point[m]=v;capa[m]=c1;flow[m]=0;next[m]=head[u];head[u]=m;m++;
point[m]=u;capa[m]=c2;flow[m]=0;next[m]=head[v];head[v]=m;m++;
}
bool bfs(int s,int t) {
FORE(it,dist) *it=-1;
int sz=1;
q[0]=s;dist[s]=0;
REP(x,sz) {
int u=q[x];
for (int i=head[u];i>=0;i=next[i])
if (dist[point[i]]<0 && flow[i]<capa[i]) {
dist[point[i]]=dist[u]+1;
q[sz]=point[i];
sz++;
}
}
return (dist[t]>=0);
}
int dfs(int s,int t,int f) {
if (s==t) return (f);
for (int &i=work[s];i>=0;i=next[i])
if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
int d=dfs(point[i],t,min(f,capa[i]-flow[i]));
if (d>0) {
flow[i]+=d;
flow[i^1]-=d;
return (d);
}
}
return (0);
}
int maxflow(int s,int t) {
int ret=0;
while (bfs(s,t)) {
FOR(i,1,n) work[i]=head[i];
while (true) {
int d=dfs(s,t,INF);
if (d<=0) break;
ret+=d;
}
}
return (ret);
}
};
int id[MAX][MAX];
vector<int> adj[MAX][MAX];
int n,m;
DinicFlow g;
void init(void) {
scanf("%d",&n);
scanf("%d",&m);
int ne=n*(m+2);
int tmp=0;
FOR(i,1,n) FOR(j,1,m) {
tmp++;
id[i][j]=tmp;
}
FOR(j,1,m-1) FOR(i,1,n) {
int t;
scanf("%d",&t);
REP(zz,t) {
int v;
scanf("%d",&v);
ne++;
adj[i][j].push_back(v);
}
}
g=DinicFlow(2*m*n+2,ne);
FOR(j,1,m-1) FOR(i,1,n) FORE(it,adj[i][j])
g.addedge(id[i][j],id[*it][j+1]+m*n,1,0);
FOR(i,1,n) FOR(j,1,m) g.addedge(id[i][j]+m*n,id[i][j],1,0);
FOR(i,1,n) g.addedge(2*m*n+1,id[i][1]+m*n,1,0);
FOR(i,1,n) g.addedge(id[i][m],2*m*n+2,1,0);
printf("%d",g.maxflow(2*m*n+1,2*m*n+2));
}
int main(void) {
init();
return 0;
}