众所周知图论中网络流问题最重要的就是建图了,如果可以建图成功了那么题目也就自然而然的做出来了,今天介绍的是拆点法建图,首先来看例题洛谷P1402
<mark>题目描述</mark>
XX酒店的老板想成为酒店之王,本着这种希望,第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等,也有自己所爱的菜,但是该酒店只有p间房间,一天只有固定的q道不同的菜。

有一天来了n个客人,每个客人说出了自己喜欢哪些房间,喜欢哪道菜。但是很不幸,可能做不到让所有顾客满意(满意的条件是住进喜欢的房间,吃到喜欢的菜)。

这里要怎么分配,能使最多顾客满意呢?

<mark>输入格式</mark>
第一行给出三个正整数表示n,p,q(<=100)。

之后n行,每行p个数包含0或1,第i个数表示喜不喜欢第i个房间(1表示喜欢,0表示不喜欢)。

之后n行,每行q个数,表示喜不喜欢第i道菜。

<mark>输出格式</mark>
最大的顾客满意数。

输入输出样例
<mark>输入</mark>
2 2 2
1 0
1 0
1 1
1 1
<mark>输出</mark>
1

题目大意就是说有n个A类点p个B类点q个C类点一个A类点匹配一个B类点一个C类点视为匹配成功,看起来有点想匈牙利的题,当然也可以用最大流来写,’
那么我们也都不难想出这样一个建图方法

那么你们有没有考虑这样一种情况呢.?

正常情况下只能匹配一个顾客,但是你会发现跑一边最大流的话就会是2,那么如何处理这种情况呢?,划重点了,拆点法建图也就是这样

这样是不是就完全解决了
接下来上代码

/* *        ┏┓ ┏┓+ + *       ┏┛┻━━━━━━━┛┻┓ + + *       ┃       ┃ *       ┃   ━   ┃ ++ + + + *       █████━█████ ┃+ *       ┃       ┃ + *       ┃   ┻   ┃ *       ┃       ┃ + + *       ┗━━┓    ┏━┛ * ┃   ┃ *         ┃   ┃ + + + + *         ┃   ┃ Code is far away from bug with the animal protecting *         ┃   ┃ +      神兽保佑,代码无bug *         ┃   ┃ *         ┃   ┃  + *         ┃    ┗━━━┓ + + *         ┃      ┣┓ *         ┃      ┏┛ *         ┗┓┓┏━━━┳┓┏┛ + + + + *          ┃┫┫  ┃┫┫ *          ┗┻┛  ┗┻┛+ + + + */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
#include<vector>
#include<cmath>
#include<functional>
#include<stack>

using namespace std;

const int maxn = 255;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge
{
	int to, next, w;
}edg[MAXN];

int head[MAXN], dep[MAXN], n, p, q, cnt = 0;

void init()
{
	memset(head, -1, sizeof(head));
	cnt = 0;
}

void Add_edge(int u, int v, int w)
{
	edg[cnt].to = v;
	edg[cnt].w = w;
	edg[cnt].next = head[u];
	head[u] = cnt++;
}

bool Bfs(int s, int t)
{
	memset(dep, 0, sizeof(dep));
	queue<int> q;
	while(!q.empty()) q.pop();
	dep[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int p = q.front();
		q.pop();
		for(int i = head[p]; i != -1; i = edg[i].next)
		{
			int w = edg[i].w; int v = edg[i].to;
			if(w && !dep[v])
			{
				dep[v] = dep[p] + 1;
				q.push(v);
				if(v == t)
					return true;
			}
		}
	}
	if(dep[t])
        return true;
    else
	return false;
}

int DFS(int s, int mw, int t)
{
	if(s == t)
		return mw;
	int res = 0;
	for(int i = head[s]; i != -1 && res < mw; i = edg[i].next)
	{
		int v = edg[i].to;
		if(edg[i].w && dep[v] == dep[s] + 1)
		{
			int k = DFS(v, min(mw - res, edg[i].w), t);
			if(!k) dep[v] = 0;
			edg[i].w -= k;
			edg[i^1].w += k;
			res += k;
		}
	}
	return res;
}

int main()
{
	scanf("%d %d %d", &n, &p, &q);
	init();
	int s = 0, t = n + p + q + n + 1;
	for(int i = 1; i <= p; ++i)// House
	{
		Add_edge(0, i, 1);
		Add_edge(i, 0, 0);
	}
	for(int i = 1; i <= p; ++i)// Menu
	{
		Add_edge(i + p, t, 1);
		Add_edge(t, i + p, 0);
	}
	for(int i = 1; i <= n; ++i)// Double people
	{
		Add_edge(i + p + q, i + p + q + n, 1);
		Add_edge(i + p + q + n, i + p + q, 0);
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= p; ++j)
		{
			int x;
			scanf("%d", &x);
			if(x == 1)
			{
				Add_edge(j, i + p + q, 1);
				Add_edge(i + p + q, j, 0);
			}
		}
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= p; ++j)
		{
			int x;
			scanf("%d", &x);
			if(x == 1)
			{
				Add_edge(i + n + p + q, p + j, 1);
				Add_edge(p + j, i + n + p +	q, 0);
			}
		}
	}
	int tot = 0;
	while(Bfs(s, t))
	{
		while(int d = DFS(s, INF, t))
			tot += d;
	}
	printf("%d\n", tot);
}