匈牙利算法

匈牙利算法的本质是，不停地进行搜索找增广路，最后求出它的最大匹配.

以HDU2444为例，这道题先让判断是否是二分图，如果是求出它的最大匹配，那么就先用染色法，然后再用匈牙利算法

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int N=200+20;
int color[N],vis[N],match[N],n,m,pre;
vector<int>G[N];
int judge()//染色法判断二分图
{
    queue<int>q;
    q.push(pre);
    color[pre]=1;
    while(!q.empty())
    {
        int v1=q.front();
        q.pop();
        for(int i=0; i<G[v1].size(); i++)
        {
            int v2=G[v1][i];
            if(color[v2]==-1)
            {
                color[v2]=-color[v1];
                q.push(v2);
            }
            else if(color[v1]==color[v2])
                return 0;
        }
    }
    return 1;
}
int dfs(int u)
{
    for(int i=0; i<G[u].size(); i++)
    {
        int v=G[u][i];
        if(!vis[v])
        {
            vis[v]=1;
            if(match[v]==-1||dfs(match[v]))
            {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int a,b;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0; i<N; i++)G[i].clear();
        mem(color,-1);
        mem(match,-1);
        pre=0;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            if(!pre)pre=a;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        if(!judge())puts("No");
        else
        {
            int sum=0;
            for(int i=1; i<=n; i++)
            {
                mem(vis,0);
                if(dfs(i))sum++;
            }
            printf("%d\n",sum/2);
        }
    }
    return 0;
}

第二种模板：

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int N=1000+20;
int e[N][N],vis[N],match[N],n;
int dfs(int u)
{
    for(int i=1; i<=num; i++)
    {
        if(e[u][i]&&!vis[i])
        {
            vis[i]=1;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int query()
{
    mem(match,0);
    int sum=0;
    for(int i=1; i<=num; i++)
    {
        mem(vis,0);
        if(dfs(i))sum++;
    }
    return sum;
}

HDU4185 Oil Skimming(二分图匹配,匈牙利算法)

有一个石油大亨要在一片N∗N区域里面打捞石油，它的网能网住的区域面积是1×2，#代表这个地方是石油，.代表这个地方是海水，问在这一片水域，最多能打捞多少石油（不能石油和海水一起捞）

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int N=1000+20;
int e[N][N],vis[N],match[N],n,temp[N][N],num;
char s[N][N];
int dfs(int u)
{
    for(int i=1; i<=num; i++)
    {
        if(e[u][i]&&!vis[i])
        {
            vis[i]=1;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int query()
{
    mem(match,0);
    int sum=0;
    for(int i=1; i<=num; i++)
    {
        mem(vis,0);
        if(dfs(i))sum++;
    }
    return sum;
}
int main()
{
    int t,q=1;
    scanf("%d",&t);
    while(t--)
    {
        mem(temp,0);
        mem(e,0);
        num=0;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%s",s[i]+1);
            for(int j=1; j<=n; j++)
                if(s[i][j]=='#')
                    temp[i][j]=++num;
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(s[i][j]=='#')
                {
                    if(i!=1&&s[i-1][j]=='#') e[temp[i][j]][temp[i-1][j]]=1;
                    if(j!=1&&s[i][j-1]=='#') e[temp[i][j]][temp[i][j-1]]=1;
                    if(i!=n&&s[i+1][j]=='#') e[temp[i][j]][temp[i+1][j]]=1;
                    if(j!=n&&s[i][j+1]=='#') e[temp[i][j]][temp[i][j+1]]=1;
                }
        printf("Case %d: %d\n",q++,query()/2);
    }
    return 0;
}