【bzoj3931】[CQOI2015]网络吞吐量

2015.05.01 14:55 Fri | 20次阅读 | 旧日oi | 固定链接 | 源码

Description

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

Input

输入文件第一行包含两个空格分开的正整数n和m,分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。接下来m行,每行包含三个空格分开的正整数a、b和d,表示从路由器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≤500,m≤100000,d,c≤10^9

题解

题目看懂之后就是一眼题了,dij求出最短路径图然后跑最大流就行了……

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define inf 0x3f3f3f3f3f3f3f3fll
#define ll long long
using namespace std;
int n,m,u,v;
struct edge
{
    int to;
    int next;
    ll flow;
}e[200005];
struct node
{
    ll dis;
    int idx;
    node(ll _ ,int __):dis(_),idx(__){}
    bool operator < (const node &a) const{
        return dis>a.dis;
    }
};
int h[1005],tp;
ll dis[1005],d,mx[1005],mp[1005][1005];
bool vis[1005];
void ae(int u,int v,ll w)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp++;
}
void add(int u,int v,ll w)
{
    ae(u,v,w);ae(v,u,0);
}
priority_queue<node> pq;
vector<int> fr[1005];
void dij()
{
    memset(dis,0x3f,sizeof(dis));dis[1]=0;
    pq.push(node(0,1));
    while(!pq.empty())
    {
        int u=pq.top().idx;pq.pop();
        if(vis[u]) continue;vis[u]=1;
        for(int v=1;v<=n;v++)
        if(mp[u][v]!=inf)
        {
            if(dis[v]>dis[u]+mp[u][v])
            {
                fr[v].clear();fr[v].push_back(u);
                dis[v]=dis[u]+mp[v][u];
                pq.push(node(dis[v],v));
            }
            else if(dis[v]==dis[u]+mp[u][v]) fr[v].push_back(u);
        }
    }
}
queue<int> q;
void build()
{
    memset(vis,0,sizeof(vis));
    for(int i=2;i<n;i++) add(i,i+n,mx[i]);
    add(1,n+1,inf);
    q.push(n);vis[n]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=0;i<fr[u].size();i++)
        {
            v=fr[u][i];
            add(v+n,u,inf);
            if(!vis[v])
            {
                vis[v]=1;
                q.push(v);
            }
        }
    }
}
bool bfs()
{
    memset(dis,0,sizeof(dis));dis[1]=1;
    while(!q.empty()) q.pop();
    q.push(1);vis[v]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==n) return 1;
            q.push(v);
        }
    }
    return 0;
}
ll dfs(int u,ll limit)
{
    if(u==n) return limit;
    ll tmp,cost=0;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(limit-cost,e[i].flow));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
ll dinic()
{
    ll ret=0;
    while(bfs())
        ret+=dfs(1,inf);
    return ret;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    memset(mp,0x3f,sizeof(mp));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lld",&u,&v,&d);
        mp[u][v]=mp[v][u]=min(mp[u][v],d);
    }
    for(int i=1;i<=n;i++) scanf("%lld",&mx[i]);
    dij();build();
    printf("%lld\n",dinic());
}```