USACO 2007 Open Gold/acwing2240：餐饮（拆点+最大流）‘三分图匹配’

╰半橙微兮° 2022-12-27 14:12 89阅读 0赞

原题链接：[acwing2240：餐饮][acwing2240]

### 题目大意 ###

有n头牛，f种食物d种饮料，每头牛都只吃喜欢的食物和饮料，现在有f种食物和d种饮料各一个，要给每头牛喂吃的和饮料，要求有吃有喝的牛数量最大是多少。

### 思路 ###

看到给牛匹配食物和饮料，就想到了二分图匹配问题，但此处要同时匹配食物和饮料，所以就变成了三个部分，相当于三分图匹配问题。  
![eg][]  
如上图，我们可以建一个源点S和汇点T，给S到所有事物都建一条容量为1的边，所有点饮料到T都建一条容量为1的边，给食物到匹配的牛和牛到匹配的饮料都建一条容量为1的边。容量为1表示这条边只能选一遍，就相当于每个食物和饮料都只能选一边遍。按照二分图的匹配问题来看，这道题就说这么建图的，但是我们现在要验证一下对于该图中的每个可行流是不是原问题的一种解。

对于上图我们可以发现，对于1号食物和2号食物都搭配到了1号牛，也同时搭配到了1号饮料和2号饮料，这是该图的一种可行流，但不是原问题的一个解，我们应该给每头牛只搭配一套食物，所以我们对所有牛的点应该有一个限制，让他只流过1的流量，因此这里就需要拆点，将一个点拆成入点和出点两个点，并在入点和出点之间连一条容量为1的边，就实现了对点的限制，如下图。  
![eg][eg 1]  
如上图，该图的每一种可行流都是原问题的一组解，因此，我们在这个图上求出最大流就是原问题的最大解了。由此我们可以知道对边的限制用边的容量来实现，对点的限制用拆点来实现。

对于点编号的分配如下图（有n头牛，f 种食物，d种饮料）  
![编号][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]

### 代码模板 ###

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int N = 410,M = 4610,INF = 0x3f3f3f3f;
    
    int n,m,s,t,f,d,dis[N],cur[N];
    int e[M],w[M],ne[M],h[N],idx;
    
    void add(int a,int b,int c)	//建边时直接建两条边，正向边和反向边
    { 
    	e[idx] = b;
    	w[idx] = c;
    	ne[idx] = h[a];
    	h[a] = idx++;
    	e[idx] = a;
    	w[idx] = 0;
    	ne[idx] = h[b];
    	h[b] = idx++;
    }
    
    bool bfs()	//dinic模板
    { 
    	queue<int> q;
    	memset(dis,-1,sizeof dis);
    	q.push(s);
    	dis[s] = 0;
    	cur[s] = h[s];
    	while(q.size())
    	{ 
    		int u = q.front();
    		q.pop();
    		for(int i = h[u];~i;i = ne[i])
    		{ 	
    			int v = e[i];
    			if(dis[v] == -1 && w[i])
    			{ 
    				dis[v] = dis[u] + 1;
    				cur[v] = h[v];
    				if(v == t)
    					return 1;
    				q.push(v);
    			}
    		}
    	}
    	return 0;
    }
    
    int dfs(int u,int limit)
    { 
    	if(u == t)
    		return limit;
    	int flow = 0;
    	for(int i = cur[u];~i;i = ne[i])
    	{ 
    		cur[u] = i;
    		int v = e[i];
    		if(dis[v] == dis[u]+1 && w[i])
    		{ 
    			int minf = dfs(v,min(w[i],limit-flow));
    			w[i] -= minf;
    			w[i^1] += minf;
    			flow += minf;
    			if(flow == limit)
    				return flow;
    		}
    	}
    	return flow;
    }
    
    int dinic()
    { 
    	int ans = 0;
    	while(bfs())
    		ans += dfs(s,INF);
    	return ans;
    }
    
    int main()
    { 
    	cin >> n >> f >> d;
    	memset(h,-1,sizeof h);
    	s = 0,t = f+d+n+n+1;	//建好源点和汇点
    	for(int i = 1;i <= f;i++)	//建所有源点到食物的边
    		add(s,i,1);
    	for(int i = 1;i <= n;i++)	//建所有牛的入点到出点的边（拆点）
    		add(f+i,f+n+i,1);
    	for(int i = 1;i <= d;i++)	//建所有饮料到汇点的边
    		add(f+n+n+i,t,1);
    	for(int i = 1;i <= n;i++)
    	{ 
    		int a,b,tmp;
    		cin >> a >> b;
    		while(a--)
    		{ 
    			cin >> tmp;
    			add(tmp,f+i,1);		//建匹配的食物到牛的边
    		}
    		while(b--)
    		{ 	
    			cin >> tmp;
    			add(f+n+i,f+n+n+tmp,1);	//建匹配的牛到饮料的边
    		}
    	}
    	cout << dinic() << endl;	//求得最大流即可
    
    	return 0;
    }

[acwing2240]: https://www.acwing.com/problem/content/2242/
[eg]: /images/20221120/6d4ae7c228ac49b8a311837aff4a9c93.png
[eg 1]: https://img-blog.csdnimg.cn/20201212171434682.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201213224759391.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx,size_16,color_FFFFFF,t_70