记录编号	420943	评测结果	AAAAAAAA
题目名称	[SDOI 2010] 星际竞速	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.482 s
提交时间	2017-07-05 20:34:13	内存使用	39.41 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
struct edge{int f,t,g,l;}w[N];
int n,m,a[N],s,t,S,T,head[N],next[N];
void add(int f,int t,int g,int l){
	static int cnt=1;
	//printf("%d->%d g=%d l=%d\n",f,t,g,l);
	w[++cnt]=(edge){f,t,g,l};
	next[cnt]=head[f];
	head[f]=cnt;
	w[++cnt]=(edge){t,f,0,-l};
	next[cnt]=head[t];
	head[t]=cnt;
}
int dis[N],flow[N],from[N];
queue<int> Q;
bool inq[N];
long long ans;
bool spfa(){
	for (int i=s;i<=t;i++) dis[i]=2e9;
	dis[s]=0;flow[s]=1e9;Q.push(s);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		inq[v]=0;
		for (int i=head[v];i;i=next[i])
		if (w[i].g&&dis[w[i].t]>dis[v]+w[i].l){
			int u=w[i].t;
			dis[u]=dis[v]+w[i].l;
			flow[u]=min(flow[v],w[i].g);
			from[u]=i;
			if (!inq[u]) inq[u]=1,Q.push(u);
		}
	}
	if (dis[t]==2e9) return 0;
	int df=flow[t];ans+=1ll*dis[t]*df;
	for (int i=from[t];i;i=from[w[i].f]) w[i].g-=df,w[i^1].g+=df;
	return 1;
}
//i connect input edge, i+n connect output edge.
int main()
{
	freopen("starrace.in","r",stdin);
	freopen("starrace.out","w",stdout);
	scanf("%d%d",&n,&m);
	s=0;t=n*2+1;
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		add(s,i,1e9,a[i]);
		add(i,t,1,0);
		add(s,i+n,1,0);
	}
	for (int i=1;i<=m;i++){
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		if (u>v) swap(u,v);
		add(u+n,v,1e9,l);
	}
	while (spfa());
	printf("%lld\n",ans);
	return 0;
}