最大流

题目1：Dining POJ - 3281

分析：

模板（当前弧优化+剪枝）

代码：

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
using namespace std;
struct edge{
     int v, val, nex;
     edge(int a = 0, int b = 0, int c = 0) : v(a), val(b), nex(c){}
}e[100010];
int head[17000], tot, nowcur[maxn];
int depth[17100];
int n, f, d, s, t;

void init()
{
    tot = 0, mem(head, -1);
}

void addedge(int u, int v, int val){
    e[tot] = edge(v, val, head[u]);
    head[u] = tot++;
    e[tot] = edge(u, 0, head[v]);
    head[v] = tot++;
}

bool bfs()
{
     queue<int> q;
     memset(depth, 0, sizeof(depth));
     depth[s] = 1, q.push(s);
     nowcur[s] = head[s];
     while(!q.empty())
     {
        int u = q.front(); q.pop();
        for(int i = head[u]; ~i; i = e[i].nex)
        {
            int v = e[i].v;
            if(!depth[v] && e[i].val > 0)
                depth[v] = depth[u] + 1, q.push(v), nowcur[v] = head[v];
        }
     }
     return depth[t] > 0;
}

int dfs(int u,int flow)
{
    if(u == t)return flow;
    int res = 0;
    for(int i = nowcur[u]; ~i && flow; i = e[i].nex)
    {
        int v = e[i].v;
        nowcur[v] = head[v];
        if(depth[v] == depth[u] + 1 && e[i].val > 0)
        {
            int tmp = dfs(v, min(flow, e[i].val));
            if(!tmp) depth[v] = -1;
            res += tmp, flow -= tmp;
            e[i].val -= tmp, e[i ^ 1].val += tmp;
        }
    }
    return res;
}

int maxflow(){
    int res = 0;
    while(bfs())
        res += dfs(s, inf);
    return res;
}

int main()
{
    while(cin >> n >> f >> d)
    {
        init();
        s = 0, t= f + n * 2 + d + 1;
        for(int i=1;i<=n;i++)
        {
            int n1, n2; cin >> n1 >> n2;
            for(int k = 1; k <= n1; k++)
            {
                int x; cin >> x;
                addedge(x, f + i, 1);
            }
            addedge(f + i, f + i + n, 1);
            for(int k = 1; k <= n2; k++)
            {
                int x; cin >> x;
                addedge(f + n + i, f + n * 2 + x, 1);
            }
        }
        for(int i = 1; i <= f; i++)
            addedge(s, i, 1);
        for(int i = 1; i <= d; i++)
            addedge(f + n * 2 + i, t, 1);
        printf("%d\n",maxflow());
    }
    return 0;
}

本文地址：https://blog.csdn.net/weixin_43987810/article/details/107390040