题目描述
现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），网络中的路由器使用 (1) 到 (n) 编号，假设所有数据包一定沿最短路径转发，试计算从路由器 (1) 到路由器 (n) 的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器 (1) 到路由器 (n) 作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将 (1) 和 (n) 直接相连的链路。
输入格式
输入的第一行是用空格隔开的两个整数，分别代表路由器的数量 (n) 和链路的数量 (m)。
第 (2) 到第 ((m + 1)) 行，每行三个整数 (u, v, w)，代表存在一条连结路由器 (u) 和路由器 (v) 的距离为 (w) 的双向链路。
第 ((m + 2)) 到第 ((n + m + 1)) 行，每行一个整数，第 ((i + m + 1)) 行的整数代表路由器 (i) 的吞吐量 (c_i)。
输出格式
输出一行一个整数，代表网络的最大吞吐量。
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
#define int long long
const int N=1e4+5,M=4e5+5,inf=9223372036854775807;
inline int read(){
int x=0; char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); }
return x;
}
int nxt[M],head[N],go[M],edge[M],tot=1;
inline void add(int u,int v,int w){
nxt[++tot]=head[u],head[u]=tot,go[tot]=v,edge[tot]=w;
nxt[++tot]=head[v],head[v]=tot,go[tot]=u,edge[tot]=0;
}
int d[N],s,t;
inline bool bfs(){
memset(d,0,sizeof(d));
queue<int>q; q.push(s); d[s]=1;
while(q.size()){
int u=q.front(); q.pop();
for(int i=head[u];i;i=nxt[i]){
int v=go[i];
if(edge[i]&&!d[v]){
d[v]=d[u]+1;
q.push(v);
if(v==t)return 1;
}
}
}
return 0;
}
int dinic(int u,int flow){
if(u==t)return flow;
int rest=flow;
for(int i=head[u];i&&rest;i=nxt[i]){
int v=go[i];
if(edge[i]&&d[v]==d[u]+1){
int k=dinic(v,min(rest,edge[i]));
if(!k)d[v]=-1;
edge[i]-=k;
edge[i^1]+=k;
rest-=k;
}
}
return flow-rest;
}
int n,m,c[N];
bool vis[N];
vector<pair<int,int> >vec[N];
inline void spfa(){
for(int i=1;i<=n;i++)d[i]=inf;
queue<int>q; q.push(s); d[s]=0;
while(q.size()){
int u=q.front(); q.pop(); vis[u]=0;
for(int i=0;i<vec[u].size();i++){
int v=vec[u][i].fi;
int w=vec[u][i].se;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
}
struct node{
int u,v,w;
}e[M];
signed main(){
n=read(),m=read();
s=1,t=n;
for(int i=1,u,v,w;i<=m;i++){
u=read(),v=read(),w=read();
vec[u].pb(mp(v,w)),vec[v].pb(mp(u,w));
e[i]=(node){u,v,w};
}
spfa();
for(int i=1;i<=n;i++)c[i]=read(); c[1]=c[n]=inf;
for(int i=1;i<=n;i++)add(i,i+n,c[i]);
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
if(d[u]+w==d[v])add(u+n,v,inf);
if(d[v]+w==d[u])add(v+n,u,inf);
}
int flow=0,maxflow=0;
while(bfs())while(flow=dinic(s,inf))maxflow+=flow;
cout<<maxflow<<endl;
}