bzoj3931【CQOI2015】網絡吞吐量

 

3931: [CQOI2015]網絡吞吐量

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

70

HINT

 

對於100%的數據，n≤500，m≤100000，d,c≤10^9

 

Source

最短路+最大流裸題

#include
#include
#include
#include
#include
#include
#include
#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
#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,greater > 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 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);
}