hdu4619

题解：

最大独立集问题

显然对于每一对交叉的建边

然后求出最大独立集

最大独立集=n-最大匹配

代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=20005;
int x[N],f[N],match[N],y[N],fi[N],num,ne[N],zz[N],n,m;
int dfs(int x)
{
    for (int i=fi[x];i;i=ne[i])
     if (!f[zz[i]])
      {
          f[zz[i]]=1;
          if (!match[zz[i]]||dfs(match[zz[i]]))
           {
               match[zz[i]]=x;
               return 1;
           }
      }
    return 0; 
}
void jb(int x,int y)
{
    ne[++num]=fi[x];
    fi[x]=num;
    zz[num]=y;
}
int main()
{
    while (~scanf("%d%d",&n,&m),n||m)
     {
         memset(fi,0,sizeof fi);
         memset(match,0,sizeof match);
         num=0;
         for (int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
         for (int i=1;i<=m;i++)scanf("%d%d",&x[i+n],&y[i+n]);
         for (int i=1;i<=n;i++)
          for (int j=1;j<=m;j++)
           if (x[i]==x[j+n]&&(y[i]==y[j+n]||y[i]==y[j+n]+1)||
          x[i]+1==x[j+n]&&(y[i]==y[j+n]||y[i]==y[j+n]+1))jb(i,j);
        int ans=0;
        for (int i=1;i<=n;i++)
         {
             memset(f,0,sizeof f);
             ans+=dfs(i);
         }  
        printf("%d
",n+m-ans); 
     }
    return 0; 
}