【BZOJ3931】【CQOI2015】网络吞吐量（最短路，网络流）

题面

跑到BZOJ上去看把

题解

网络流模板题？？？

SPFA跑出最短路，重新建边后

直接Dinic就行了

大火题嗷。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<vector>

using namespace std;

#define INF 1e18

#define MAX 1000

#define MAXL 100000

#define ll long long

#define int ll

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Line

{

	int v,next,w;

}e[MAXL],E[MAXL];

int h[MAX],cnt=1;

int H[MAX],Cnt=1;

int n,m,level[MAX];

ll dis[MAX],C[MAX];

ll FB[MAXL];

ll G[MAX][MAX];

bool vis[MAX];

inline void Add(int u,int v,int w)

{

	e[cnt]=(Line){v,h[u],w};

	h[u]=cnt++;

}

inline void reAdd(int u,int v,int w)

{

	E[Cnt]=(Line){v,H[u],w};FB[Cnt]=Cnt+1;

	H[u]=Cnt++;

	E[Cnt]=(Line){u,H[v],0};FB[Cnt]=Cnt-1;

	H[v]=Cnt++;

}

void spfa()

{

	queue<int> Q;

	for(int i=1;i<=n;++i)dis[i]=INF,vis[i]=false;

	vis[1]=true;dis[1]=0;

	Q.push(1);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=h[u];i;i=e[i].next)

		{

			int v=e[i].v;

			ll w=e[i].w+dis[u];

			if(dis[v]>w)

			{

				dis[v]=w;

				if(!vis[v]){vis[v]=true;Q.push(v);}

			}

		}

		vis[u]=false;

	}

}

void Rebuild()

{

	C[n]=INF;C[1]=INF;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			if(dis[i]+G[i][j]==dis[j]&&i!=j)

			reAdd(i,j,min(C[j],C[i]));

}

bool BFS()

{

	queue<int> Q;while(!Q.empty())Q.pop();

	for(int i=1;i<=n;++i)level[i]=0;

	level[1]=1;Q.push(1);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=H[u];i;i=E[i].next)

		{

			int v=E[i].v;

			if(E[i].w&&!level[v])

			{

				level[v]=level[u]+1;

				Q.push(v);

			}

		}

	}

	return level[n];

}

ll DFS(int u,ll ff)

{

	if(!ff||u==n)return ff;

	ll re=0;

	for(int i=H[u];i;i=E[i].next)

	{

		int v=E[i].v;

		if(E[i].w&&level[u]+1==level[v])

		{

			ll gg=DFS(v,min(ff,E[i].w));

			re+=gg;ff-=gg;E[i].w-=gg;

			E[FB[i]].w+=gg;

		}

	}

	return re;

}

ll Dinic()

{

	ll re=0;

	while(BFS())re+=DFS(1,INF);

	return re;

}

#undef int

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)G[i][j]=INF;

	for(ll i=1;i<=m;++i)

	{

		ll u=read(),v=read(),w=read();

		Add(u,v,w);Add(v,u,w);

		G[u][v]=G[v][u]=min(G[u][v],w);

	}

	for(ll i=1;i<=n;++i)C[i]=read();

	spfa();

	Rebuild();

	printf("%lld\n",Dinic());

	return 0;

}