天天看點
傳回

二分比對算法學習篇水題集

目錄

  • 學習篇
    • 二分圖以及其最大比對
    • 匈牙利算法
    • 二分圖最大比對變形題
      • 最小頂點覆寫 || 最大獨立集
      • DAG圖的最小路徑覆寫
  • 水題集
    • hdu 2063：男女最大比對
    • hdu 1150：機器最少重新開機次數
    • hdu 1151：DAG最小覆寫路
    • hdu 1068：最大沒有聯系的男女個數
    • hdu 1281 ：騎士最大放置數

學習篇

二分圖以及其最大比對

一、什麼是二分圖

如果一個圖的頂點可以分為兩個集合X、Y, 圖的所有邊一定是有一個頂點屬于集合X，另一個頂點屬于集合Y， 則稱該圖為“二分圖”或“二部圖”。

二、二分圖的最大比對

在二分圖的應用中，最常見的就是求————最大比對，很多其他問題都可以轉化為比對問題來解決。

匈牙利算法

舉個例子：男女婚配（詳看hdu 2063

二分比對算法學習篇水題集

周遊左邊男的：

男1：周遊右邊女的， 從 女1 開始，有連線并且本輪沒用過，則男1 女1 比對 為一對

男2：周遊右邊女的，從 女1 開始，有連線并且本輪沒用過，但女1 有對象，則看看 其對象是否有另外的選擇，若有則 到目前為止一共比對兩對，若無則 隻有一對

二分圖最大比對變形題

最小頂點覆寫 || 最大獨立集

定義：用最少的頂點覆寫所有的邊

最小頂點覆寫=比對對數（詳看hdu 1150）

最大獨立集=總頂點數-比對數

DAG圖的最小路徑覆寫

定義：用最少的路覆寫所有的點（詳看hdu 1151

最小路覆寫=點的總數 - 最大比對

因為：比對一個，點就少一個

做法：X、Y集合均為相同的頂點，表示從X -> Y的頂點

水題集

hdu 2063：男女最大比對

hdu 2063

#include <bits/stdc++.h>
using namespace std;

int K,M,N,v[510],mp[510][510],p[510];
//mp[][]記錄兩頂點之間的連線，p用來儲存女生的對象，v标記數組

bool dfs(int i){//dfs的含義是 判斷該編号i的男生能否找到對象

    for(int j=1;j<=N;j++){//周遊女生
        if(mp[i][j]&&!v[j]){//若本輪有連線且沒用過的女生，則标記
            v[j]=1;
            if(!p[j] || dfs(p[j])){//若該女生沒有對象 或者 本來有對象但原來的對象能找到别的女生則可以讓 i編号的男生為 j編号的女生的對象
                p[j]=i;return 1;
            }
        }
    }
    return 0;//該男生沒找到對象
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>K){
        if(K==0)break;
        cin>>M>>N;
        int ans=0;
        memset(mp,0,sizeof mp);
        for(int i=1;i<=K;i++){
            int g,b;cin>>g>>b;
            mp[g][b]=1;
        }

        memset(p,0,sizeof(p));//将所有女生的對象初始化為一個值，且該值不等于任何男生的編号（-1或0）
        for(int i=1;i<=M;i++){
            memset(v,0,sizeof v);//每輪都要初始化
            if(dfs(i))ans++;//找到對象，比對數加加
        }
        cout<<ans<<endl;;
    }
    return 0;
}

hdu 1150：機器最少重新開機次數

hdu 1150

題意：兩個機器，初始模式均為0，變成下一個模式要重新開機，每個任務對于兩種機器有各自的模式，求兩種機器最少重新開機幾次才能完成所有任務

本質：最少頂點覆寫，邊的總數就是任務數，對應的兩種機器的模式就是兩個集合的點；

注意：機器本身就在0模式，是以要預處理一下：跟 0模式相連的點不需要 記錄兩點的連線

#include <bits/stdc++.h>
using namespace std;

int n,m,k,v[110],mp[110][110],p[110];


bool dfs(int i){
    for(int j=1;j<m;j++){
        if(mp[i][j] && !v[j]){
            v[j]=1;
            if(p[j]==-1 || dfs(p[j]) ){
                p[j]=i;return 1;
            }
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    while(cin>>n){
        if(n==0)break;
        cin>>m>>k;

        memset(mp, 0,sizeof mp);
        for(int i=0;i<k;i++){
            int a,b;cin>>i>>a>>b;
            if(a==0 ||b==0)continue;//預處理
            mp[a][b]=1;
        }
        int ans=0;
        memset(p,-1,sizeof p);//因為“對象”有編号為0的，是以初始化為-1
        for(int i=1;i<n;i++){
            memset(v,0,sizeof v);
            if(dfs(i))ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

hdu 1151：DAG最小覆寫路

hdu 1151

題意：給路口的數量、路的數量及其連通的方式（兩個路口編号）

本質：DAG圖的最小覆寫路

#include <bits/stdc++.h>
using namespace std;

int n,m,p[130],mp[130][130],v[130];

bool dfs(int i){
    for(int j=1;j<=n;j++){
        if(mp[i][j]&&!v[j]){
            v[j]=1;
            if(!p[j] || dfs(p[j])){
                p[j]=i;return 1;
            }
        }
    }
    return 0;
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        cin>>n>>m;

        memset(mp,0,sizeof mp);
        for(int i=1;i<=m;i++){
            int a,b;cin>>a>>b;
            mp[a][b]=1;
        }
        int ans=0;
        memset(p,0,sizeof p);
        for(int i=1;i<=n;i++){
            memset(v,0,sizeof v);
            if(dfs(i))ans++;
        }
        cout<<n-ans<<endl;
    }
    return 0;
}

hdu 1068：最大沒有聯系的男女個數

hdu 1068

本質：最大獨立集 -> 二分圖最大比對

注意：本題并沒有指明男女生的分類，那麼兩個集合采用的均為所有人的編号，最後結果就是：總人數-最大比對數/2

#include <bits/stdc++.h>
using namespace std;

int n,ans,p[1000],v[1000],mp[1000][1000];

bool dfs(int i){
    for(int j=0;j<n;j++){
        if(mp[i][j]&&!v[j]){
            v[j]=1;
            if(p[j]==-1||dfs(p[j])){
                p[j]=i;return 1;
            }
        }
    }
    return 0;
}

int main(){
    while(scanf("%d",&n)==1){
        ans=0;
        memset(mp,0, sizeof mp);
        for(int i=0;i<n;i++){
            int k;scanf("%d: (%d)",&i,&k);
            while(k--){
                int a;scanf("%d",&a);
                mp[i][a]=1;
            }
        }
        memset(p,-1,sizeof p);
        for(int i=0;i<n;i++){
            memset(v,0,sizeof v);
            if(dfs(i))ans++;
        }
        printf("%d\n",n-ans/2);
    }
    return 0;
}

hdu 1281 ：騎士最大放置數

hdu 1281

題意：在一個棋盤裡，給出能放置棋子的格子數以及具體坐标，求騎士最多能多少個（任何棋子之間不能傷害對方）；求重要點的數量，重要點：即不放該個格子，騎士最大值就變了

國際象棋中的騎士是橫豎走的，兩個棋子的坐标x互不相同，y坐标互不相同；即可以轉化為集合X 和 集合Y 的最大比對數

求重要點：依次将某個點删去（兩點間的連線由1->0），在進行二分比對操作，看比對書是否改變

#include <bits/stdc++.h>
using namespace std;

int n,m,k,ans,p[110],v[110],mp[110][110];

bool dfs(int i){
    for(int j=1;j<=m;j++){
        if(mp[i][j]&&!v[j]){
            v[j]=1;
            if(!p[j] || dfs(p[j])){
                p[j]=i;return 1;
            }
        }
    }
    return 0;
}

int match(){
    int res=0;
    memset(p,0,sizeof p);
    for(int i=1;i<=n;i++){
        memset(v,0,sizeof v);
        if(dfs(i))res++;
    }
    return res;
}

int main(){
    int t=1;
    while(scanf("%d%d%d",&n,&m,&k)==3){
        memset(mp,0,sizeof mp);
        while(k--){
            int x,y;scanf("%d%d",&x,&y);
            mp[x][y]=1;
        }
        ans=match();
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(mp[i][j]){
                    mp[i][j]=0;
                    if(match()<ans)cnt++;
                    mp[i][j]=1;
                }
            }
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",t++,cnt,ans);
    }
    return 0;
}
題 學習随更
上一篇: 部分求和問題-dfs/窮竭搜尋
下一篇: 遞推系列（未學dp前的分析系列）水題集wa了多次的?水題集?

繼續閱讀