hdu4619 / 最大独立集

题意，一个矩阵，上面可以横放或者竖着放骨牌（1X2）保证横的与横的不重叠，竖的和竖的不重叠，求拿掉最小的牌，使所有的都不重叠。

分析：一看，不重叠就是没有边，拿最少，就是留最多，最大独立集啊！二分图，n+m个-最大流（最大匹配）=ans。

简单题。

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxv=2005,maxe=10001;

struct ka

{

    int x,y;

};

int n,m;int ss,tt;

ka xx[1005];ka yy[1005];

int nume=0;int e[maxe][3];int head[maxv];

void inline adde(int i,int j,int c)

{

    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;

    e[nume++][2]=c;

    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;

    e[nume++][2]=0;

}

int lev[maxv];int vis[maxv];

bool bfs()

{

    memset(lev,0,sizeof(lev));

    memset(vis,0,sizeof(vis));

    queue<int>q;

    vis[ss]=1;

    q.push(ss);

    while(!q.empty())

    {

        int cur=q.front();

        q.pop();

        for(int i=head[cur];i!=-1;i=e[i][1])

        {

            int v=e[i][0];

          if(!vis[v]&&e[i][2]>0)

          {

              lev[v]=lev[cur]+1;

              q.push(v);

              vis[v]=1;

          }

        }

    }

    return vis[tt];

}

int dfs(int u,int minf)

{

    if(u==tt||minf==0)return minf;

    int sumf=0,f;

     for(int i=head[u];i!=-1&&minf;i=e[i][1])

     {

         int v=e[i][0];

         if(lev[v]==lev[u]+1&&e[i][2]>0)

         {

             f=dfs(v,minf<e[i][2]?minf:e[i][2]);

             minf-=f;

             sumf+=f;

             e[i][2]-=f;e[i^1][2]+=f;

         }

     }

    if(!sumf)lev[u]=-1;

     return sumf;

}

int dinic()

{

    int sum=0;

    while(bfs())sum+=dfs(ss,inf);

    return sum;

}

void read_build()

{

     for(int i=0;i<n;i++)

           scanf("%d%d",&xx[i].x,&xx[i].y);

     for(int j=0;j<m;j++)

           scanf("%d%d",&yy[j].x,&yy[j].y);

     for(int i=0;i<n;i++)

       for(int j=0;j<m;j++)

       {

           if(xx[i].x==yy[j].x&&xx[i].y==yy[j].y)

             adde(i,n+j,1);

           else if(xx[i].x==yy[j].x&&xx[i].y==yy[j].y+1)

             adde(i,n+j,1);

           else if(xx[i].x+1==yy[j].x&&xx[i].y==yy[j].y)

             adde(i,n+j,1);

           else if(xx[i].x+1==yy[j].x&&xx[i].y==yy[j].y+1)

             adde(i,n+j,1);

       }

         for(int i=0;i<n;i++)

            adde(ss,i,1);

        for(int i=0;i<m;i++)

            adde(i+n,tt,1);

    /*   for(int i=0;i<n+m+2;i++)

          for(int j=head[i];j!=-1;j=e[j][1])

            printf("%d->%d:%d\n",i,e[j][0],e[j][2]);*/

}

void init()

{

    nume=0;

    memset(head,-1,sizeof(head));

    ss=n+m;

    tt=n+m+1;

}

int main()

{

    while(~scanf("%d%d",&n,&m)&&(n+m))

    {

       init();

       read_build();

       int ans=dinic();

       printf("%d\n",n+m-ans);

    }

    return 0;

}

巴特西

hdu4619 / 最大独立集

最新文章

热门文章