Shoot the Bullet(有源汇带上下界最大流)

有源汇带上下界最大流
在原图基础上连一条汇点到源点流量为inf的边,将有源汇网络流转化为无源汇网络流用相同方法判断是否满流，如果满流再跑一边源点到汇点的最大流就是答案
例题：Shoot the Bullet 东方文花帖
题目传送门

#include <bits/stdc++.h>
using namespace std;
/*    freopen("k.in", "r", stdin);
    freopen("k.out", "w", stdout); */
// clock_t c1 = clock();
// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ls ((x) << 1)
#define rs ((x) << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef vector<int, int> VII;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 2e3 + 7;
const ll MAXM = 1e5 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1.0);
int cnt = -1, head[MAXM], dis[MAXN], cur[MAXM];
int n, m;
struct Edge
{
    int to, v, net;
    Edge(int _to = 0, int _v = 0, int _net = 0) { to = _to, v = _v, net = _net; }
} e[MAXM << 1]; ///共有n*2条边
void add_edge(int from, int to, int v)
{ ///链式前向星
    e[++cnt] = Edge(to, v, head[from]);
    head[from] = cnt;
    e[++cnt] = Edge(from, 0, head[to]);
    head[to] = cnt;
}
int bfs(int st, int ed)
{ ///建立层次图
    queue<int> que;
    memset(dis, -1, sizeof(dis));
    dis[st] = 0;
    que.push(st);
    while (!que.empty())
    {
        int x = que.front();
        que.pop();
        for (int i = head[x]; ~i; i = e[i].net)
        {
            int now = e[i].to;
            if (dis[now] == -1 && e[i].v)
            {
                que.push(now);
                dis[now] = dis[x] + 1;
            }
        }
    }
    return dis[ed] != -1;
}
int dfs(int x, int t, int maxflow)
{
    if (x == t)
        return maxflow;
    int ans = 0;
    for (int i = cur[x]; ~i; i = e[i].net)
    { ///当前弧优化
        int now = e[i].to;
        if (dis[now] != dis[x] + 1 || e[i].v == 0 || ans >= maxflow)
            continue;
        cur[x] = i;
        int f = dfs(now, t, min(e[i].v, maxflow - ans));
        e[i].v -= f;
        e[i ^ 1].v += f; ///反向边加流量
        ans += f;
    }
    if (!ans)
        dis[x] = -1; ///炸点优化
    return ans;
}
int Dinic(int st, int ed)
{
    int ans = 0;
    while (bfs(st, ed))
    {
        memcpy(cur, head, sizeof(head));
        int k;
        while ((k = dfs(st, ed, inf)))
            ans += k;
    }
    return ans;
}
int totflow[MAXN];
int ans[MAXM];
int lowf[MAXN];
void init()
{
    cnt = -1;
    memset(head, -1, sizeof(head));
    memset(totflow, 0, sizeof(totflow));
    memset(lowf, 0, sizeof(lowf));
}
int day[MAXN], girl[MAXN];
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        init();
        int st = 0, ed = n + m + 1;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d", &girl[i]);
            totflow[n + i] -= girl[i];
            totflow[ed] += girl[i];
        }
        int tot = 0;
        for (int i = 1; i <= n; i++)
        {
            int c, d;
            scanf("%d%d", &c, &day[i]);
            for (int j = 1; j <= c; j++)
            {
                int t, l, r;
                scanf("%d%d%d", &t, &l, &r);
                ++t;
                lowf[++tot] = l;
                totflow[i] -= l;
                totflow[n + t] += l;
                add_edge(i, n + t, r - l);
            }
        }
        for (int i = 1; i <= m; i++)
            add_edge(n + i, ed, inf);
        for (int i = 1; i <= n; i++)
            add_edge(st, i, day[i]);
        add_edge(ed, st, inf);
        int ss = n + m + 2, tt = n + m + 3;
        int sumflow = 0;

        for (int i = 0; i <= n + m + 1; i++)
        {
            if (totflow[i] < 0)
                add_edge(i, tt, -totflow[i]);
            else if (totflow[i] > 0)
            {
                sumflow += totflow[i];
                add_edge(ss, i, totflow[i]);
            }
        }

        if (Dinic(ss, tt) == sumflow)
        {
            printf("%d\n", Dinic(st, ed));
            for (int i = 1; i <= tot; i++)
                printf("%d\n", e[((i - 1) << 1) | 1].v + lowf[i]);
        }
        else
            printf("-1\n");
        printf("\n");
    }
    return 0;
}

Shoot the Bullet(有源汇带上下界最大流)

原文：https://www.cnblogs.com/graytido/p/12012883.html