记录编号	158245	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]网络吞吐量	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.203 s
提交时间	2015-04-13 17:59:09	内存使用	23.26 MiB

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=2010,maxm=500010,inf=0x3f3f3f3f;
struct edge{
	int x,dis;
	bool operator < (const edge &a) const{
		return dis > a.dis;
	}
};
bool vis[maxn];
int n,m,S,T,p[maxn],dis[maxn];
int len,g[maxn],to1[maxm],next1[maxm],cost[maxm];
int tot=1,head[maxn],cap[maxm],to2[maxm],next2[maxm];
void add1(int x,int y,int w){
	to1[++len]=y,next1[len]=g[x],cost[len]=w,g[x]=len;
}
void add2(int x,int y,int v){
	to2[++tot]=y,next2[tot]=head[x],cap[tot]=v,head[x]=tot;
	to2[++tot]=x,next2[tot]=head[y],cap[tot]=0,head[y]=tot;
}
void in(int &x){
	int ch;
	while((ch=getchar())<48);x=ch-48;
	while((ch=getchar())>47) x=x*10+ch-48;
}
queue <int> q;
void Dijkstra(){
	priority_queue <edge> Q;
	for(int i=2;i<=n;i++) dis[i]=inf;
	Q.push((edge){1,0});
	for(int i=1;i<n;i++){
		int x=Q.top().x;
		Q.pop();
		while(vis[x]) x=Q.top().x,Q.pop();
		vis[x]=1;
		for(int i=g[x];i;i=next1[i])
			if(dis[to1[i]]>dis[x]+cost[i])
				dis[to1[i]]=dis[x]+cost[i],Q.push((edge){to1[i],dis[to1[i]]});
	}
	for(int i=1;i<n;i++) vis[i]=0;
	q.push(n),vis[n]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=g[x];i;i=next1[i])
			if(dis[x]==dis[to1[i]]+cost[i]){
				add2(to1[i]+n,x,inf);
				if(!vis[to1[i]]) vis[to1[i]]=1,q.push(to1[i]);
			}
	}
}
bool bfs(){
	memset(dis,0,sizeof dis);
	q.push(S),dis[S]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=next2[i])
			if(cap[i]&&!dis[to2[i]])
				dis[to2[i]]=dis[x]+1,q.push(to2[i]);
	}
	return dis[T];
}
int dfs(int x,int y){
	if(x==T||y==0) return y;
	int flow=0;
	for(int &i=p[x];i;i=next2[i]){
		if(!cap[i]||dis[to2[i]]!=dis[x]+1) continue;
		int f=dfs(to2[i],min(cap[i],y));
		flow+=f,y-=f;
		cap[i]-=f,cap[i^1]+=f;
		if(!y) break;
	} 
	return flow;
}
int dinic(){
	for(int j,i=1;i<=n;i++) in(j),add2(i,i+n,j);
	int maxflow=0;
	while(bfs()){
		for(int i=n*2;i;i--) p[i]=head[i];
		maxflow+=dfs(S,inf);
	}
	return maxflow;
}
main(){
	freopen("cqoi15_network.in","r",stdin);
	freopen("cqoi15_network.out","w",stdout);
	in(n),in(m),S=n+1,T=n;
	for(int u,v,c,i=1;i<=m;i++)
		in(u),in(v),in(c),add1(u,v,c),add1(v,u,c);
	Dijkstra();
	printf("%lld",dinic());
}