网络流&dij模板题HDU6582

Posted on | In , ,

题目给出一个有向图，要求阻挡其中的一些边，使得从1到n的最短路径变长，阻挡一条边的代价是这条边的长度。

问题其实就转化为，找到从1到n的所有最短路，并在这些路中找到能阻挡最短路的一些边且边权和最小——也就是找到最短路构成图的最小割。

找所有最短路可以贪心地去找合适的边，什么样的边(u, v)是合适的呢？从1到u，从v到n的最短距离之和等于整体最短路减去这条边权时，意味着这条边可以放在一条最短路中。我们就把它加入新图的集合。

然后对新图求最大流即可。Dinic算法，正常复杂度为$n^2m$，在求解二分图最大匹配时复杂度是$m\sqrt{n}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
int t,n,m;
const int maxn=1e4+4;
struct edge{
    int to;
    ll cap,flow;
    edge(int _to,ll _cap,ll _flow):to(_to),cap(_cap),flow(_flow){}
};

typedef pair<ll,int> P;
vector<edge> G[maxn],invG[maxn],sG[maxn];
ll d[maxn],invd[maxn];

void dijkstra(){
    priority_queue<P,vector<P>,greater<P>> que;
    memset(d,inf,sizeof(d));
    que.push(P(0,1));
    d[1]=0;
    while(!que.empty()){
        P p=que.top();que.pop();	//队列里存着被更新过的点
        int u=p.second;
        if(p.first>d[u])    //这个点的值已经过时了，且由于在把它从队列里拿出来之前已经更新为更小值，它甚至已经做过跳板，没有必要再做了
            continue;
        for(int i=0;i<G[u].size();i++){
            edge e=G[u][i];
            if(d[u]+e.cap<d[e.to]){
                d[e.to]=d[u]+e.cap;
                que.push(P(d[e.to],e.to));
            }
        }
    }
    memset(invd,inf,sizeof(invd));
    que.push(P(0,n));
    invd[n]=0;
    while(!que.empty()){
        P p=que.top();que.pop();
        int u=p.second;
        if(p.first>invd[u])    //之前有更优的，已经是第二次用这个点，相当于vis[u]=1，就直接弃用
            continue;
        for(int i=0;i<invG[u].size();i++){
            edge e=invG[u][i];
            if(invd[u]+e.cap<invd[e.to]){
                invd[e.to]=invd[u]+e.cap;
                que.push(P(invd[e.to],e.to));
            }
        }
    }
}


struct Dinic {
    int n,m,s, t;
    vector<edge> edges;
    vector<int> G[maxn];	//储存边在edges中的下标
    int d[maxn], cur[maxn];
    bool vis[maxn];

    void init(int n) {
        for(int i = 1; i <= n; i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, int cap) {
        edges.push_back(edge(to, cap, 0));
        edges.push_back(edge(from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);	//记录刚加入的两条边
        G[to].push_back(m - 1);
    }

    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); i++) {
                edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];	//还有增广路
    }

    ll DFS(int x, ll a) {
        //a是当前可允许的最大流量
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++) {
            edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;	//因为一次必定添加一对，所以原边下标是偶数，反向边是奇数
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    ll Maxflow(int s, int t) {
        this->s = s;
        this->t = t;
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, inf);
        }
        return flow;
    }
};

int main(){
    cin>>t;
    while(t--){
        scanf("%d%d",&n,&m);
        int u,v,c;
        for(int i=1;i<=n;i++){
            G[i].clear();
            invG[i].clear();
        }
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&c);
            G[u].push_back(edge(v,c,0));
            invG[v].push_back(edge(u,c,0)); //添加反向边
        }
        dijkstra();
        Dinic dinic;
        dinic.init(n);
        for(int i=1;i<=n;i++){
            for(int j=0;j<G[i].size();j++){
                if(d[i]+G[i][j].cap+invd[G[i][j].to]==d[n]){
                    dinic.AddEdge(i,G[i][j].to,G[i][j].cap);
                }
            }
        }
        cout<<dinic.Maxflow(1,n)<<endl;
    }
    return 0;
}