记录编号	158963	评测结果	AAAAAAAAAA
题目名称	[CQOI2015]网络吞吐量	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.824 s
提交时间	2015-04-18 18:34:57	内存使用	5.61 MiB

#include<cstdio>
#include<iostream>
#include<deque>
using namespace std;
typedef long long LL;
int n,m,e[510]={0},poi[510]={0},h[1010]={0},r[1010]={0},f[1010][1010];
LL sw[510]={0},ans=0,maxn=0x3f3f3f3f;
class miku
{
public:
	int to;
	int lo;
};
deque<miku> p[501];
deque<int> s,st[1010];
deque<LL> liu[1010];
int check()
{
	for(int i=1;i<=2*n;i++)
		{
			cout<<i<<" "<<r[i]<<endl;
			
			cout<<endl;
		}
	return 0;
}
int in(int i,int j,int k)
{
	miku x;
	x.to=j;
	x.lo=k;
	p[i].push_back(x);
	return 0;
}
int spfa()
{
	deque<int> q;
	int iq[501]={0},rq[501]={0};
	q.push_back(1);
	iq[1]=1;
	sw[1]=0;
	rq[1]++;
	while(!q.empty())
	{
		int x=q.front();
		q.pop_front();
		iq[x]=0;
		for(int j=0;j<p[x].size();j++)
		{
			miku u=p[x][j];
			if(sw[x]+u.lo<sw[u.to])
			{
				sw[u.to]=sw[x]+u.lo;
				if(iq[u.to]==0)
				{
					iq[u.to]=1;
					q.push_back(u.to);
					rq[u.to]++;
				}
			}
		}
	}
	return 0;
}
int bfs()
{
	while(!s.empty())
	{
		int x=s.front();
		s.pop_front();
		for(int i=0;i<p[x].size();i++)
	    {
		miku w=p[x][i];
		if(sw[x]+w.lo==sw[w.to])
		{
			if(w.to!=n)
			{
				st[x].push_back(w.to+n);liu[x].push_back(maxn);
				st[w.to+n].push_back(x);liu[w.to+n].push_back(0);
				st[w.to+n].push_back(w.to);liu[w.to+n].push_back(e[w.to]);
				st[w.to].push_back(w.to+n);liu[w.to].push_back(0);
			}
			else
			{
				st[x].push_back(n+n);liu[x].push_back(maxn);
				st[n+n].push_back(x);liu[x].push_back(0);
			}
			if(poi[w.to]==0)
			{
				poi[w.to]=1;
				s.push_back(w.to);
			}
		}
		}
	}
	return 0;
}
int set()
{
	h[1]=2*n-2;
	for(int i=0;i<st[1].size();i++)
	{
		int x=st[1][i];
			f[1][x]=liu[1][i];
			f[x][1]=-1*liu[1][i];
			r[x]=liu[1][i];
			r[1]-=liu[1][i];
			//cout<<<<" "<<liu[1][i]<<endl;
	}
	return 0;
}
int push(int i,int j)
{
	int c,d;
	c=liu[i][j]-f[i][st[i][j]];
	if(c>0)
	{
		int x=st[i][j];
		d=min(r[i],c);
		f[i][x]+=d;
		f[x][i]=-1*f[i][x];
		r[i]-=d;
		r[x]+=d;
	}
	return 0;
}
int mf()
{
	set();
	int mi,flag=0;
	while(flag==0)
	{
		flag=1;
		//if(r[n*2]!=0)
			//return 0;
		//check();
		for(int i=2;i<n*2;i++)
		{
			if(r[i]>0)
			{
				mi=maxn;
				flag=0;
				for(int j=0;j<st[i].size();j++)
				{
					int x=st[i][j];
					if(liu[i][j]-f[i][x]>0)
					{
						if(h[x]==h[i]-1)
						{
							push(i,j);
							goto NEXT;
						}
					}
					if(h[x]<mi) mi=h[i];
				}
				h[i]=mi+1;
			}
			NEXT:;
		}
		
	}
	return 0;
}
int main()
{
	freopen("cqoi15_network.in","r",stdin);
	freopen("cqoi15_network.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		in(a,b,c);
		in(b,a,c);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&e[i]);
		sw[i]=0x3f3f3f3f;
	}
	if(spfa()==0)
	{
		s.push_back(1);
		poi[1]=1;
		bfs();
		mf();
		for(int i=1;i<=n*2;i++)
		{
			if(i==2*n) continue;
			ans+=f[i][n*2];
		}
	}
	cout<<ans;
	//cout<<st[2].size();
	return 0;
}