[BZOJ3931/Luogu3171][CQOI2015]网络吞吐量(网络流,最短路)

发布于 2018-03-20  66 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3931/Luogu3171][CQOI2015]网络吞吐量(网络流,最短路)

Description

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

Http

BZOJ
Luogu

Tag

网络流,最短路

解决思路

先走出最短路,求出最短路图,保证上面的每一条边的转移都是在最短路上转移,然后求最大流即可。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=510*2;
const int maxM=(100010+maxN)*10;
const ll INF=1e17;

class Edge
{
public:
    ll v,flow;
    ll w;
};

class Queue_Data
{
public:
    int u;
    ll dis;
};

bool operator < (Queue_Data A,Queue_Data B)
{
    return A.dis>B.dis;
}

int n,m,S,T;
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
ll Dist[maxN];
int Depth[maxN],Queue[maxN],cur[maxN];
priority_queue<Queue_Data> Q;
bool vis[maxN];

void Add_Edge(int u,int v,ll w,ll flow);
bool Bfs();
ll dfs(int u,ll flow);

int main()
{
    mem(Head,-1);
    ios::sync_with_stdio(false);
    cin>>n>>m;S=1;T=n+n;
    for (int i=1;i<=m;i++)
    {
        int u,v;ll w;cin>>u>>v>>w;
        if (u!=n) Add_Edge(u+n,v,w,INF);
        if (v!=n) Add_Edge(v+n,u,w,INF);
    }
    for (int i=1;i<=n;i++)
    {
        ll w;cin>>w;
        Add_Edge(i,i+n,0,w);
    }
    Add_Edge(1,1+n,0,INF);Add_Edge(n,n+n,0,INF);
    mem(Dist,-1);Dist[S]=0;//先求最短路
    Q.push((Queue_Data){S,0});
    do
    {
        Queue_Data u=Q.top();Q.pop();
        if (vis[u.u]) continue;
        vis[u.u]=1;
        for (int i=Head[u.u];i!=-1;i=Next[i])
            if ((vis[E[i].v]==0)&&(E[i].flow>0)&&((Dist[E[i].v]==-1)||(Dist[E[i].v]>Dist[u.u]+E[i].w)))
            {
                Dist[E[i].v]=Dist[u.u]+E[i].w;
                Q.push((Queue_Data){E[i].v,Dist[E[i].v]});
            }
    }
    while (!Q.empty());
    ll mxflow=0;//在最短路上走最大流
    while (Bfs())
    {
        for (int i=S;i<=T;i++) cur[i]=Head[i];
        while (ll di=dfs(S,INF)) mxflow=mxflow+di;
    }
    printf("%lld\n",mxflow);
    return 0;
}

void Add_Edge(int u,int v,ll w,ll flow)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;
    E[edgecnt].v=v;E[edgecnt].w=w;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;
    E[edgecnt].v=u;E[edgecnt].w=-w;E[edgecnt].flow=0;
    return;
}

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;Queue[1]=S;Depth[S]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((E[i].flow>0)&&(Dist[E[i].v]==Dist[u]+E[i].w)&&(Depth[E[i].v]==-1))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
    }
    while (t!=h);
    if (Depth[T]==-1) return 0;
    return 1;
}

ll dfs(int u,ll flow)
{
    if (u==T) return flow;
    for (int &i=cur[u];i!=-1;i=Next[i])
        if ((E[i].flow>0)&&(Dist[E[i].v]==Dist[u]+E[i].w)&&(Depth[E[i].v]==Depth[u]+1))
        {
            ll di=dfs(E[i].v,min(flow,E[i].flow));
            if (di)
            {
                E[i].flow-=di;
                E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3931/Luogu3171][CQOI2015]网络吞吐量(网络流,最短路)


HNCJ OIer