「BZOJ3931」[CQOI2015]网络吞吐量

Description

路由是指通过计算机网络把信息从源地址传输到目的地址的活动,也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地,路由器需要选择最优的路径转发数据包。例如在常用的路由算法 OSPF (开放式最短路径优先) 中,路由器会使用经典的 Dijkstra 算法计算最短路径,然后尽量沿最短路径转发数据包。现在,若已知一个计算机网络中各路由器间的连接情况,以及各个路由器的最大吞吐量(即每秒能转发的数据包数量),假设所有数据包一定沿最短路径转发,试计算从路由器 11 到路由器 nn 的网络的最大吞吐量。计算中忽略转发及传输的时间开销,不考虑链路的带宽限制,即认为数据包可以瞬间通过网络。路由器 11 到路由器 nn 作为起点和终点,自身的吞吐量不用考虑,网络上也不存在将 11nn 直接相连的链路。

Input

输入文件第一行包含两个空格分开的正整数 nnmm,分别表示路由器数量和链路的数量。网络中的路由器使用 11nn 编号。

接下来 mm 行,每行包含三个空格分开的正整数 aabbdd,表示从路由器 aa 到路由器 bb 存在一条距离为 dd 的双向链路。

接下来 nn 行,每行包含一个正整数 cc,分别给出每一个路由器的吞吐量。

Output

输出一个整数,为题目所求吞吐量。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
7 10
1 2 2
1 5 2
2 4 1
2 3 3
3 7 1
4 5 4
4 3 1
4 6 1
5 6 2
6 7 1
1
100
20
50
20
60
1

Sample Output

1
70

HINT

对于 100%100 \% 的数据,n500,m100000, d,c109n \leq 500, m \leq 100000, \ d,c \leq 10^9

Solution

找出最短路上的边(u,v)(u,v),然后网络流上连(u+n,v,inf)(u+n,v,inf)
对于i[2,n)i\in [2,n),连边(i,i+n,ai)(i,i+n,a_i)
(s,n+1,inf),(n,t,inf)(s,n+1,inf),(n,t,inf)
跑一遍最大流就是答案了。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int M = 210000, N = 1100;
int n, m;
const ll inf = 1e16;
struct G {
struct Edge {
int u, v, nxt, w;
}e[M];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].w = z;
}
bool vis[N];
ll d[N];
priority_queue<pii,vector<pii>,greater<pii> >q;
void dijkstra() {
for(int i = 1; i <= n; ++i) d[i] = inf;
d[1] = 0;
q.push(mk(0, 1));
while(!q.empty()) {
pii now = q.top(); q.pop();
int x = now.se;
if(vis[x]) continue;
vis[x] = 0;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(d[y] > d[x] + e[i].w) {
d[y] = d[x] + e[i].w;
q.push(mk(d[y], y));
}
}
}
}
}g1;
int s, t;
struct G2 {
int head[N * 2], en;
struct Edge {
int u, v, nxt;
ll f;
}e[M * 8];
void addedge(int x, int y, ll z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], e[en].f = z, head[x] = en;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int d[N * 2];
bool bfs() {
queue<int>q;
q.push(s);
memset(d, 0, sizeof d);
d[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f) {
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
ll dinic(int x, ll flow) {
if(x == t) return flow;
ll k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(e[i].f && d[e[i].v] == d[x] + 1) {
k = dinic(e[i].v, min(rest, e[i].f));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow - rest;
}
ll solve() {
ll res = 0, y ;
while(bfs()) {
while(y = dinic(s, inf)) res += y;
}
return res;
}
}g2;
ll a[N];
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read(), z = read();
g1.addedge(x, y, z);
g1.addedge(y, x, z);
}
g1.dijkstra();
g2.en = 1;
for(int i = 1; i <= g1.en; ++i)
if(g1.d[g1.e[i].v] == g1.d[g1.e[i].u] + g1.e[i].w) {
g2.addedge(g1.e[i].u + n, g1.e[i].v, inf);
}
for(int i = 1; i <= n; ++i) a[i] = read();
for(int i = 2; i < n ; ++i) g2.addedge(i, i + n, a[i]);
s = n * 2 + 1;
t = n * 2 + 2;
g2.addedge(s, 1 + n, inf);
g2.addedge(n, t, inf);
writeln(g2.solve());
return 0;
}