将最短路图找出来，跑maxflow即可。有注意到数据范围。然后输出的时候%dWA了三次QAQ。。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,n) for(int i=1;i<=n;i++)#define ll long long#define clr(x,c) memset(x,c,sizeof(x))#define qwq(x) for(Edge *o=h[x];o;o=o->next)#define QWQ(x) for(edge *o=head[x];o;o=o->next)#define REP(i,s,t) for(int i=s;i<=t;i++)int read(){	int x=0;char c=getchar();bool f=true;	while(!isdigit(c)) {		if(c=='-') f=false; c=getchar();	}	while(isdigit(c)) x=x*10+c-'0',c=getchar();	return f?x:-x;} const int nmax=1005;const int maxn=400005;const ll inf=(ll)1<<60;struct edge{	int to;ll cap;edge *next,*rev;};edge edges[maxn],*pt=edges,*head[nmax],*p[nmax],*cur[nmax];void add(int u,int v,ll w){	pt->to=v;pt->cap=w;pt->next=head[u];head[u]=pt++;}void adde(int u,int v,ll w){	add(u,v,w);add(v,u,0);head[u]->rev=head[v];head[v]->rev=head[u];}struct Edge{	int to;ll dist;Edge *next;};Edge Edges[maxn],*e=Edges,*h[nmax];void addedge(int u,int v,ll w){	e->to=v;e->dist=w;e->next=h[u];h[u]=e++;}int cnt[nmax],H[nmax];bool inq[nmax];ll d[nmax];void spfa(int s,int t,int n){	rep(i,n) d[i]=inf;	clr(inq,0);inq[s]=1;d[s]=0;	queue
          
           q;q.push(s); while(!q.empty()){ int x=q.front();q.pop();inq[x]=0; qwq(x) if(d[o->to]>d[x]+o->dist){ d[o->to]=d[x]+o->dist; if(!inq[o->to]) q.push(o->to),inq[o->to]=1; } }}ll maxflow(int s,int t,int n){ clr(cnt,0);cnt[0]=n;clr(H,0); ll flow=0,a=inf;int x=s;edge *e; while(H[s]
           
            next) if(e->cap>0&&H[x]==H[e->to]+1) break; if(e){ p[e->to]=cur[x]=e;a=min(a,e->cap);x=e->to; if(x==t){ while(x!=s) p[x]->cap-=a,p[x]->rev->cap+=a,x=p[x]->rev->to; flow+=a,a=inf; } }else{ if(!--cnt[H[x]]) break; H[x]=n; for(e=head[x];e;e=e->next) if(e->cap>0&&H[x]>H[e->to]+1) H[x]=H[e->to]+1,cur[x]=e; cnt[H[x]]++; if(x!=s) x=p[x]->rev->to; } } return flow;}int main(){ int n=read(),m=read(),u,v;ll w; rep(i,m) u=read(),v=read(),w=read(),addedge(u,v,w),addedge(v,u,w); /*rep(i,n){ qwq(i) printf("%d ",o->to);printf("\n"); }*/ spfa(1,n,n); //rep(i,n) printf("%d ",d[i]); rep(i,n) qwq(i) if(d[o->to]==d[i]+o->dist) if(i==1||i==n) adde(i,o->to,inf); else adde(i+n,o->to,inf); /*rep(i,n){ QWQ(i) printf("%d ",o->to);printf("\n"); }*/ rep(i,n) { w=read(); if(i!=1&&i!=n) adde(i,i+n,w); } printf("%lld\n",maxflow(1,n,n+n-2)); return 0;}
           
          
         
        
       
      
     

　

3931: [CQOI2015]网络吞吐量

Time Limit: 10 Sec  Memory Limit: 512 MB

Submit: 1328  Solved: 549

[][][]

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

 

[ ][ ][ ]