传送门:http://poj.org/problem?id=1636
题意:有两个监狱,每个监狱有n个人,有m种关系,表示A监狱第i个人不能跟B监狱第j个人在一个监狱,问你最多能换几组人(从A,B监狱互换一个人,ans<=n/2)
方法:首先这是一个很明显的二分图,我们可以很轻松的建边,但交换一次要把所有与这两个人有关的情况都遍历一遍.dp[i][j]表示从A监狱换i个人再从B监狱换j个人是否可行.
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct node{
int a,b;
}guan[405];
int n,m,fa[405];
int find(int x)
{
if (fa[x]==x) return x;
else
{
guan[fa[x]].a+=guan[x].a;
guan[fa[x]].b+=guan[x].b;
guan[x].a=guan[x].b=0;
return fa[x]=find(fa[x]);
}
}
bool f[205][205];
int main()
{
int t;
cin>>t;
while (t--)
{
scanf("%d%d",&n,&m);
for (int i=1;i<=2*n;i++)//初始化
{
if (i<=n) guan[i].a=1,guan[i].b=0,fa[i]=i;
else guan[i].a=0,guan[i].b=1,fa[i]=i;
}
for (int i=1;i<=m;i++)//建边
{
int x,y;
scanf("%d%d",&x,&y);
y+=n;
int dx=find(x);
int dy=find(y);
if (dx!=dy)
{
if (dx<dy) fa[dy]=dx;
else fa[dx]=dy;
}
}
memset(f,false,sizeof(f));
f[0][0]=true;
for (int i=1;i<=2*n;i++)
{
find(i);
}
int fx=0,fy=0;
for (int i=1;i<=2*n;i++)//solve
{
int z=find(i);
int x=guan[z].a,y=guan[z].b;
if (x&&y)
{
for (int i=n/2;i>=x;i--)
for (int j=n/2;j>=y;j--)
{
if (i-x>=0&&j-y>=0&&f[i-x][j-y]) f[i][j]=true;
}
}
else if (x) fx++;
else if (y) fy++;
guan[z].a=guan[z].b=0;
}
int ans=0;
int y=min(fx,fy);
for (int i=0;i<=n/2;i++)//统计
for (int j=0;j<=n/2;j++)
if (f[i][j])
{
if (i==j)
ans=max(ans,i+y);
else if (i<=j&&i+fx>=j)
ans=max(ans,j+min(fx-j+i,fy));
else if (j<=i&&j+fy>=i)
ans=max(ans,i+min(fy-i+j,fx));
}
printf("%d\n",min(ans,n/2));
}
}