[AHOI 2006] 上学路线

发表于2017-04-26更新于2020-08-06

题目大意

题目有两问。第一问是求给定的两点间最短路；第二问中，每条边除了权值 ww 以外还有一个代价 cc，求使那两点间最短路变大（不再联通也算）的最小代价。

2⩽n⩽5002 \leqslant n \leqslant 500

1⩽m⩽124,7501 \leqslant m \leqslant 124,750

1⩽w,  c⩽10,0001 \leqslant w, \; c \leqslant 10,000

题目链接

【AHOI 2006】上学路线 - Luogu 4300

题解

第一问直接跑 Dijkstra 就行了。。。

第二问，对于所有在最短路上的边，以代价为容量建最小割；判断一条边是否在最短路上，以起点、终点为源各跑一遍 Dijkstra，满足 e.u.dist[s]+e.w+e.v.dist[t]=t.dist[s]=s.dist[t]e.u.dist[s] + e.w + e.v.dist[t] = t.dist[s] = s.dist[t] 就是。

代码

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
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
#include <new>
const int MAXN = 505;
const int MAXM = 124755;
struct EdgeD;
struct NodeD {
    EdgeD *e;
    int dist[2], id;
    bool vis[2];
} ND[MAXN];
struct EdgeD {
    NodeD *u, *v;
    EdgeD *next;
    int w, c;
    EdgeD() {}
    EdgeD(NodeD *u, NodeD *v, int w, int c) : u(u), v(v), w(w), c(c), next(u->e) {}
} _pool[MAXM << 1], *_cur = _pool;
void addEdgeD(int  u, int v, int w, int c) {
    ND[u].e = new (_cur++) EdgeD(&ND[u], &ND[v], w, c);
    ND[v].e = new (_cur++) EdgeD(&ND[v], &ND[u], w, c);
}
namespace Dijkstra {
    struct HeapNode {
        NodeD *u;
        int dist;
        bool operator<(const HeapNode &another) const {
            return dist > another.dist;
        }
    };
    void solve(NodeD *s, int id, int n) {
        for (int i = 1; i <= n; i++) {
            ND[i].dist[id] = INT_MAX;
            ND[i].vis[id] = false;
        }
        std::priority_queue<HeapNode> q;
        s->dist[id] = 0;
        q.push((HeapNode) {s, 0});
        while (!q.empty()) {
            NodeD *u = q.top().u;
            q.pop();
            if (u->vis[id]) continue;
            u->vis[id] = true;
            for (EdgeD *e = u->e; e; e = e->next) {
                if (e->v->dist[id] > u->dist[id] + e->w) {
                    e->v->dist[id] = u->dist[id] + e->w;
                    q.push((HeapNode) {e->v, e->v->dist[id]});
                }
            }
        }
    }
}
struct Edge;
struct Node {
    Edge *e, *curr;
    int level;
} N[MAXN];
struct Edge {
    Node *u, *v;
    Edge *next, *rev;
    int cap, flow;
    Edge(Node *u, Node *v, int cap) : u(u), v(v), cap(cap), flow(0), next(u->e) {}
};
void addEdge(int u, int v, int cap) {
    N[u].e = new Edge(&N[u], &N[v], cap);
    N[v].e = new Edge(&N[v], &N[u], 0);
    N[u].e->rev = N[v].e;
    N[v].e->rev = N[u].e;
}
namespace Dinic {
    bool makeLevelGraph(Node *s, Node *t, int n) {
        for (int i = 1; i <= n; i++) N[i].level = 0;
        std::queue<Node *> q;
        q.push(s);
        s->level = 1;
        while (!q.empty()) {
            Node *u = q.front();
            q.pop();
            for (Edge *e = u->e; e; e = e->next) {
                if (e->cap > e->flow && e->v->level == 0) {
                    e->v->level = u->level + 1;
                    if (e->v == t) return true;
                    q.push(e->v);
                }
            }
        }
        return false;
    }
    int findPath(Node *s, Node *t, int limit = INT_MAX) {
        if (s == t) return limit;
        for (Edge *&e = s->curr; e; e = e->next) {
            if (e->cap > e->flow && e->v->level == s->level + 1) {
                int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
                if (flow > 0) {
                    e->flow += flow;
                    e->rev->flow -= flow;
                    return flow;
                }
            }
        }
        return 0;
    }
    int solve(int s, int t, int n) {
        int res = 0;
        while (makeLevelGraph(&N[s], &N[t], n)) {
            for (int i = 1; i <= n; i++) N[i].curr = N[i].e;
            int flow;
            while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
        }
        return res;
    }
}
void build(int dist) {
    for (EdgeD *e = _pool; e != _cur; e++) {
        if (e->u->dist[0] + e->v->dist[1] + e->w == dist) {
            addEdge(e->u->id, e->v->id, e->c);
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w, c;
        scanf("%d %d %d %d", &u, &v, &w, &c);
        addEdgeD(u, v, w, c);
    }
    Dijkstra::solve(&ND[1], 0, n);
    printf("%d\n", ND[n].dist[0]);
    Dijkstra::solve(&ND[n], 1, n);
    for (int i = 1; i <= n; i++) ND[i].id = i;
    build(ND[n].dist[0]);
    printf("%d\n", Dinic::solve(1, n, n));
    return 0;
}