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; }
|