BZOJ 3931 / Luogu P3171 [CQOI2015]网络吞吐量 (最大流板题)

题面

分析

这题建图是显然的,拆点后 $i$ 和 $i'$ 连容量为吞吐量的边,根据题目要求, $1$ 和 $n$ 的吞吐量看作 $infty$ .
然后用 $dist$ 表示到 $1$ 的最小距离,对于满足 $dist[v]=dist[u]+w[u,v]$ 的边, $u'$ 和 $v$ 连容量为 $infty$ 的边.最后建一个超级源点和超级汇点,分别与 $1$ 和 $n'$ 连容量为 $infty$ 的边,跑最大流就行了.

CODE

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<typename T>inline void read(T &num) {
    char ch; while((ch=getc())<'0'||ch>'9');
    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getc());
}

const int MAXN = 1005;
const int MAXM = 200005;
const LL inf = 1e15;
int n, m, S, T; LL dist[MAXN];
vector<pair<int, int> >v[MAXN];
int fir[MAXN], info[MAXN], cnt;
struct edge { int to, nxt; LL c; }e[MAXM];
inline void add(int u, int v, LL cc) {
    e[cnt] = (edge){ v, fir[u], cc }; fir[u] = cnt++;
    e[cnt] = (edge){ u, fir[v], 0 }; fir[v] = cnt++;
}
int q[MAXN], vis[MAXN], cur, dis[MAXN];
inline bool bfs() {
    int head = 0, tail = 0;
    vis[S] = ++cur; q[tail++] = S;
    while(head < tail) {
        int u = q[head++];
        for(int i = fir[u]; ~i; i = e[i].nxt)
            if(e[i].c && vis[e[i].to] != cur)
                dis[e[i].to] = dis[u] + 1, vis[e[i].to] = cur, q[tail++] = e[i].to;
    }
    if(vis[T] == cur) memcpy(info, fir, (T+1)<<2);
    return vis[T] == cur;
}
LL dfs(int u, LL Max) {
    if(u == T || Max == 0) return Max;
    LL flow = 0, delta;
    for(int &i = info[u]; ~i; i = e[i].nxt)
        if(e[i].c && dis[e[i].to] == dis[u] + 1 && (delta=dfs(e[i].to, min(Max-flow, e[i].c)))) {
            e[i].c -= delta, e[i^1].c += delta, flow += delta;
            if(flow == Max) return flow;
        }
    return flow;
}
inline LL dinic() {
    memset(vis, 0, sizeof vis);
    LL flow = 0, x;
    while(bfs()) {
        while((x=dfs(S, inf)))
            flow += x;
    }
    return flow;
}
queue<int>Q;
inline void spfa() {
    memset(dist, 0x7f, sizeof dist);
    dist[1] = 0; Q.push(1);
    while(!Q.empty()) {
        int u = Q.front(); Q.pop(); vis[u] = 0;
        for(int i = 0, siz = v[u].size(); i < siz; ++i)
            if(dist[v[u][i].first] > dist[u] + v[u][i].second) {
                dist[v[u][i].first] = dist[u] + v[u][i].second;
                if(!vis[v[u][i].first])
                    vis[v[u][i].first] = 1, Q.push(v[u][i].first);
            }
    }
}
int main ()
{
    memset(fir, -1, sizeof fir);
    read(n), read(m); S = 0, T = n+n+1;
    for(int i = 1, x, y, z; i <= m; ++i) {
        read(x), read(y), read(z);
        v[x].push_back(make_pair(y, z));
        v[y].push_back(make_pair(x, z));
    }
    spfa();
    add(S, 1, inf); add(n+n, T, inf);
    for(int i = 1, x; i <= n; ++i) read(x), add(i, i+n, (i>1&&i<n) ? x : inf);
    for(int i = 1; i <= n; ++i)
        for(int j = 0, siz = v[i].size(); j < siz; ++j)
            if(dist[v[i][j].first] == dist[i] + v[i][j].second)
                add(i+n, v[i][j].first, inf);
    printf("%lld
", dinic());
}

其实这道题挺水的,本来不想写博客,但是不知怎么的就 $BZOJ rank 1$ 了…截图留念