Path - 2019 Multi-University Training Contest 1

题意

有一张n个点，m条边的有向图，切边的代价为边权，要求以最小的代价切掉一些边，使最短路变长

思路

先跑一遍Dijkstra，获得最短路，然后依照以下方法构造最短路图

if(dis[u[i]]+w[i] == dis[v[i]]){
    addEdge(u[i],v[i],w[i]);
}

其中dis[i]表示第1个点到第i个点的距离，u[i],v[i],w[i]分别为起点，终点，边权

之后就是求这张最短路图的最小割，根据最大流最小割定理，Dinic 跑一遍最大流即可

时间复杂度 O(玄学)

Code

//ItsLucas 2019.07.22

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;

const long long maxn = 10010;

struct node {
    long long v,w;
    node(long long v=0,long long w=0): v(v), w(w){};
    inline bool operator<(const node &a) const { 
        return w > a.w; 
    }
};

vector<node> G[maxn];
ll dis[maxn];
bool vis[maxn];
long long u[maxn],v[maxn],w[maxn];

inline void add(long long u,long long v,long long w) {
    G[u].push_back(node(v,w));
}

void init() {
    for (long long i = 0; i < maxn; i++) {
        G[i].clear();
        vis[i] = false;
        dis[i] = 1e18;
    }
}

void dijkstra(long long s) {
    priority_queue<node> Q;
    Q.push(node(s,0));
    dis[s] = 0;
    while(!Q.empty()) {
        node now = Q.top();
        Q.pop();
        long long v = now.v;
        if(vis[v]) continue;
        vis[v] = true;
        for(node i : G[v]) {
            long long v2 = i.v;
            long long len = i.w;
            if(!vis[v2] && dis[v2] > dis[v] + len) {
                dis[v2] = dis[v] + len;
                Q.push(node(v2,dis[v2]));
            }
        }
    }
}

struct Edge {
    long long to, cap;
    Edge(long long to, long long cap) : to(to), cap(cap) {}
};

struct Dinic {
    const long long INF = 1e18;
    long long n, s, t;
    vector<Edge> es;
    vector<vector<long long> > G;
    vector<long long> dis, cur;
    Dinic(long long n, long long s, long long t) : n(n), s(s), t(t), G(n + 1), dis(n + 1), cur(n + 1) {}

    void addEdge(long long u, long long v, long long cap) {
        G[u].push_back(es.size());
        es.emplace_back(v, cap);
        G[v].push_back(es.size());
        es.emplace_back(u, 0);
    }

    bool bfs() {
        dis.assign(n + 1, 0);
        queue<long long> q;
        q.push(s);
        dis[s] = 1;
        while (!q.empty()) {
            long long u = q.front();
            q.pop();
            for (long long i : G[u]) {
                Edge& e = es[i];
                if (!dis[e.to] && e.cap > 0) {
                    dis[e.to] = dis[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return dis[t];
    }

    long long dfs(long long u, long long cap) {
        if (u == t || cap == 0) return cap;
        long long tmp = cap, f;
        for (long long& i = cur[u]; i < G[u].size(); i++) {
            Edge& e = es[G[u][i]];
            if (dis[e.to] == dis[u] + 1) {
                f = dfs(e.to, min(cap, e.cap));
                e.cap -= f;
                es[G[u][i] ^ 1].cap += f;
                cap -= f;
                if (cap == 0) break;
            }
        }
        return tmp - cap;
    }

    ll solve() {
        ll flow = 0;
        while (bfs()) {
            cur.assign(n + 1, 0);
            flow += dfs(s, INF);
        }
        return flow;
    }
};

int main() {
    long long t;
    cin>>t;
    while(t-->0) {
        long long n,m;
        cin>>n>>m;
        init();
        for(long long i=1;i<=m;i++) {
            cin>>u[i]>>v[i]>>w[i];
            add(u[i],v[i],w[i]);
        }
        dijkstra(1);
        Dinic dinic = Dinic(n,1,n);
        for(long long i=1;i<=m;i++) {
            if(dis[u[i]]+w[i] == dis[v[i]]){
                dinic.addEdge(u[i],v[i],w[i]);
            }
        }
        cout<<dinic.solve()<<endl;
    }
    return 0;
}