NC19939 [CQOI2015]网络吞吐量

题目：

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

题解：

第一反应是最小费用最大流，但其实并不是
题目要求的是在最短路的基础上求最大吞吐量
若我们要走1到n的最短路，那我们只能走dis[v]=dis[u]+edge[u][v]的边
所以我们第一步就跑遍最短路，保留最短路中的边，此时边权我们就可以忽略掉了，因为之后再也用不上
题目中吞吐量的限制与平常不一样，这里不是对边而是对点，对点的话没办法直接算，我们可以将点一分为二，将n个点拆成n*2个点，然后第i个点向第i+n个点建立一个容量为A[i]的边
然后对于最短路中的边e[u][v]，我们从第u+n个点向第v个点建一条容量为inf的边
从源点s向点1建一条容量为inf的边
从点2n向汇点t建立一条容量为inf的边
然后跑最大流即可
本题的特殊之处就在于先用最短路处理一下，剩下的步骤都是最大流常规操作了、

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define inf 0x7fffffffff/2
#define eps 1e-6
#define N 2010
#define M 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
ll dist[N];
struct edge
{
    int next,to;
    ll fl;
}e[M<<1];
int cnt=1,head[N];
int n,m;
int vis[N];
ll c[N];
int s,t;
int depth[N];
queue<int>Q;
vector<int>to[N];
vector<ll>v[N];
inline void add_edge(int from,int to,ll fl)
{
    e[++cnt].to=to;
    e[cnt].next=head[from];
    e[cnt].fl=fl;
    head[from]=cnt;
}
inline int bfs()
{
    while(!Q.empty())Q.pop();memset(depth,0,sizeof(depth));
    Q.push(s);depth[s]=1;
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(register int i=head[x];i;i=e[i].next)
        {
            if(!depth[e[i].to]&&e[i].fl>0)
            {
                depth[e[i].to]=depth[x]+1;
                Q.push(e[i].to);
            }
        }
    }
    return depth[t];
}
ll dfs(int now,ll flow)
{
    if(now==t)return flow;
    ll ret=0;
    for(register int i=head[now];i;i=e[i].next)
    {
        if(ret==flow)return ret;
        if(depth[e[i].to]==depth[now]+1&&e[i].fl>0)
        {
            ll fl=dfs(e[i].to,min(flow-ret,e[i].fl));
            if(fl>0)
            {
                ret+=fl;
                e[i].fl-=fl;
                e[i^1].fl+=fl;
            }
        }
    }
    return ret;
}
inline ll Dinic()
{
    ll sum=0;
    while(bfs())
    {
        ll x=1;while(x){x=dfs(s,inf);sum+=x;}
    }
    return sum;
}
inline void spfa()
{
    for(register int i=2;i<=n;i++)dist[i]=inf;
    while(!Q.empty())Q.pop();
    Q.push(1);vis[1]=1;
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();vis[x]=0;
        for(register int i=0;i<to[x].size();i++)
        {
            int go=to[x][i];
            ll val=v[x][i];
            if(dist[x]+val<dist[go])
            {
                dist[go]=dist[x]+val;
                if(!vis[go])
                {
                    vis[go]=1;
                    Q.push(go);
                }
            }
        }
    }
} 
int main()
{
    n=read(),m=read();
    t=n*2+1;
    for(register int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        ll val=read();
        to[x].push_back(y);v[x].push_back(val);
        to[y].push_back(x);v[y].push_back(val);
    }
    spfa();
    for(register int i=1;i<=n;i++)c[i]=read();
    add_edge(s,1,inf);add_edge(1,s,0);
    add_edge(2*n,t,inf);add_edge(t,2*n,0);
    for(register int i=1;i<=n;i++)
    {
        if(i!=1&&i!=n)
        {
            add_edge(i,i+n,c[i]);
            add_edge(i+n,i,0);
        }
        else 
        {
            add_edge(i,i+n,inf);
            add_edge(i+n,i,0);
        }
    }//通过拆点对每个点经过的流量进行限制
    for(register int i=1;i<=n;i++)
    {
        for(register int j=0;j<to[i].size();j++)
        {
            int go=to[i][j];
            ll val=v[i][j];
            if(dist[go]==dist[i]+val)//在最短路中
            {
                add_edge(i+n,go,inf);
                add_edge(go,i+n,0);
            }
        }
    }//对在最短路中的边建边 
    printf("%lld\n",Dinic());
    return 0;
}