POJ 3281 Dining - 最大流 (Dinic) 模型構建

問題描述

N 頭牛、F 種食物、D 種飲料。每頭牛有喜歡的食物集合和飲料集合。每種食物/飲料只能供一頭牛。求最多有多少頭牛同時獲得喜歡的食物和飲料。

網絡流建模

關鍵：每頭牛拆成兩個節點 (in, out)，中間連容量 1 的邊，限制每頭牛最多用一次食物和一次飲料。

• 源點 S → 每種食物 (容量 1)
• 食物 → 牛_in (若牛喜歡，容量 1)
• 牛_in → 牛_out (容量 1)
• 牛_out → 飲料 (若牛喜歡，容量 1)
• 飲料 → 匯點 T (容量 1)

最大流即為答案。

Dinic 實現要點

• 鄰接表存儲，含反向邊（用於增廣）。
• BFS 分層 + DFS 阻塞流。
• 節點數：S(0), 食物 1..F, 牛_in F+1..F+N, 牛_out F+N+1..F+2N, 飲料 F+2N+1..F+2N+D, T 最後。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205; // F+N+N+D+2 ≤ 100+100+100+100+2
const int MAXM = 20000;
const int INF = 0x3f3f3f3f;

struct Edge { int to, cap, nxt; } e[MAXM];
int head[MAXN], ecnt, level[MAXN], cur[MAXN];
int S, T, N, F, D;

void addEdge(int u,int v,int c){ e[ecnt]={v,c,head[u]}; head[u]=ecnt++; e[ecnt]={u,0,head[v]}; head[v]=ecnt++; }

bool bfs() {
    memset(level, -1, sizeof(level));
    queue q; q.push(S); level[S]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].cap>0 && level[v]==-1){
                level[v]=level[u]+1; q.push(v);
            }
        }
    }
    return level[T]!=-1;
}

int dfs(int u, int f) {
    if(u==T || f==0) return f;
    int flow=0;
    for(int &i=cur[u]; ~i; i=e[i].nxt){
        int v=e[i].to;
        if(e[i].cap>0 && level[v]==level[u]+1){
            int ret=dfs(v, min(f, e[i].cap));
            if(ret){
                e[i].cap-=ret; e[i^1].cap+=ret;
                flow+=ret; f-=ret;
                if(f==0) break;
            }
        }
    }
    if(!flow) level[u]=-1;
    return flow;
}

int dinic() {
    int ans=0;
    while(bfs()){
        memcpy(cur, head, sizeof(head));
        ans+=dfs(S, INF);
    }
    return ans;
}

int main() {
    while(scanf("%d%d%d",&N,&F,&D)==3){
        memset(head,-1,sizeof(head)); ecnt=0;
        S=0; T=F+2*N+D+1;
        // 源點->食物
        for(int i=1;i<=F;i++) addEdge(S,i,1);
        // 飲料->匯點
        for(int i=1;i<=D;i++) addEdge(F+2*N+i,T,1);
        // 牛拆點
        for(int i=1;i<=N;i++) addEdge(F+i, F+N+i, 1);
        // 讀取偏好
        for(int i=1;i<=N;i++){
            int nf, nd; scanf("%d%d",&nf,&nd);
            for(int j=0;j

複雜度
Dinic O(E√V) 此處極快。節點 ≤ 402，邊 ≤ 20000，完全滿足。