题目链接: https://vjudge.net/problem/POJ-3281
题目: 有不同种类的食物和饮料, 每种只有 1 个库存, 有 N 头牛, 每头牛喜欢某些食物和某些饮料, 但是一头牛
只能吃一种食物和喝一种饮料, 问怎么分配食物和饮料才能让最多数量的牛饱餐.
思路: 容易想到 食物 -> 牛 -> 饮料的流, 当然一个牛可以被多个饮料流到, 需要把牛拆成入点和出点, 入点和出点流量为 1, 这样可以保证牛只吃或者喝某种食物和饮料, 别的都流是套路, 除了牛的分点之间流量为 1, 别的连接设置成 1 或者 INF 都一样, 因为有牛的分点流量的限制.
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- using namespace std;
- const int N = 410,INF = (int)1e9;
- int n,F,D,tot,S,T;
- int head[N],lev[N];
- queue<int> que;
- struct node{
- int to,nxt,flow;
- }e[N*N];
- inline void add(int u,int v,int flow){
- e[tot].to = v;
- e[tot].flow = flow;
- e[tot].nxt = head[u];
- head[u] = tot++;
- e[tot].to = u;
- e[tot].flow = 0;
- e[tot].nxt = head[v];
- head[v] = tot++;
- }
- void build_map(int s,int t){
- for(int i = s; i <= t; ++i) head[i] = -1; tot = 0;
- // 读入信息 0 是源点 1~F 食物 F+1~F+2*n 牛 F+2*n+1~F+2*n+D 饮料 F+2*n+D+1 是汇点
- int kind_f,kind_d,x;
- for(int i = 1; i <= n; ++i){
- scanf("%d%d",&kind_f,&kind_d);
- for(int j = 1; j <= kind_f; ++j){
- scanf("%d",&x);
- add(x,F+i,1);// add(F+i,x,0);
- }
- for(int j = 1; j <= kind_d; ++j){
- scanf("%d",&x);
- add(F+n+i,F+2*n+x,1);// add(F+2*n+x,F+n+i,0);
- }
- }
- for(int i = 1; i <= F; ++i){
- add(s,i,1);// add(i,s,0);
- }
- for(int i = 1; i <= D; ++i){
- add(F+2*n+i,t,1);// add(t,F+2*n+i,0);
- }
- for(int i = 1; i <= n; ++i){
- add(F+i,F+n+i,1);// add(F+n+i,F+i,0);
- }
- }
- void show(int s,int t){
- for(int i = s; i <= t; ++i){
- cout << "当前点为" << i << " ";
- cout << "能去到";
- for(int o = head[i]; ~o; o = e[o].nxt){
- printf("%d 流量为 %d",e[o].to,e[o].flow);
- }cout << endl;
- }
- }
- bool bfs(int s,int t){
- while(!que.empty()) que.pop();
- for(int i = s; i <= t; ++i) lev[i] = 0;
- lev[s] = 1;
- que.push(s);
- while(!que.empty()){
- int u = que.front(); que.pop();
- for(int o = head[u]; ~o; o = e[o].nxt){
- int v = e[o].to;
- if(!lev[v] && e[o].flow ){
- lev[v] = lev[u] + 1;
- if(v == t) return true;
- que.push(v);
- }
- }
- }
- return false;
- }
- int dfs(int now,int flow,int t){
- if(now == t) return flow;
- int to,sum = 0,tmp;
- for(int o = head[now]; ~o; o = e[o].nxt){
- to = e[o].to;
- if((lev[to] == lev[now] + 1) && e[o].flow && (tmp = dfs(to,min(flow-sum,e[o].flow),t))){
- e[o].flow -= tmp;
- e[o^1].flow += tmp;
- if((sum += tmp) == flow) return sum;
- }
- }
- return sum;
- }
- int mf(int s,int t){
- int _mf = 0;
- while(bfs(s,t)){
- _mf += dfs(s,INF,t);
- }
- return _mf;
- }
- int main(){
- scanf("%d%d%d",&n,&F,&D);
- S = 0; T = F+2*n+D+1;
- // 建图
- build_map(S,T);
- // show(S,T); // 图的显示
- int ans = mf(S,T);
- printf("%d\n",ans);
- return 0;
- }
来源: https://www.cnblogs.com/SSummerZzz/p/12241735.html