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

Download