1
12
2016
0

【CQOI2015】【bsoj4235】【最短路径】【最大流】网络吞吐量

3931: [CQOI2015]网络吞吐量

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 853  Solved: 381
[Submit][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

70

HINT

 

 对于100%的数据,n≤500,m≤100000,d,c≤10^9

 

Source


堆优化Dijkstra找出最短路,最短路图上求最大流 

题中已经规定从1到n,则源点为1,汇点为n。

网络流经典模型:结点容量

每个结点都有一个允许通过的最大流量,称为结点容量

解:把每个原始结点u拆成u1和u2两个结点,(u1=u,u2=u+n,标号为了防止加边时混乱。)中间连一条有向弧,容量等于u的结点容量。原先到达u的弧改成到达u1;原先从u出发的弧改成从u2出发。

1、拆点后t<=2.注意重构图时点的标号

2、因为中间要拆点,把数据范围扩大为所给值原来的2倍——否则各种T、RE 

我的代码:#include<cstdio>

#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
#define pa pair<ll,int>
#define inf 100000000000000000ll
#define for2(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std;
const int M=200000,N=1000;
ll int m,n,s,t,val[N];
ll int tot,head[N],d1[N],d2[N],v[N],rec[N];
ll int cnt=1,h[N],dis[N],cur[N],maxflow;
struct edge{
	ll int from,go,next,w;
}e[M],ed[M];
inline void addedge1(int x,int y,ll z)
{
	e[++tot]=(edge){x,y,head[x],z};head[x]=tot;
}
inline void addedge2(int x,int y,ll z)
{
	ed[++cnt]=(edge){x,y,h[x],z};h[x]=cnt;
	ed[++cnt]=(edge){y,x,h[y],0};h[y]=cnt;
}
inline ll int read()
{
	ll 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;
}
void dijkstra1()
{
	priority_queue<pa,vector<pa>,greater<pa> >que;
	for(int i=1;i<=n;i++) d1[i]=inf;
	memset(v,0,sizeof(v));
	d1[s]=0;
	que.push(make_pair(0,s));
	while(!que.empty())
	{
		int x=que.top().second;
		que.pop();
		if(v[x]) continue;
		v[x]=1;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].go;
			if(d1[x]+e[i].w<d1[y])
			{
				d1[y]=d1[x]+e[i].w;
				que.push(make_pair(d1[y],y));
			}
		}
	}
}
void buildgraph()
{
	for2(i,1,n) addedge2(i*2-1,i*2,val[i]);
	for2(i,1,tot){
		int x=e[i].from,y=e[i].go;
		if(d1[x]+e[i].w==d1[y])
			addedge2(x*2,y*2-1,inf);
	}
}
bool bfs()
{
	queue<int> q;
    memset(dis,-1,sizeof(dis));
    q.push(s);dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=h[x];i;i=ed[i].next)
         if(ed[i].w&&dis[ed[i].go]==-1)
         {
            dis[ed[i].go]=dis[x]+1;q.push(ed[i].go);
         }
    }
    return dis[t]!=-1;
}
ll int dfs(int x,ll int f)
{
    if(x==t) return f;
    ll int tmp,used=0;
    for(int i=cur[x];i;i=ed[i].next)
     if(ed[i].w&&dis[ed[i].go]==dis[x]+1)
    {
        tmp=dfs(ed[i].go,min(ed[i].w,f-used));
        ed[i].w-=tmp;if(ed[i].w)cur[x]=i;
        ed[i^1].w+=tmp;used+=tmp;
        if(used==f)return f;
    }
    if(!used) dis[x]=-1;
    return used;
}
void dinic()
{
	maxflow=0;
	while(bfs()){
		for2(i,s,t)cur[i]=h[i];
		maxflow+=dfs(s,inf);
	}
}
int main()
{
	freopen("network.in","r",stdin);
	freopen("network.out","w",stdout);
	n=read();m=read();
	ll int x,y,z;
	for2(i,1,m){
		x=read();y=read();z=read();
		addedge1(x,y,z);
		addedge1(y,x,z);
	}
	s=1;t=n;
	dijkstra1();
	for2(i,1,n) val[i]=read();val[s]=val[t]=inf;
	buildgraph();
	s=1;t=2*n;
	dinic();
	printf("%lld\n",maxflow);
	return 0; 
}

阿当的代码:

#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);
}
Category: 网络流 | Tags: | Read Count: 455

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com