1. 洛谷 P1251 餐巾计划问题

这题三年前交过居然（哇不知不觉打了三年了

当时肯定不会网络流这种东西的 好像是练习写暴力在（毕竟noip混一等

然后今天重新做了以下

/*
这题建图有点难啊
 一开始想的简单的S到每个点流无穷花p 每个点到T流ri花0
 然后i到后面可以用的点流无穷花x
 但是有个问题就是
 这里的流量需要复用
 就是i流出去的既要流向T 贡献流量 又要留到后面的点 毛巾复用
 这显然流量不够用
 我们要做的就是 引入一些 免费的流量
 这些流量不会减少花费 却能为满流做贡献

 对于i 拆成2个点 i1 i2
 起点到i1 流无穷花p  表示新买的毛巾
 i1到T 流ri花0 把i天能用的干净毛巾对满流的贡献算上
 起点到i2 流ri花0 表示i天之后脏毛巾 后面可以继续用
 然后和上面一样 i2向后面的点的j1连边
 还有就是  延期处理的毛巾
 i2 连向 (i+1)2 流无穷花0

 这样子 每个S到i2的流 就是我们引入的  免费的流
 要想每个i有足够的毛巾 限制在 i1 流向T的流是满的
 并且这些只能是新买的或者之前 重新洗过的
 不可能来自我们引进的免费流

 */
#include<bits/stdc++.h>

#define inf 1e15
#define pa pair<ll,ll>
#define mk make_pair
#define Fi first
#define Se second
#define maxn 8010
#define ll long long
using namespace std;
ll n, r[maxn], N, M, P, F, S;
ll preV[maxn], preE[maxn], H[maxn], dis[maxn];

struct edge {
    ll v, flow, t, rev;

    edge() {};

    edge(ll v, ll flow, ll t, ll rev) : v(v), flow(flow), t(t), rev(rev) {}
};

vector<edge> G[maxn];

void Add(ll from, ll to, ll flw, ll dis) {
    G[from].push_back(edge(to, flw, dis, G[to].size()));
    G[to].push_back(edge(from, 0, -dis, G[from].size() - 1));
}

void Dij(ll t) {
    priority_queue<pa, vector<pa >, greater<pa > > q;
    for (ll i = 0; i <= t; i++)dis[i] = inf;
    for (ll i = 0; i <= t; i++)preE[i] = preV[i] = -1;
    dis[1] = 0;
    q.push(pa(0, 1));
    while (!q.empty()) {
        pa now = q.top();
        q.pop();
        ll u = now.Se;
        if (dis[u] < now.Fi)continue;
        for (ll i = 0; i < G[u].size(); ++i) {
            edge &e = G[u][i];
            if (e.flow == 0)continue;
            ll v = e.v;
            if (dis[v] > dis[u] + e.t + H[u] - H[v]) {
                dis[v] = dis[u] + e.t + H[u] - H[v];
                preE[v] = i;
                preV[v] = u;
                q.push(pa(dis[v], v));
            }
        }
    }
}

ll Min_cost(ll s, ll t, ll totflow) {
    ll res = 0;
    memset(H, 0, sizeof(H));
    while (totflow) {
        Dij(t);
        if (dis[t] == dis[0])break;
        for (ll i = 1; i <= t; ++i)H[i] += dis[i];
        ll mi = totflow, pos = t;
        while (preV[pos] != -1) {
            mi = min(mi, G[preV[pos]][preE[pos]].flow);
            pos = preV[pos];
        }
        pos = t;
        res += mi * H[t];
        totflow -= mi;
        while (preV[pos] != -1) {
            G[preV[pos]][preE[pos]].flow -= mi;
            G[pos][G[preV[pos]][preE[pos]].rev].flow += mi;
            pos = preV[pos];
        }
    }
//    cout << 1e9 - totflow << endl;
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (ll i = 1; i <= n; i++)cin >> r[i];
    cin >> P >> M >> F >> N >> S;
    for (ll i = 1; i <= n; i++) {
        Add(1, 2 * i, 1e9, P);
        Add(1, 2 * i + 1, r[i], 0);
        Add(2 * i, 2 * n + 2, r[i], 0);
    }

    for (ll i = 1; i <= n; i++) {
        if (i + M <= n) {
            Add(2 * i + 1, 2 * (i + M), 1e9, F);
        }
        if (i + N <= n) {
            Add(2 * i + 1, 2 * (i + N), 1e9, S);
        }
        if (i < n) {
            Add(i * 2 + 1, (i + 1) * 2 + 1, 1e9, 0);
        }
    }
    cout << Min_cost(1, 2 * n + 2, 1e9) << endl;
    return 0;
}

2. P4016 负载平衡问题

这题比较简单吧 就强行网络流 应该有别的方法吧也

#include<bits/stdc++.h>

#define inf 1e15
#define pa pair<ll,ll>
#define mk make_pair
#define Fi first
#define Se second
#define maxn 8010
#define ll long long
using namespace std;
ll n, a[maxn];
ll preV[maxn], preE[maxn], H[maxn], dis[maxn];

struct edge {
    ll v, flow, t, rev;

    edge() {};

    edge(ll v, ll flow, ll t, ll rev) : v(v), flow(flow), t(t), rev(rev) {}
};

vector<edge> G[maxn];

void Add(ll from, ll to, ll flw, ll dis) {
    G[from].push_back(edge(to, flw, dis, G[to].size()));
    G[to].push_back(edge(from, 0, -dis, G[from].size() - 1));
}

void Dij(ll t) {
    priority_queue<pa, vector<pa >, greater<pa > > q;
    for (ll i = 0; i <= t; i++)dis[i] = inf;
    for (ll i = 0; i <= t; i++)preE[i] = preV[i] = -1;
    dis[1] = 0;
    q.push(pa(0, 1));
    while (!q.empty()) {
        pa now = q.top();
        q.pop();
        ll u = now.Se;
        if (dis[u] < now.Fi)continue;
        for (ll i = 0; i < G[u].size(); ++i) {
            edge &e = G[u][i];
            if (e.flow == 0)continue;
            ll v = e.v;
            if (dis[v] > dis[u] + e.t + H[u] - H[v]) {
                dis[v] = dis[u] + e.t + H[u] - H[v];
                preE[v] = i;
                preV[v] = u;
                q.push(pa(dis[v], v));
            }
        }
    }
}

ll Min_cost(ll s, ll t, ll totflow) {
    ll res = 0;
    memset(H, 0, sizeof(H));
    while (totflow) {
        Dij(t);
        if (dis[t] == dis[0])break;
        for (ll i = 1; i <= t; ++i)H[i] += dis[i];
        ll mi = totflow, pos = t;
        while (preV[pos] != -1) {
            mi = min(mi, G[preV[pos]][preE[pos]].flow);
            pos = preV[pos];
        }
        pos = t;
        res += mi * H[t];
        totflow -= mi;
        while (preV[pos] != -1) {
            G[preV[pos]][preE[pos]].flow -= mi;
            G[pos][G[preV[pos]][preE[pos]].rev].flow += mi;
            pos = preV[pos];
        }
    }
//    cout << 1e9 - totflow << endl;
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    ll sum = 0;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
//    cout << sum  << endl;
    sum /= n;
    for (ll i = 1; i <= n; i++) {
        Add(1, i + 1, a[i], 0);
        Add(i + 1, n + 2, sum, 0);
        if (i < n) {
            Add(i + 1, i + 2, 1e9, 1);
        }
        if (i > 1) {
            Add(i + 1, i, 1e9, 1);
        }
    }
    Add(2, n + 1, 1e9, 1);
    Add(n + 1, 2, 1e9, 1);
    cout << Min_cost(1, n + 2, 1e9) << endl;
    return 0;
}