HDU4185-Oil Skimming(二分图最大匹配)

题目链接:HDU4185-Oil Skimming

题意:

给一个n×n的地图,上面有一些油井,相邻的两个油井可以匹配在一起,同一个油井最多只能和一个油井匹配,问最大匹配数。

题解:

对于每个油井编号之后建图,建无向图,注意最后的答案需要除以2。

参考代码:

#include<bits/stdc++.h>
using namespace std;
int T,n,tot;
bool vis[10004];
int id[102][102],dir[5][3];
int match[10004];
char mp[102][102];
struct EDGE
{
    int v,nxt;
}edge[100005];
int cnt,fir[10004];
void addedge(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
bool dfs(int u)
{
    for(int i=fir[u];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            if(match[v]==-1||dfs(match[v]))
            {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int MaxMatch()
{
    int sum=0;
    memset(match,-1,sizeof(match));
    for(int i=1;i<=tot;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            sum++;
    }
    return sum;
}
int main()
{
    int icase=0;
    scanf("%d",&T);
    dir[1][1]=1;dir[2][1]=0;
    dir[1][2]=0;dir[2][2]=1;
    while(T--)
    {
        scanf("%d",&n);
        memset(fir,-1,sizeof(fir));
        memset(id,0,sizeof(id));
        cnt=tot=0;
        for(int i=1;i<=n;i++)
            scanf("%s",mp[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(mp[i][j]=='#')
                    id[i][j]=++tot;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(mp[i][j]!='.')
            {
                for(int k=1;k<=2;k++)
                {
                    int tx=i+dir[k][1];
                    int ty=j+dir[k][2];
                    if(tx<1||ty<1||tx>n||ty>n||mp[tx][ty]!='#')
                        continue;
                    addedge(id[i][j],id[tx][ty]);
                    addedge(id[tx][ty],id[i][j]);
                }
            }
           
        }
        int ans=MaxMatch();
        printf("Case %d: %d\n",++icase,ans/2);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。