[CQOI2015]网络吞吐量https://www.luogu.org/problemnew/show/P3171
题目描述
路由是指通过计算机网络把信息从源地址传输到目的地址的活动，也是计算机网络设计中的重点和难点。网络中实现路由转发的硬件设备称为路由器。为了使数据包最快的到达目的地，路由器需要选择最优的路径转发数据包。例如在常用的路由算法OSPF(开放式最短路径优先)中，路由器会使用经典的Dijkstra算法计算最短路径，然后尽量沿最短路径转发数据包。现在，若已知一个计算机网络中各路由器间的连接情况，以及各个路由器的最大吞吐量（即每秒能转发的数据包数量），假设所有数据包一定沿最短路径转发，试计算从路由器1到路由器n的网络的最大吞吐量。计算中忽略转发及传输的时间开销，不考虑链路的带宽限制，即认为数据包可以瞬间通过网络。路由器1到路由器n作为起点和终点，自身的吞吐量不用考虑，网络上也不存在将1和n直接相连的链路。
输入格式：
输入文件第一行包含两个空格分开的正整数n和m，分别表示路由器数量和链路的数量。网络中的路由器使用1到n编号。接下来m行，每行包含三个空格分开的正整数a、b和d，表示从路由器a到路由器b存在一条距离为d的双向链路。 接下来n行，每行包含一个正整数c，分别给出每一个路由器的吞吐量。
输出格式：
输出一个整数，为题目所求吞吐量。
输入样例：
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
输出样例：
70
说明
对于100%的数据，n<=500，m<=100000，d,c<=10^9
正解思路:最短路+最大流
1.跑出最短路[可能有多条] (貌似DJ比Spfa快??)
2.将所有最短路上的边连到网络流的图上[将u+n节点与v节点连边,容量为inf]
3.拆点,限制流量[将i节点与i+n节点连边,容量为节点的吞吐量] (1节点和n节点连边时的容量置为inf)
4.跑最大流
实现时的难点:
对于步骤2
一开始写的dfs,不好写,可以过样例,但是会TLE和RE.
后来在网上看到一种方法:
以n节点为起点再跑一遍最短路,
枚举每条边,
若有:
dist[1][i]+w(i,j)+dist[j][n]==dist[1][n]
则该边一定在最短路上.
实现时的坑点:
inf需要很大,1e9是不够的
#define RG register
#define LL long long
#define inf (1LL<<60)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int N=505,NN=2000,M=1e5+5;
inline LL read()
{
RG LL x=0,w=1;RG char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
inline LL minn(LL a,LL b){return a<b?a:b;}
LL n,m,S,T,Ans,cnt; //源点S为1,汇点T为2*n
LL last[N],dist[2][N]; //last[]是跑最短路建图时所用的邻接表的末指针数组,dist[0][i]表示节点i到起点1的最短路长度,dist[1][i]表示节点i到n节点的最短路长度
LL a[M],b[M],c[M]; //存储边的信息
LL dep[NN],cur[NN],head[NN]; //dep[]为dfs深度,cur[]当前弧,head[]是跑最大流建图时所用的邻接表的末指针数组
bool used[N];
struct edge{
LL to,next,w;
}e[2*M],ee[3*M];//两个图
inline void insert(LL u,LL v,LL w) //连边[最短路] (双向边)
{
e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
e[++cnt]=(edge){u,last[v],w};last[v]=cnt;
}
inline void link(LL u,LL v,LL w) //连边[最大流] (单向边)
{
ee[++cnt]=(edge){v,head[u],w};head[u]=cnt;
ee[++cnt]=(edge){u,head[v],0};head[v]=cnt;
}
queue<LL> Q;
inline void Dijkstra(LL ss,LL op)
{
memset(used,0,sizeof(used));
for(LL i=1;i<=n;i++)dist[op][i]=inf;
dist[op][ss]=0;
while(1)
{
LL now=-1;
for(LL i=1;i<=n;i++)if(!used[i]&&(now==-1||dist[op][now]>dist[op][i]))now=i;
if(now==-1)break;
used[now]=1;
for(LL i=last[now];i;i=e[i].next)
{
LL v=e[i].to;
dist[op][v]=min(dist[op][v],dist[op][now]+e[i].w);
}
}
}
inline bool bfs()
{
while(!Q.empty())Q.pop();
memset(dep,0,sizeof(dep));
dep[S]=1;
Q.push(S);
while(!Q.empty())
{
LL now=Q.front();Q.pop();
for(LL i=head[now];i;i=ee[i].next)
{
LL v=ee[i].to;
if(ee[i].w>0&&!dep[v])
{
dep[v]=dep[now]+1;
Q.push(v);
}
}
}
return dep[T]!=0;
}
LL dfs(LL now,LL flow)
{
if(now==T)return flow;
for(LL& i=cur[now];i;i=ee[i].next)
{
LL v=ee[i].to;
if(dep[v]==dep[now]+1&&ee[i].w!=0)
{
LL di=dfs(v,minn(flow,ee[i].w));
if(di>0){ee[i].w-=di;ee[i^1].w+=di;return di;}
}
}
return 0;
}
int main()
{
n=read();
m=read();
for(LL i=1;i<=m;i++)
{
a[i]=read(),b[i]=read(),c[i]=read();
insert(a[i],b[i],c[i]);
}
Dijkstra(1,0);
Dijkstra(n,1);
cnt=1;
for(LL i=1;i<=m;i++) //连边
{
if(dist[0][a[i]]+c[i]+dist[1][b[i]]==dist[0][n])link(a[i]+n,b[i],inf);
if(dist[0][b[i]]+c[i]+dist[1][a[i]]==dist[0][n])link(b[i]+n,a[i],inf);
}
for(LL i=1;i<=n;i++) //拆点
{
LL x=read();
if(i==1||i==n)link(i,i+n,inf);
else link(i,i+n,x);
}
S=1;T=2*n;
while(bfs())
{
for(LL i=S;i<=T;i++)cur[i]=head[i];
while(LL d=dfs(S,inf))Ans+=d;
}
printf("%lld
",Ans);
return 0;
}