程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> (圖論算法之2分匹配) hdu 1281（棋盤游戲）

(圖論算法之2分匹配) hdu 1281（棋盤游戲）

編輯：C++入門知識

(圖論算法之2分匹配) hdu 1281（棋盤游戲）

題意：給一個n*m的棋盤，在上面放上車，放的車之間不能相互攻擊(在同一行或者同一列就能相互攻擊)，並且只有某些點能放車。問最多能放多少車，其中有多少個格子必須放才能放最多的車。

這是一道很好的理解匈牙利算法的題目。首先我們求最多放多少車，這是一個行列匹配問題。假設我們用n個左邊的點代表行，m個右邊的點放在右邊，如果一個格子(x,y)能放車，那麼將左邊的x和右邊的y連接一起建一條邊。這個一個很經典的模型，就不必多少了。用匈牙利算法求一次最大匹配。

後面這一問很好。首先我說說最暴力的方法。記錄下最大匹配的中的匹配邊，然後再原圖中去掉這條邊，看最大匹配是否和原來的相等。一次匈牙利的復雜度是O（n*m^2).

總共n次匈牙利，總的復雜度是O（n^2*m^2），對於這題100的數據是能AC的。但是如果數據量增加就要換個方法了。實際上，在求出最大匹配以後，假設(x->y)是最大匹配中的一條邊，我們首先刪掉這條邊，並且使y失陪。此時為x尋找增光路，如果能找到，說明我們用另外的一個匹配代替了匹配（x->y）,所以(x->y)並非必須的。否者，（x->y）是必須的。注意：如果（x->y）是必須的，那麼要 link[y]=x 是的x再次匹配y 到達最大匹配。另外：不管(x->)是不是必須的，都必須還原圖。

方法一暴力：

VIEW CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mod=99999997;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3fffffff;

bool G[110][110];
int link[110];
int n,m;
bool vis[110];
bool match(int x)
{
    for(int i=1;i<=m;i++)
    {
        if(G[x][i]&&(!vis[i]))
        {
            vis[i]=1;
            if(link[i]==-1||match(link[i]))
            {
                link[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int hungury()
{
    int ans=0;
    memset(link,-1,sizeof link);
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof vis);
        if(match(i))
            ans++;
    }
    return ans;
}
int link__[110];
int main()
{
    int k,ca=0;
    while(cin>>n>>m>>k)
    {
        memset(G,0,sizeof G);
        while(k--)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            G[x][y]=1;
        }
        int aa=hungury();
        int ans=0;
        for(int i=1;i<=m;i++)
            link__[i]=link[i];
        for(int i=1;i<=m;i++)
        {
            if(link__[i]+1)
            {
                int x=link__[i];
                G[x][i]=0;
                if(hungury()!=aa)
                    ans++;
                G[x][i]=1;
            }
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",++ca,ans,aa);
    }
    return 0;
}

方法2: 一次找增廣路

VIEW CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mod=99999997;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3fffffff;

bool G[110][110];
int link[110];
int n,m;
bool vis[110];
bool match(int x)
{
    for(int i=1;i<=m;i++)
    {
        if(G[x][i]&&(!vis[i]))
        {
            vis[i]=1;
            if(link[i]==-1||match(link[i]))
            {
                link[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int hungury()
{
    int ans=0;
    memset(link,-1,sizeof link);
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof vis);
        if(match(i))
            ans++;
    }
    return ans;
}
int main()
{
    int k,ca=0;
    while(cin>>n>>m>>k)
    {
        memset(G,0,sizeof G);
        while(k--)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            G[x][y]=1;
        }
        int aa=hungury();
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            if(link[i]+1)
            {
                int x=link[i];
                G[x][i]=0;
                link[i]=-1;
                memset(vis,0,sizeof vis);
                if(!match(x))
                {
                    ans++;
                    link[i]=x;
                }
                G[x][i]=1;
            }
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",++ca,ans,aa);
    }
    return 0;
}