传送门:

BZOJ

洛谷


Description

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


Input

输入文件第一行包含两个空格分开的正整数nm,分别表示路由器数量和链路的数量。网络中的路由器使用1n编号。接下来m行,每行包含三个空格分开的正整数abd,表示从路由器a到路由器b存在一条距离为d的双向链路。 接下来n行,每行包含一个正整数c,分别给出每一个路由器的吞吐量。

Output

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


Sample Input

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

70

HINT

对于100 \%的数据,n \le 500,m \le 100000,d,c \le 10^9


解题思路:

首先跑一遍最短路,这是肯定的。

然后我们考虑拆点,将每个点拆成在最短路上和不在最短路上两种情况来讨论,首先i \to i+n,容量为c_i,然后枚举点u和与其相连的点v,判断是否是最短路径上的边,如果是则u+n \to v,容量为inf

Code:

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll inf=1e18;
const int maxn=2e3+10;
const int maxm=1e5+10;
ll maxflow,dis[maxn];queue<int >q;
struct node{int to,nxt;ll w;}e[maxm<<1],e1[maxm<<1];
int n,m,S,T,tot,tot1,c[maxn],head[maxn],head1[maxn],d[maxn];bool vis[maxn];
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(ll x){print(x);puts("");}
void add(int u,int v,int w){e1[++tot1].to=v;e1[tot1].w=w;e1[tot1].nxt=head1[u];head1[u]=tot1;}
void insert(int u,int v,ll w){
    e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;
    e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
bool bfs(){
    memset(d,0,sizeof(d));
    while(!q.empty())q.pop();
    q.push(S);d[S]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
            if(e[i].w&&!d[v]){
                q.push(v);d[v]=d[x]+1;
                if(v==T)return 1;
            }
    }return 0;
}
ll dinic(int x,ll flow){
    if(x==T)return flow;
    ll rest=flow,w;
    for(int i=head[x],v=e[i].to;i&&rest;i=e[i].nxt,v=e[i].to)
        if(e[i].w&&d[v]==d[x]+1){
            w=dinic(v,min(rest,e[i].w));
            if(!w)d[v]=0;
            e[i].w-=w;e[i^1].w+=w;rest-=w;
        }
    return flow-rest;
}
void spfa(){
    while(!q.empty())q.pop();
    memset(vis,0,sizeof(vis));
    memset(dis,63,sizeof(dis));
    q.push(1);dis[1]=0;vis[1]=1;
    while(!q.empty()){
        int x=q.front();q.pop();vis[x]=0;
        for(int i=head1[x],v=e1[i].to;i;i=e1[i].nxt,v=e1[i].to)
            if(dis[x]+e1[i].w<dis[v]){
                dis[v]=dis[x]+e1[i].w;
                if(!vis[v]){vis[v]=1;q.push(v);}
            }
    }
}
int main(){
    n=read();m=read();S=0;T=2*n+1;tot=1;
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }spfa();
    for(int i=1;i<=n;i++)c[i]=read();insert(S,1,inf);insert(2*n,T,inf);
    for(int i=1;i<=n;i++)insert(i,i+n,i!=1&&i!=n?c[i]:inf);
    for(int x=1;x<=n;x++)
        for(int i=head1[x],v=e1[i].to;i;i=e1[i].nxt,v=e1[i].to)
            if(dis[v]==dis[x]+e1[i].w)insert(x+n,v,inf);
    while(bfs())maxflow+=dinic(S,inf);write(maxflow);
    return 0;
}