1927: [Sdoi2010]星际竞速

题意：一个带权DAG，每个点恰好经过一次，每个点有曲速移动到他的代价，求最小花费

---

不动脑子直接上上下界费用流过了...

s到点连边边权为曲速的代价，一个曲速移动等价于走到t再从s重新开始



搜了下题解发现全是普通费用流...

源向i+n连容量1，费用为能力爆发的费用

源向i连容量1，费用为0

i+n向汇连容量1，费用0

如果有边x<y，连x到y+n容量为1，费用为时间

和最小路径覆盖很像，只是连到i+n有权值

---

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define fir first

#define sec second

typedef long long ll;

const int N=2005, M=1e5+5, INF=1e9;

inline ll read(){

    char c=getchar();ll x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, m, s, t, tot, extra[N], x, val, warp;

struct edge{int v, c, f, w, ne, lower;}e[M];

int cnt=1, h[N];

inline void ins(int u, int v, int c, int w=0, int lower=0) {

	e[++cnt] = (edge){v, c, 0, w, h[u], lower}; h[u]=cnt;

	e[++cnt] = (edge){u, 0, 0, -w, h[v], lower}; h[v]=cnt;

}

int q[N], head, tail, d[N], inq[N];

pair<int, int> pre[N];

inline void lop(int &x) {if(x==N) x=1;}

bool spfa(int s, int t) {

	memset(inq, 0, sizeof(inq));

	memset(d, 0x3f, sizeof(d));

	head=tail=1;

	q[tail++]=s; d[s]=0; inq[s]=1;

	pre[t].fir = -1;

	while(head!=tail) {

		int u=q[head++]; inq[u]=0; lop(head);

		for(int i=h[u];i;i=e[i].ne) {

			int v=e[i].v;

			if(e[i].c > e[i].f && d[v]>d[u]+e[i].w) {

				d[v]=d[u]+e[i].w;

				pre[v]=make_pair(u, i);

				if(!inq[v]) q[tail++]=v, inq[v]=1, lop(tail);

			}

		}

	}

	return pre[t].fir != -1;

}

int ek(int s, int t) {

	int flow=0, cost=0, x;

	while(spfa(s, t)) {

		int f=INF;

		for(int i=t; i!=s; i=pre[i].fir) x=pre[i].sec, f=min(f, e[x].c - e[x].f);

		flow+=f; cost+=d[t]*f;

		for(int i=t; i!=s; i=pre[i].fir) x=pre[i].sec, e[x].f+=f, e[x^1].f-=f;

	}

	return cost;

}

int main() {

	//freopen("in","r",stdin);

	freopen("starrace.in","r",stdin);

	freopen("starrace.out","w",stdout);

	n=read(); m=read(); s=0; t=n+n+1;

	for(int i=1; i<=n; i++)

		warp=read(), ins(s, i, 1, warp), ins(i, i+n, 0, 0, 1), extra[i]--, extra[i+n]++, ins(i+n, t, 1);

	for(int i=1; i<=m; i++) {

		int u=read(), v=read(), val=read();

		if(u>v) swap(u, v);

		ins(u+n, v, 1, val);

	}

	int ss=t+1, tt=t+2, sum=0; tot=tt;

	for(int i=s; i<=t; i++) {

		if(extra[i]>0) ins(ss, i, extra[i]), sum+=extra[i];

		if(extra[i]<0) ins(i, tt, -extra[i]);

	}

	ins(t, s, INF);

	int ans=ek(ss, tt);

	printf("%d",ans);

}