hdu 4185 （Oil Skimming） 奇偶匹配

   通过题意我们可以看出，一块地如果是油田，那么如果他要组成一块地，必须和周围的4块中的一块组成。那么可以得到，坐标和（i+j）是奇数的油田必须和坐标和为偶数的匹配才能组成一块地。那么我们可以把偶数油田看成是左边的点，奇数油田看成右边的点， 如果左边的点能和右边的点组成一块地 ， 就建一条边 。 这样可以得到一个2分图。对2图求最大匹配，就是答案。  求2分匹配有2中方法 ，匈牙利算法和网络流算法。 这题2种算法时间复杂度都是够的 。 

方法一：匈牙利算法

VIEW CODE

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<stdlib.h>
using namespace std;
const int mod=99999997;
const int mmax=610;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3fffffff;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
    int st,en;
    int next;
}E[4*mmax*mmax];
int p[mmax*mmax];
int num,n;
void init()
{
    memset(p,-1,sizeof p);
    num=0;
}
void add(int st,int en)
{
    E[num].st=st;
    E[num].en=en;
    E[num].next=p[st];
    p[st]=num++;
}
int Id[mmax][mmax];
char G[mmax][mmax];
int get_id(int x,int y)
{
    return x*n+y;
}
bool in(int x,int y)
{
    return 0<=x&&x<n&&0<=y&&y<n;
}
void make(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(in(tx,ty)&&G[tx][ty]=='#')
        {
            add(get_id(x,y),get_id(tx,ty));
        }
    }
}
bool use[mmax*mmax];
int link[mmax*mmax];
bool match(int x)
{
    for(int i=p[x];i+1;i=E[i].next)
    {
        if(!use[E[i].en])
        {
            use[E[i].en]=1;
            if(link[E[i].en]==-1||match(link[E[i].en]))
            {
                link[E[i].en]=x;
                return 1;
            }
        }
    }
    return 0;
}
int hungury(int m)
{
    int ans=0;
    memset(link,-1,sizeof link);
    for(int i=0;i<m;i++)
    {
        memset(use,0,sizeof use);
        if(match(i))
            ans++;
    }
    return ans;
}
int main()
{
    int t;
    int ca=0;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
            scanf("%s",G[i]);
        init();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if((i+j)%2==0&&G[i][j]=='#')
                {
                    make(i,j);
                }
            }
        }
        int ans=hungury(n*n);
        printf("Case %d: %d\n",++ca,ans);
    }
    return 0;
}
           

方法2： 网络流 (dinic )

VIEW CODE

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<stdlib.h>
using namespace std;
const int mod=99999997;
const int mmax=610;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3fffffff;
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
    int st,en;
    int flow;
    int next;
}E[4*mmax*mmax];
int p[mmax*mmax];
int num,n;
void init()
{
    memset(p,-1,sizeof p);
    num=0;
}
void add(int st,int en,int flow)
{
    E[num].st=st;
    E[num].en=en;
    E[num].flow=flow;
    E[num].next=p[st];
    p[st]=num++;
    E[num].st=en;
    E[num].en=st;
    E[num].flow=0;
    E[num].next=p[en];
    p[en]=num++;
}
int d[mmax*mmax];
bool vis[mmax*mmax];
int qq[mmax*mmax];
int cur[mmax*mmax];
bool bfs(int st,int en)
{
    memset(vis,0,sizeof vis);
    int qcnt=0;
    qq[++qcnt]=st;
    d[st]=0;
    vis[st]=1;
    while(qcnt)
    {
        int x=qq[qcnt];
        qcnt--;
        for(int i=p[x];i+1;i=E[i].next)
        {
            int v=E[i].en;
            if(!vis[v]&&E[i].flow)
            {
                vis[v]=1;
                qq[++qcnt]=v;
                d[v]=d[x]+1;
            }
        }
    }
    return vis[en];
}

int dfs(int st,int en,int flow)
{
    if(st==en|| flow==0)
        return flow;
    int f=0,dd;
    for(int &i=cur[st];i+1;i=E[i].next)
    {
        int v=E[i].en;
        if(d[st]+1==d[v] && (dd=dfs(v,en,min(flow,E[i].flow) )  )>0 )
        {
            E[i].flow-=dd;
            E[i^1].flow+=dd;
            flow-=dd;
            f+=dd;
            if(flow==0)
                break;
        }
    }
    return f;
}
int Dinic(int st,int en,int m)
{
    int flow=0;
    while(bfs(st,en))
    {
        for(int i=0;i<=m;i++)
            cur[i]=p[i];
        flow+=dfs(st,en,inf);
    }
    return flow;
}
int Id[mmax][mmax];
char G[mmax][mmax];
int get_id(int x,int y)
{
    return x*n+y;
}
bool in(int x,int y)
{
    return 0<=x&&x<n&&0<=y&&y<n;
}
void make(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(in(tx,ty)&&G[tx][ty]=='#')
        {
            add(get_id(x,y),get_id(tx,ty),1);
        }
    }
}
int main()
{
    int t;
    int ca=0;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
            scanf("%s",G[i]);
        init();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if((i+j)%2==0&&G[i][j]=='#')
                {
                    add(n*n,get_id(i,j),1);
                    make(i,j);
                }
                else
                    add(get_id(i,j),n*n+1,1);
            }
        }

        int ans=Dinic(n*n,n*n+1,n*n+1);
        printf("Case %d: %d\n",++ca,ans);
    }
    return 0;
}