PBCWAYS - Trò chơi di chuyển con tốt
Tác giả: flashmt
Ngôn ngữ: C++
#include<iostream>
#include<algorithm>
#include<cstdio>
#define fr(a,b,c) for(a=b;a<=c;a++)
#define oo 1000111222
#define maxn 1111
using namespace std;
int m,n,s,t,c[maxn][maxn],f[maxn][maxn],q[maxn],d[maxn],a[maxn][maxn],sl[maxn];
int find(int n)
{
int x,y,i=1,nq=1,j;
fr(x,1,n) d[x]=0;
d[s]=s; q[1]=s;
while (i<=nq)
{
x=q[i++];
fr(j,1,sl[x])
{
y=a[x][j];
if (!d[y])
{
if (!f[x][y] && c[x][y]) { q[++nq]=y; d[y]=x; }
else
if (f[y][x]) { q[++nq]=y; d[y]=-x; }
if (d[t]) return 1;
}
}
}
return 0;
}
void incflow()
{
int x=t,y;
while (x!=s)
{
y=x; x=d[x];
if (x>0) f[x][y]++;
else x=-x,f[y][x]--;
}
}
int main()
{
int i,x,y,v,k,j;
cin >> m >> n;
s=m*n*2+1, t=s+1;
fr(i,1,m)
{
x=n*m*2+1-i;
c[s][i]=c[x][t]=1;
a[s][++sl[s]]=i; a[i][++sl[i]]=s;
a[x][++sl[x]]=t; a[t][++sl[t]]=x;
}
fr(i,1,m)
{
x=n*m+1-i;
c[x][x+n*m]=1;
a[x][++sl[x]]=x+n*m; a[x+m*n][++sl[x+n*m]]=x;
}
fr(i,1,n-1)
{
fr(j,1,m)
{
x=(i-1)*m+j+m*n;
c[x-m*n][x]=1;
a[x][++sl[x]]=x-m*n; a[x-m*n][++sl[x-m*n]]=x;
scanf("%d",&k);
while (k--)
{
scanf("%d",&v);
y=i*m+v;
c[x][y]=1;
a[x][++sl[x]]=y; a[y][++sl[y]]=x;
}
}
}
while (find(m*n*2+2)) incflow();
int re=0;
fr(i,1,m) re+=f[s][i];
cout << re << endl;
return 0;
}