[Poj #1636] Prison Rearrangement

二元关系可以用图来维护。
对罪犯i，记录如果i换监狱，那么多少个人会从A监狱到B监狱，多少人又会从B监狱到A监狱。（这是个连锁反应）
然后dp，f[i][j]表示i个人过去j个人过来是否可行。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge
{
    int v,last;
}e[20010];
int in[10010],cnt=0;
void addedge(int x,int y)
{
    e[++cnt].v=y;
    e[cnt].last=in[x];
    in[x]=cnt;
}
int n;
int a,b;
bool vis[10010];
int f[1010][1010];
int p[10010],q[10010],top;
void dfs(int cur)
{
    int i,t;
    vis[cur]=1;
    if(cur<=n)a++;
    else b++;
    for(i=in[cur];i;i=e[i].last)
    {
        t=e[i].v;
        if(vis[t])continue;
        dfs(t);
    }
}
int main()
{
    int T,m,i,j,k,x,y,z;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(vis,0,sizeof(vis));
        cnt=0;
        memset(f,0,sizeof(f));
        memset(in,0,sizeof(in));
        top=0;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            addedge(x,y+n);
            addedge(y+n,x);
        }
        for(i=1;i<=n*2;i++)
        {
            if(vis[i])continue;
            a=b=0;
            dfs(i);
            p[++top]=a;
            q[top]=b;
        }
        f[0][0]=1;
        for(i=1;i<=top;i++)
        {
            for(j=n/2;j>=p[i];j--)
            {
                for(k=n/2;k>=q[i];k--)
                {
                    f[j][k]|=f[j-p[i]][k-q[i]];
                }
            }
        }
        for(i=n/2;~i;i--)if(f[i][i])break;
        printf("%d\n",i);
    }
    return 0;
}