3931: [CQOI2015]网络吞吐量
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 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
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>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #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; } |
阿当的代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | #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 1000000000000000llusing 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);} |
评论 (0)
