二分图匹配

hhhhyq · 2018-10-15 19:12:28 · 题解

今天自学了二分图匹配，想找个题做，于是在洛谷上找题“最大匹配”、“难度排序”，就找到了“P2071 座位安排 ”这道神仙题

还好还好做出来了

然后心虚看了看题解 看题解学习一下，发现我的做法竟然和题解不一样（emmm就两篇还有一个是网络流 tttql）

然后就这个题面都提示了是二分图匹配

于是朴素的二分图匹配代码：

 bool dfs(int now){
    for (int a=1;a<=n2;a++)
        if (!use[a] && match[now][a]){
            use[a]=true;
            if (!result[a] || dfs(result[a])){
                result[a]=now;
                return true;
            }
        }
    return false;
}

int xiongyali(){
    int ans=0;
    for (int a=1;a<=n1;a++){
        memset(use,false,sizeof(use));
        if (dfs(a)) ans++;
    }

    return ans;
}

如果是匈牙利算法都不会的同学先自学一下吧，挺简单的hhh（毕竟我都能学会），板子在 P3386 【模板】二分图匹配

观察到：每排椅子都可以对应两个人，而我们用result数组来表示右图中的一个点所对相应的左图中的一个点，所以我们把result数组开二维就好了吧hhhh突然感觉好简单......

还有用邻接矩阵存理论复杂度O(n^3),果断邻接链表 理论复杂度O(nm) （这都是理论最大值，实际不会这么大）

代码（邻接矩阵 60）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;

typedef long long ll;
const int maxn=4004;

int n,m,e;
int result[maxn][2],use[maxn];
int g[maxn][maxn];

bool dfs(int now){
    for(int i=1;i<=n;i++){
        if(!use[i]&&g[now][i]){
            use[i]=true;
            if(!result[i][0]||dfs(result[i][0])){
                result[i][0]=now;
                return true;
            }
            if(!result[i][1]||dfs(result[i][1])){
                result[i][1]=now;
                return true;
            }
        }
    }
    return false;
}

int xiongyali(){
    int ans=0;
    for(int i=1;i<=n*2;i++){
        memset(use,0,sizeof(use));
        if(dfs(i))ans++;
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*2;i++){
        int a,b;scanf("%d%d",&a,&b);
        g[i][a]=1;g[i][b]=1;
    }
    printf("%d\n",xiongyali());
}

代码（邻接链表 100分）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;

typedef long long ll;
const int maxn=4004;
struct edge{
    int v,nxt;
}e[maxn*16];
int n,m,cnt=0;
int result[maxn][2],use[maxn];
int head[maxn];

void add_edge(int u,int v){
    ++cnt;
    e[cnt]=(edge){v,head[u]};
    head[u]=cnt;
}

bool dfs(int now){

    for(int j=head[now];j;j=e[j].nxt){
        int v=e[j].v;
        if(!use[v]){
        use[v]++;
        if(!result[v][0]||dfs(result[v][0])){
            result[v][0]=now;
            return true;
        }
        if(!result[v][1]||dfs(result[v][1])){
            result[v][1]=now;
            return true;
        }
    }
    }

    return false;
}

int xiongyali(){
    int ans=0;
    for(int i=1;i<=n*2;i++){
        memset(use,0,sizeof(use));
        if(dfs(i))ans++;
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*2;i++){
        int a,b;scanf("%d%d",&a,&b);
        add_edge(i,a);
        add_edge(i,b);
    }
    printf("%d\n",xiongyali());
}

www求通过