【BZOJ3931】[CQOI2015]网络吞吐量

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

HINT

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

题解：本题理解题意是关键。意思是你只能沿着最短路走，然后求最大流

直接dijkstra求出那些边在最短路上，把其他边删掉就好了，然后拆点求最大流

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

#include <utility>

#define mp(A,B) make_pair(A,B)

using namespace std;

typedef long long ll;

int n,m,cnt,S,T;

int to[1000000],next[1000000],head[1010],vis[1010];

int pa[100010],pb[100010],pc[100010],d[1010];

ll dis[1010],ans,val[1000000];

queue<int> q;

priority_queue<pair<ll,int> > pq;

int rd()

{

    int ret=0,f=1;  char gc=getchar();

    while(gc<'0'||gc>'9') {if(gc=='-')f=-f;   gc=getchar();}

    while(gc>='0'&&gc<='9')   ret=ret*10+gc-'0',gc=getchar();

    return ret*f;

}

void add(int a,int b,int c)

{

    to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;

}

int dfs(int x,int mf)

{

    if(x==T)    return mf;

    int i,k,temp=mf;

    for(i=head[x];i!=-1;i=next[i])

    {

        if(d[to[i]]==d[x]+1&&val[i])

        {

            k=dfs(to[i],min(temp,(int)val[i]));

            if(!k)  d[to[i]]=0;

            val[i]-=k,val[i^1]+=k,temp-=k;

            if(!temp)   break;

        }

    }

    return mf-temp;

}

void dij()

{

    int i,u;

    while(!pq.empty())  pq.pop();

    memset(dis,0x3f,sizeof(dis));

    dis[1]=0,pq.push(mp(0,1));

    while(!pq.empty())

    {

        u=pq.top().second,pq.pop();

        if(vis[u])  continue;

        vis[u]=1;

        for(i=head[u];i!=-1;i=next[i])

        {

            if(dis[to[i]]>dis[u]+val[i])

            {

                dis[to[i]]=dis[u]+val[i];

                pq.push(mp(-dis[to[i]],to[i]));

            }

        }

    }

}

int bfs()

{

    memset(d,0,sizeof(d));

    while(!q.empty())   q.pop();

    int i,u;

    q.push(S),d[S]=1;

    while(!q.empty())

    {

        u=q.front(),q.pop();

        for(i=head[u];i!=-1;i=next[i])

        {

            if(!d[to[i]]&&val[i])

            {

                d[to[i]]=d[u]+1;

                if(to[i]==T)    return 1;

                q.push(to[i]);

            }

        }

    }

    return 0;

}

int main()

{

    n=rd(),m=rd();

    int i,a,b,c;

    memset(head,-1,sizeof(head));

    for(i=1;i<=m;i++)

    {

        pa[i]=rd(),pb[i]=rd(),pc[i]=rd();

        add(pa[i],pb[i],pc[i]),add(pb[i],pa[i],pc[i]);

    }

    dij();

    memset(head,-1,sizeof(head)),cnt=0;

    for(i=1;i<=m;i++)

    {

        if(dis[pa[i]]==dis[pb[i]]+pc[i])    add(pb[i]+n,pa[i],1<<30),add(pa[i],pb[i]+n,0);

        if(dis[pb[i]]==dis[pa[i]]+pc[i])    add(pa[i]+n,pb[i],1<<30),add(pb[i],pa[i]+n,0);

    }

    for(i=1;i<=n;i++)    add(i,i+n,rd()),add(i+n,i,0);

    S=1+n,T=n;

    while(bfs())    ans+=dfs(S,1<<30);

    printf("%lld",ans);

    return 0;

}

巴特西

【BZOJ3931】[CQOI2015]网络吞吐量最大流

【BZOJ3931】[CQOI2015]网络吞吐量

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

【BZOJ3931】[CQOI2015]网络吞吐量 最大流

【BZOJ3931】[CQOI2015]网络吞吐量

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

【BZOJ3931】[CQOI2015]网络吞吐量最大流