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<<60 using 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 ",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; }