【CODEVS】1022 覆盖

【算法】二分图匹配(最大流)

【题解】对i+j进行奇偶染色，就可以保证相邻两格异色。

然后就是二分图了，对相邻格子连边跑最大流即可。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=,maxN=,inf=0x3f3f3f3f;

struct edge{int from,v,flow;}e[];

int n,m,k,tot=,first[maxN],p[maxn][maxn],cnt,d[maxN],q[],S,T,cur[maxN];

long long ans;

void insert(int u,int v,int flow)

{

    tot++;e[tot].v=v;e[tot].flow=flow;e[tot].from=first[u];first[u]=tot;

    tot++;e[tot].v=u;e[tot].flow=;e[tot].from=first[v];first[v]=tot;

}

bool bfs()

{

    memset(d,-,sizeof(d));

    int head=,tail=;q[]=S;d[]=;

    while(head!=tail)

     {

         int x=q[head++];if(head>=)head=;

         for(int i=first[x];i;i=e[i].from)

          if(e[i].flow&&d[e[i].v]==-)

           {

               d[e[i].v]=d[x]+;

               q[tail++]=e[i].v;if(tail>=)tail=;

           }

     }

    return d[T]!=-;

}

int dfs(int x,int a)

{

    if(x==T||a==)return a;

    int flow=,f;

    for(int i=first[x];i;i=e[i].from)

     if(d[e[i].v]==d[x]+&&(f=dfs(e[i].v,min(a,e[i].flow)))>)

      {

          e[i].flow-=f;

          e[i^].flow+=f;

          a-=f;

          flow+=f;

          if(a==)break;

      }

    return flow;

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    S=;

    for(int i=;i<=k;i++)

     {

         int u,v;

         scanf("%d%d",&u,&v);

         p[u][v]=-;

     }

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

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

      {

          if(p[i][j]!=-)

           {

               p[i][j]=++cnt;

           }

      }

    T=++cnt;

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

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

      {

          if(p[i][j]!=-)

           {

               if((i+j)&)

                {

                    if(i>&&p[i-][j]>)insert(p[i][j],p[i-][j],);

                   if(i<n&&p[i+][j]>)insert(p[i][j],p[i+][j],);

                   if(j>&&p[i][j-]>)insert(p[i][j],p[i][j-],);

                   if(j<n&&p[i][j+]>)insert(p[i][j],p[i][j+],);

                   insert(S,p[i][j],);

                }

               else insert(p[i][j],T,);

           }

      }

    ans=;

    while(bfs())

     {

         for(int i=;i<=tot;i++)cur[i]=first[i];

         ans+=dfs(S,inf);

     }

    printf("%lld",ans);

    return ;

}