记录编号	87902	评测结果	AAAAAAAA
题目名称	[SDOI 2010] 星际竞速	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.303 s
提交时间	2014-02-11 19:50:34	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
using namespace std;
const int SIZEN=1210,INF=0x7fffffff/2;
class EDGE{
public:
	int from,to,cap,flow,cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];//邻接表
int N;//范围是从0到N
void addedge(int from,int to,int cap,int cost){
	edges.push_back((EDGE){from,to,cap,0,cost});
	edges.push_back((EDGE){to,from,0,0,-cost});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int anscost=0;
bool SPFA(int S,int T){
	queue<int> Q;
	bool inq[SIZEN]={0};
	int f[SIZEN]={0};
	int father[SIZEN]={0};
	int i,x;
	for(i=0;i<=N;i++) f[i]=INF;
	f[S]=0,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		x=Q.front();inq[x]=false;Q.pop();
		for(i=0;i<c[x].size();i++){
			EDGE& e=edges[c[x][i]];
			if(e.cap<=e.flow) continue;
			if(f[x]+e.cost<f[e.to]){
				f[e.to]=f[x]+e.cost;
				father[e.to]=c[x][i];
				if(!inq[e.to]){
					inq[e.to]=true;
					Q.push(e.to);
				}
			}
		}
	}
	if(f[T]==INF) return false;
	int minf=INF;
	x=T;
	while(x!=S){
		EDGE& e=edges[father[x]];
		minf=min(minf,e.cap-e.flow);
		x=e.from;
	}
	anscost+=minf*f[T];
	x=T;
	int now;
	while(x!=S){
		now=father[x];
		edges[now].flow+=minf;
		edges[now^1].flow-=minf;
		x=edges[now].from;
	}
	return true;
}
void MCMF(int S,int T){
	while(SPFA(S,T));
	printf("%d\n",anscost);
}
int S,T;
void read(void){
	int n,m,a,u,v,w;
	scanf("%d%d",&n,&m);
	S=0,T=2*n+1;
	N=T;
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		addedge(S,i+n,1,a);
		addedge(i+n,T,1,0);
		addedge(S,i,1,0);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		if(u>v) swap(u,v);
		addedge(u,v+n,1,w);
	}
}
int main(){
	freopen("starrace.in","r",stdin);
	freopen("starrace.out","w",stdout);
	read();
	MCMF(S,T);
	return 0;
}