自动搬运

查看原文

来自洛谷，原作者为

	hhhhyq **

搬运于2025-08-24 21:33:39，当前版本为作者最后更新于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求通过