Submit: 1762 Solved: 728
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
图论 最短路 网络流
题面即题意。
求出最短路，在最短路的边上跑最大流即可。
注意数据范围！刚开始INF设成0x3f3f3f3f秒WA，一看数据，第一个点的答案都比这个大
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 #define LL long long 10 using namespace std; 11 const LL INF=0x3f3f3f3f3f3f; 12 const int mxn=200010; 13 int read(){ 14 int x=0,f=1;char ch=getchar(); 15 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 16 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 17 return x*f; 18 } 19 struct EG{ 20 int x,y,d; 21 }eg[mxn]; 22 int c[mxn]; 23 struct edge{ 24 int v,nxt; 25 LL f; 26 }e[mxn<<1]; 27 int hd[mxn],mct=0; 28 void add_edge(int u,int v,LL f){ 29 e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;e[mct].f=f;return; 30 } 31 void insert(int u,int v,LL c){ 32 add_edge(u,v,c);add_edge(v,u,0);return; 33 } 34 // 35 LL dis[601],dis2[601]; 36 struct node{ 37 int v; 38 LL dis; 39 bool operator < (node b)const{return dis>b.dis;} 40 }; 41 priority_queue<node>st; 42 void Dij(int s,int t){ 43 memset(dis,0x3f,sizeof dis); 44 dis[s]=0; 45 st.push((node){s,0}); 46 while(!st.empty()){ 47 node tmp=st.top(); 48 if(tmp.dis>dis[tmp.v]){st.pop();continue;} 49 int u=tmp.v;st.pop(); 50 for(int i=hd[u],v;i;i=e[i].nxt){ 51 v=e[i].v; 52 if(dis[v]>dis[u]+e[i].f){ 53 dis[v]=dis[u]+e[i].f; 54 st.push((node){v,dis[v]}); 55 } 56 } 57 } 58 return; 59 } 60 int n,m,S,T; 61 void Build(){ 62 Dij(1,n); 63 LL tot=dis[n]; 64 memcpy(dis2,dis,sizeof dis); 65 while(!st.empty())st.pop(); 66 Dij(n,1); 67 mct=1; 68 memset(hd,0,sizeof hd); 69 insert(1,1+n,INF); 70 S=1;T=n; 71 for(int i=2;i<=n;i++)insert(i,i+n,c[i]); 72 for(int i=1;i<=m;i++){ 73 int u=eg[i].x,v=eg[i].y; 74 if(dis[u]<dis[v])swap(u,v); 75 if(dis2[u]+dis[v]+eg[i].d==tot){ 76 insert(u+n,v,INF); 77 insert(v+n,u,INF); 78 } 79 } 80 return; 81 } 82 // 83 int d[1200]; 84 queue<int>q; 85 bool BFS(){ 86 memset(d,0,sizeof d); 87 d[S]=1; 88 q.push(S); 89 while(!q.empty()){ 90 int u=q.front();q.pop(); 91 for(int i=hd[u],v;i;i=e[i].nxt){ 92 v=e[i].v; 93 if(!d[v] && e[i].f){ 94 d[v]=d[u]+1; 95 q.push(v); 96 } 97 } 98 } 99 return d[T]; 100 } 101 LL DFS(int u,LL lim){ 102 if(u==T)return lim; 103 LL f=0,tmp; 104 for(int i=hd[u],v;i;i=e[i].nxt){ 105 v=e[i].v; 106 if(e[i].f && d[v]==d[u]+1 && (tmp=DFS(v,min(e[i].f,lim)))){ 107 e[i].f-=tmp; 108 e[i^1].f+=tmp; 109 lim-=tmp; 110 f+=tmp; 111 if(!lim)return f; 112 } 113 } 114 d[u]=0; 115 return f; 116 } 117 LL Dinic(){ 118 LL res=0; 119 while(BFS()){res+=DFS(S,INF);} 120 return res; 121 } 122 int main(){ 123 int i,j,a,b,d; 124 n=read();m=read(); 125 for(i=1;i<=m;i++){ 126 eg[i].x=read(); 127 eg[i].y=read(); 128 eg[i].d=read(); 129 add_edge(eg[i].x,eg[i].y,eg[i].d); 130 add_edge(eg[i].y,eg[i].x,eg[i].d); 131 } 132 for(i=1;i<=n;i++)c[i]=read(); 133 Build(); 134 LL ans=Dinic(); 135 printf("%lld ",ans); 136 return 0; 137 }