bzoj3931【CQOI2015】网络吞吐量

3931: [CQOI2015]网络吞吐量

Time Limit: 10 Sec Memory Limit: 512 MB

Submit: 853 Solved: 381

[Submit][

id=3931" style="color:blue; text-decoration:none">Status][Discuss]

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

Source

最短路+最大流裸题

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define F(i,j,n) for(int i=j;i<=n;i++)

#define D(i,j,n) for(int i=j;i>=n;i--)

#define ll long long

#define pa pair<ll,int>

#define maxn 1100

#define maxm 400100

#define inf 1000000000000000ll

using namespace std;

int n,m,s,t,cnt=0;

int head[maxn],cur[maxn],x[100100],y[100100];

ll dis[maxn],c[maxn],z[100100];

ll ans=0;

bool inq[maxn],vst[maxn];

struct edge_type

{

	int to,next;

	ll v;

}e[maxm];

inline int read()

{

	int x=0,f=1;char ch=getchar();

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

	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

inline void add_edge(int x,int y,ll z1,ll z2)

{

	e[++cnt]=(edge_type){y,head[x],z1};head[x]=cnt;

	e[++cnt]=(edge_type){x,head[y],z2};head[y]=cnt;

}

inline void dijkstra()

{

	priority_queue<pa,vector<pa>,greater<pa> > q;

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

	dis[1]=0;

	q.push(make_pair(0,1));

	while (!q.empty())

	{

		int x=q.top().second;q.pop();

		while (!q.empty()&&vst[x]){x=q.top().second;q.pop();}

		if (vst[x]) break;

		vst[x]=true;

		for(int i=head[x];i;i=e[i].next)

		{

			int y=e[i].to;

			if (dis[y]==-1||dis[y]>dis[x]+e[i].v)

			{

				dis[y]=dis[x]+e[i].v;

				q.push(make_pair(dis[y],y));

			}

		}

	}

}

inline ll dfs(int x,ll f)

{

	ll tmp,sum=0;

	if (x==t) return f;

	for(int &i=cur[x];i;i=e[i].next)

	{

		int y=e[i].to;

		if (e[i].v&&dis[y]==dis[x]+1)

		{

			tmp=dfs(y,min(f-sum,e[i].v));

			e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;

			if (sum==f) return sum;

		}

	}

	if (!sum) dis[x]=-1;

	return sum;

}

inline bool bfs()

{

	queue<int> q;

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

	dis[s]=0;q.push(s);

	while (!q.empty())

	{

		int tmp=q.front();q.pop();

		if (tmp==t) return true;

		for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1)

		{

			dis[e[i].to]=dis[tmp]+1;

			q.push(e[i].to);

		}

	}

	return false;

}

inline void dinic()

{

	while (bfs())

	{

		F(i,1,t) cur[i]=head[i];

		ans+=dfs(s,inf);

	}

}

int main()

{

	n=read();m=read();

	F(i,1,m)

	{

		x[i]=read();y[i]=read();z[i]=read();

		add_edge(x[i],y[i],z[i],z[i]);

	}

	F(i,1,n) c[i]=read();

	c[1]=c[n]=inf;

	dijkstra();

	memset(head,0,sizeof(head));

	cnt=1;s=1;t=2*n;

	F(i,1,n) add_edge(i,i+n,c[i],0);

	F(i,1,m)

	{

		if (dis[y[i]]==dis[x[i]]+z[i]) add_edge(x[i]+n,y[i],inf,0);

		if (dis[x[i]]==dis[y[i]]+z[i]) add_edge(y[i]+n,x[i],inf,0);

	}

	dinic();

	printf("%lld\n",ans);

}

巴特西