3931: [CQOI2015]网络吞吐量

3931: [CQOI2015]网络吞吐量

链接

分析：

　　跑一遍dijkstra，加入可以存在于最短路中的点，拆点最大流。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#define pa pair<LL,int> 
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 2005;
const LL INF = 1e18;
int a[100005], b[100005];LL c[100005];

namespace Dijkstra{
    LL dis[N]; bool vis[N]; int head[N], En;
    struct Edge{ int to, nxt;LL w; } e[500005];
    void add_edge(int u,int v,LL w) {
        ++En; e[En].to = v, e[En].w = w, e[En].nxt = head[u]; head[u] = En;
        ++En; e[En].to = u, e[En].w = w, e[En].nxt = head[v]; head[v] = En;
    }
    priority_queue< pa, vector< pa >, greater< pa > > q;
    void solve() {
        memset(dis, 0x3f, sizeof(dis));
        dis[1] = 0; q.push(pa(0, 1));
        while (!q.empty()) {
            int u = q.top().second; q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].to;
                if (dis[v] > dis[u] + e[i].w) {
                    dis[v] = dis[u] + e[i].w;
                    q.push(pa(dis[v], v));
                }
            }
        }
    }
}
namespace Dinic {
    struct Edge{ int to, nxt;LL cap; } e[500005];
    int head[N], cur[N], q[N], dis[N], En = 1, S, T;
    void add_edge(int u,int v,LL w) {
        ++En; e[En].to = v, e[En].cap = w, e[En].nxt = head[u]; head[u] = En;
        ++En; e[En].to = u, e[En].cap = 0, e[En].nxt = head[v]; head[v] = En;
    }
    bool bfs() {
        for (int i = 0; i <= T; ++i) dis[i] = -1, cur[i] = head[i];
        int L = 1, R = 0; q[++R] = S; dis[S] = 0; 
        while (L <= R) {
            int u = q[L ++];
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].to;
                if (dis[v] == -1 && e[i].cap > 0) {
                    dis[v] = dis[u] + 1, q[++R] = v;
                    if (v == T) return 1;
                }
            }
        }
        return 0;
    }
    LL dfs(int u,LL flow) {
        if (u == T) return flow;
        LL used = 0, tmp = 0;
        for (int &i = cur[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[v] == dis[u] + 1 && e[i].cap > 0) {
                tmp = dfs(v, min(flow - used, e[i].cap));
                if (tmp > 0) {
                    e[i].cap -= tmp, e[i ^ 1].cap += tmp, used += tmp;
                    if (used == flow) break;
                }
            }
        }
        if (used != flow) dis[u] = -1;
        return used;
    }
    LL dinic() {
        LL ans = 0;
        while (bfs()) ans += dfs(S, INF);
        return ans;
    }
}
int main() {
    int n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        a[i] = read(), b[i] = read(), c[i] = read();
        Dijkstra::add_edge(a[i], b[i], c[i]);
    }
    Dijkstra::solve();
    for (int i = 1; i <= m; ++i) {
        if (Dijkstra::dis[a[i]] + c[i] == Dijkstra::dis[b[i]]) {
            Dinic::add_edge(a[i] + n, b[i], INF);
        }
        if (Dijkstra::dis[b[i]] + c[i] == Dijkstra::dis[a[i]]) {
            Dinic::add_edge(b[i] + n, a[i], INF);
        }
    }
    for (int i = 1; i <= n; ++i) {
        int c = read();
        if (i == 1 || i == n) Dinic::add_edge(i, i + n, INF);
        else Dinic::add_edge(i, i + n, c);
    }
    Dinic::S = 1, Dinic::T = n + n;
    cout << Dinic::dinic();
    return 0;
}