[文章目录]
Description
路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1和n直接相连的链路。
感觉题意杀啊。题意看懂了基本没问题。
就是要求一个最短路上的最大流。求出来单源最短路然后对于边的两端点的路径长度之差刚好为边权的边进行加边，然后对于每个点限流。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m,s,t;
int head1[510],to1[201000],nxt1[201000],cnt1;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll f1[201000],ans;
void add1(int x,int y,ll z)
{
to1[++cnt1]=y;
nxt1[cnt1]=head1[x];
head1[x]=cnt1;
f1[cnt1]=z;
}
ll dis1[510];
bool v[510];
queue<int>q;
void spfa()
{
memset(dis1,0x3f,sizeof(dis1));
dis1[1]=0; v[1]=1; q.push(1); int x,y;
while(!q.empty())
{
x=q.front(); q.pop(); v[x]=0;
for(int i=head1[x];i;i=nxt1[i])
if(dis1[y=to1[i]]>dis1[x]+f1[i])
{
dis1[y]=dis1[x]+f1[i];
if(!v[y]) q.push(y),v[y]=1;
}
}
}
int head[1500],to[501000],nxt[501000],cnt=1;
ll f[501000];
void add(int x,int y,ll z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
ll dis[1500];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
ll dinic(int x,ll flow)
{
if(x==t) return flow;
ll xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,x,y; ll z;
for(i=1;i<=m;++i)
{
scanf("%d%d%lld",&x,&y,&z);
add1(x,y,z); add1(y,x,z);
}
spfa();
for(i=1;i<=n;++i)
{
scanf("%lld",&z); if(i==1||i==n) z=inf;
add(i,i+n,z);
for(j=head1[i];j;j=nxt1[j])
if(dis1[to1[j]]==dis1[i]+f1[j])
add(i+n,to1[j],inf);
}
s=1+n,t=n;
while(bfs()) ans+=dinic(s,1<<30);
printf("%lld\n",ans);
return 0;
}