POJ 3281 Dining （网络流/最大流建图拆点 EK+dinic解法）

Dining

题目大意：
奶牛要吃食物和饮料，给n种食物，m种饮料，问最多能喂多少奶牛（每种食物和饮料只能使用一次）

解题思路：
最大流问题，让每个奶牛都和一种食物和饮料匹配，求最大匹配值，这个题的难点在于建图拆点，
要注意把奶牛拆成两个点，中间建一个容量为1的点，假设不建这条边的话，一个奶牛可能会对应多种食物和饮料，和题意要求不同。

Ek：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 10005;
struct poi {
	int u, v, cap, next; 
}edges[maxn];

int head[maxn], cnt;
int n, f, d;
int dis[maxn];
int S, T;
int p[maxn];

void init() {
	memset(head, -1, sizeof(head));
	memset(edges, 0, sizeof(edges));
	cnt = 0;
	S = 2 * n + f + d + 1;
	T = S + 1;
}

void adde(int u, int v, int w) {
	edges[cnt].u = u, edges[cnt].v = v, edges[cnt].cap = w;
	edges[cnt].next = head[u], head[u] = cnt++;
	
	edges[cnt].u = v, edges[cnt].v = u, edges[cnt].cap = 0;
	edges[cnt].next = head[v], head[v] = cnt++;
}

int EK() {
	int flow = 0;
	while (1) {
		memset(dis, 0, sizeof(dis));
		queue<int> Q;
		Q.push(S);
		dis[S] = inf;
		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			for (int i = head[u]; ~i; i = edges[i].next) {
				int v = edges[i].v, cap = edges[i].cap;
				if (!dis[v] && cap > 0) {
					p[v] = i;
					dis[v] = min(dis[u], cap);
					Q.push(v);
				}
			}
			if (dis[T]) break;
		}
		if (!dis[T]) break;
		for (int u = T; u != S; u = edges[p[u]].u) {
			edges[p[u]].cap -= dis[T];
			edges[p[u] ^ 1].cap += dis[T];
		}
		flow += dis[T];
	}
	return flow;
}

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    while(cin>>n>>f>>d){
    	init();
    	for(int i=2*n+1;i<=2*n+f;i++) adde(S,i,1);       // 源点和食物建边
    	for(int i=1;i<=n;i++) adde(i,i+n,1);               //奶牛拆点
    	for(int i=2*n+f+1;i<=2*n+f+d;i++) adde(i,T,1);        //饮料和汇点建边
    	
    	for(int i=1;i<=n;i++){
    		int fi,di;
    		cin>>fi>>di;
    		for(int j=1;j<=fi;j++){
    			int x;
    			cin>>x;
    			adde(2*n+x,i,1);                  //奶牛和食物
			}
			for(int j=1;j<=di;j++){
				int x;
				cin>>x;
				adde(i+n,2*n+f+x,1);          //奶牛分身和饮料建边
			}
		}
		cout<<EK()<<endl;
	}
	
    return 0;
}

dinic：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 10005;
struct poi {
	int u, v, cap, next; 
}edges[maxn];

int head[maxn], cnt;
int n, f, d;
int dis[maxn];
int S, T;
int cur[maxn];

void init() {
	memset(head, -1, sizeof(head));
	memset(edges, 0, sizeof(edges));
	cnt = 0;
	S = 2 * n + f + d + 1;
	T = S + 1;
}

void adde(int u, int v, int w) {
	edges[cnt].u = u, edges[cnt].v = v, edges[cnt].cap = w;
	edges[cnt].next = head[u], head[u] = cnt++;
	
	edges[cnt].u = v, edges[cnt].v = u, edges[cnt].cap = 0;
	edges[cnt].next = head[v], head[v] = cnt++;
}

//bfs 分层次
bool bfs() {
	memset(dis, 0, sizeof(dis));
	dis[S] = 1;
	queue<int> Q;
	Q.push(S);
	int flow = 0;
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop();
		for (int i = head[u]; ~i; i = edges[i].next) {
			int v = edges[i].v, cap = edges[i].cap;
			if (cap > 0 && !dis[v]) {
				dis[v] = dis[u] + 1;
				Q.push(v);
			}
		}
	}
	return dis[T] != 0;
}

//dfs 找增广路
int dfs(int u, int mw) {
	if (u == T || mw == 0) return mw;
	int flow = 0;
	for (int &i = cur[u]; ~i; i = edges[i].next) {//从上次考虑的弧开始
		int v = edges[i].v, cap = edges[i].cap;
		if (cap > 0 && dis[v] == dis[u] + 1) {
			int cw = dfs(v, min(mw, cap));
			flow += cw;
			edges[i].cap -= cw;
			edges[i ^ 1].cap += cw;
			mw -= cw;
			if (mw == 0) break;
		}
	}
	return flow;
}

//主进程
int dinic() {
	int res = 0;
	while (bfs()) {
		memcpy(cur, head, sizeof(head));
		res += dfs(S, inf);
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    while(cin>>n>>f>>d){
    	init();
    	for(int i=2*n+1;i<=2*n+f;i++) adde(S,i,1);       // 源点和食物建边
    	for(int i=1;i<=n;i++) adde(i,i+n,1);               //奶牛拆点
    	for(int i=2*n+f+1;i<=2*n+f+d;i++) adde(i,T,1);        //饮料和汇点建边
    	
    	for(int i=1;i<=n;i++){
    		int fi,di;
    		cin>>fi>>di;
    		for(int j=1;j<=fi;j++){
    			int x;
    			cin>>x;
    			adde(2*n+x,i,1);                  //奶牛和食物
			}
			for(int j=1;j<=di;j++){
				int x;
				cin>>x;
				adde(i+n,2*n+f+x,1);          //奶牛分身和饮料建边
			}
		}
		cout<<dinic()<<endl;
	}
	
    return 0;
}

本文地址：https://blog.csdn.net/weixin_43872264/article/details/107953147