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=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

const LL INF = 1e18;

int a[], b[];LL c[];

namespace Dijkstra{

    LL dis[N]; bool vis[N]; int head[N], En;

    struct Edge{ int to, nxt;LL w; } e[];

    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[] = ; q.push(pa(, ));

        while (!q.empty()) {

            int u = q.top().second; q.pop();

            if (vis[u]) continue;

            vis[u] = ;

            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[];

    int head[N], cur[N], q[N], dis[N], En = , 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 = , e[En].nxt = head[v]; head[v] = En;

    }

    bool bfs() {

        for (int i = ; i <= T; ++i) dis[i] = -, cur[i] = head[i];

        int L = , R = ; q[++R] = S; dis[S] = ;

        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] == - && e[i].cap > ) {

                    dis[v] = dis[u] + , q[++R] = v;

                    if (v == T) return ;

                }

            }

        }

        return ;

    }

    LL dfs(int u,LL flow) {

        if (u == T) return flow;

        LL used = , tmp = ;

        for (int &i = cur[u]; i; i = e[i].nxt) {

            int v = e[i].to;

            if (dis[v] == dis[u] +  && e[i].cap > ) {

                tmp = dfs(v, min(flow - used, e[i].cap));

                if (tmp > ) {

                    e[i].cap -= tmp, e[i ^ ].cap += tmp, used += tmp;

                    if (used == flow) break;

                }

            }

        }

        if (used != flow) dis[u] = -;

        return used;

    }

    LL dinic() {

        LL ans = ;

        while (bfs()) ans += dfs(S, INF);

        return ans;

    }

}

int main() {

    int n = read(), m = read();

    for (int i = ; 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 = ; 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 = ; i <= n; ++i) {

        int c = read();

        if (i ==  || i == n) Dinic::add_edge(i, i + n, INF);

        else Dinic::add_edge(i, i + n, c);

    }

    Dinic::S = , Dinic::T = n + n;

    cout << Dinic::dinic();

    return ;

}