首页 > 代码库 > [BZOJ 3931][CQOI2015]网络吞吐量（SPFA+网络流）
[BZOJ 3931][CQOI2015]网络吞吐量（SPFA+网络流）
Description
路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1和n直接相连的链路。
Solution
裸题？
先求最短路看哪些边会被用到，拆点跑一下网络流
（虽然说了“会使用经典的Dijkstra算法计算最短路径”，我还是万年SPFA）
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<queue>#include<vector>#define INF 1LL<<60using namespace std;typedef long long LL;vector<int>G[505];int n,m,s,t,head1[505],head2[1005],level[1005],cnt1=0,cnt2=0;LL dis[505];bool inq[505];struct Node{ int next,to; LL w;}Edges1[200005],Edges2[500005];LL read(){ LL x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}void addedge1(int u,int v,LL w){ Edges1[cnt1].next=head1[u]; head1[u]=cnt1; Edges1[cnt1].to=v; Edges1[cnt1++].w=w;}void addedge2(int u,int v,LL w){ Edges2[cnt2].next=head2[u]; head2[u]=cnt2; Edges2[cnt2].to=v; Edges2[cnt2++].w=w;}void insert(int u,int v,LL w){ addedge2(u,v,w); addedge2(v,u,0);}queue<int>q;void SPFA(){ for(int i=1;i<=n;i++)dis[i]=INF; q.push(1);inq[1]=1,dis[1]=0; while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=head1[u];~i;i=Edges1[i].next) { int v=Edges1[i].to; if(dis[v]>=dis[u]+Edges1[i].w) { dis[v]=dis[u]+Edges1[i].w; G[u].push_back(i),G[v].push_back(i); if(!inq[v]) inq[v]=1,q.push(v); } } }}bool bfs(){ memset(level,-1,sizeof(level)); level[s]=0;q.push(s); while(!q.empty()) { int u=q.front();q.pop(); for(int i=head2[u];~i;i=Edges2[i].next) { int v=Edges2[i].to; if(Edges2[i].w&&level[v]==-1) level[v]=level[u]+1,q.push(v); } } if(level[t]==-1)return false; return true;}LL dfs(int u,LL f){ if(u==t)return f; LL flow=0,d; for(int i=head2[u];~i&&flow<f;i=Edges2[i].next) { int v=Edges2[i].to; if(level[v]==level[u]+1&&Edges2[i].w) { d=dfs(v,min(Edges2[i].w,f-flow)); flow+=d; Edges2[i].w-=d; Edges2[i^1].w+=d; } } if(!flow)level[u]=-1; return flow;}void Dinic(){ LL res=0,d; while(bfs()) { while(d=dfs(s,INF)) res+=d; } printf("%lld\n",res);}int main(){ memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); n=read(),m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); LL w=read(); addedge1(u,v,w); addedge1(v,u,w); } s=1,t=2*n; for(int i=1;i<=n;i++) { int x=read(); if(i==1||i==n) { insert(i,i+n,INF); continue; } insert(i,i+n,x); } SPFA(); for(int u=1;u<=n;u++) { for(int i=0;i<G[u].size();i++) { int j=G[u][i]; int v=Edges1[j].to; if(dis[v]==dis[u]+Edges1[j].w) insert(u+n,v,INF); } } Dinic(); return 0;}
[BZOJ 3931][CQOI2015]网络吞吐量（SPFA+网络流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。