首页

某谷某模拟赛碰到二分图的签到题不会写丢人 QAQ

回来补个板子 QwQ

# 模板

P3386 【模板】二分图最大匹配

思路：

左边点n1n1 个， 右边点n2n2 个， e[i][j]e[i][j] 表示左边 ii 号与右边 jj 号节点连接。

依次给左边每个点找对象，其过程中：若遇到某个右边点已经有对象，让这个右边点的对象（也就是之前匹配的左边点）再重新找个对象试试 emm

code:

bool dfs(int np)
{
	rep(i, 1, n2) // 匹配右边第 i 号
	{
		if (!vis[i] && e[np][i])
		{
			vis[i] = 1;
			if (!match[i] || dfs(match[i])) // 若该点已经被匹配，让其匹配的左边点再找个新的对象 QwQ
			{
				match[i] = np;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d", &n1, &n2, &m);
	int u, v;
	rep(i, 1, m)
	{
		scanf("%d%d", &u, &v);
		e[u][v] = 1;
	}
	rep(i, 1, n1) // 匹配左边第 i 号
	{
		memset(vis, 0, sizeof(vis));
		if (dfs(i))
			ans++;
	}
    printf("%d\n", ans);
    return 0;
}

# 杂题

话说在这搬运题目好像没版权呀，，算了反正也没人看 qwq

题意：

某 dl 出题人想要每个题的 题号 与题 目名称的首字母 对应，每个题目有多个备选名称，问是否存在一种符合的方案。

例如：

//合法
bqqqww
aqwq ccc
//8行
aabb bbaa
ccc

思路：

二分图匹配裸题，菜死了 QAQ

输入格式：

nn 个题，每个题 mm 个备用名，字符串给出。

code:

#include <cstdio>
#include <iostream>
#include <cstring>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int MAXN = 33;
int n, m, ans, match[MAXN];
char str[233];
bool e[MAXN][MAXN], vis[MAXN];
bool dfs(int np)
{
	rep (i, 1, n)
	{
		if (!vis[i] && e[np][i])
		{
			vis[i] = 1;
			if (!match[i] || dfs(match[i]))
			{
				match[i] = np;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	scanf("%d", &n);
	rep (i, 1, n)
	{
		scanf("%d ", &m);
		rep (j, 1, m)
		{
			scanf("%s ", str);
			e[i][str[0] - 'a' + 1] = 1;
		}
	}
	rep (i, 1, n)
	{
		memset(vis, 0, sizeof(vis));
		if (dfs(i))
			ans++;
	}
	if (ans == n)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

好耶，又水了一篇文章。

更新于