BZOJ 1927 [Sdoi2010]星际竞速

题目大意

给你一个有向无环图，经过每个点要么花费$S_i$时间传送到，要么花费$V_j$时间从一个比它编号小的点抵达，求遍历所有点的最小时间。

这题好难啊……根本不会建图……

每个点要么花费$S_i$时间传送到，要么花费$V_j$时间从一个比它编号小的点抵达.

将每个点拆成两个点，从S向所有点的入点连边，容量1花费0,所有入点向它连接的点的出点连边，容量1花费边长，截止到现在到出点表示抵达这个点是由其他点抵达的；S向所有出点连边，容量1花费传送代价，表示传送到这个点。所有出点到T连边容量1花费0表示到过这个点。此时有最大流N，此时的最小费用就是最小时间，也就是最终答案。

我费用流统计的时候只记得正向边减流竟然忘了反向边加流……GG

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10000
#define M 100000
#define INF 1<<30
int n,m,S,T,ix,iy,iz,dis[N],pre[N],from[N],ans;
int to[M],nex[M],val[M],cost[M],head[N],tot=1;
queue<int>q;
bool SPFA()
{
	q.push(S);
	memset(dis,0x3f,sizeof dis);
	dis[S]=0;
	from[T]=-1;
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=head[tmp];i;i=nex[i]) if(val[i]&&dis[to[i]]>dis[tmp]+cost[i])
		{
			dis[to[i]]=dis[tmp]+cost[i];
			from[to[i]]=tmp;
			pre[to[i]]=i;
			q.push(to[i]);
		}
	}
	return ~from[T];
}
int calc()
{
	int tmp=INF,ret=0;
	for(int i=T;i!=S;i=from[i]) tmp=min(tmp,val[pre[i]]);
	for(int i=T;i!=S;i=from[i]) ret+=tmp*cost[pre[i]],val[pre[i]]-=tmp,val[pre[i]^1]+=tmp;
	return ret;
}
inline void AE(int tx,int ty,int ta,int tb)
{
	to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=ta,cost[tot]=tb;
	to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=0,cost[tot]=-tb;
}
int main()
{
	scanf("%d%d",&n,&m);
	T=(n<<1)+1;
	for(int i=1;i<=n;++i) scanf("%d",&ix),AE(S,i,1,0),AE(S,i+n,1,ix),AE(i+n,T,1,0);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&ix,&iy,&iz);
		if(ix>iy) swap(ix,iy);
		AE(ix,iy+n,1,iz);
	}
	while(SPFA()) ans+=calc();
	printf("%d\n",ans);
	return 0;
}