[SDOI2010]星际竞速——费用流

类似于最短路的网络流，而且还要保证每个点经过一次，拆点就比较方便了。

连边怎么连？要保证最大流是n（每个点经过一次）还要能从直接跳转

将每个点拆点。
源点向每个点的入点连一条容量为1费用为0的边。
源点向每个点的出点连一条容量为1费用为瞬移到该点所需时间的边。
每个点的出点向汇点连一条容量为1费用为0的边。
对于每条边(i,j)，从i点入点向j点出点连一条容量为1费用为航路所需时间的边。

就是，到了每个点，出点会标记到了这个点（连向T一条边的流量会流过去）

走从S到一个点x的入点边，相当于选择从这个点x走要一条边到达另一个点

走。。。。。。。出点边，相当于直接瞬移。

费用都是正的，所以每个点一定被经过恰好一次。

把这些流按一定顺序排序，走出来的一定就是一个合法的路径。

流到该点出点的某入点对应的星球，在之前的某一时刻一定由某种合法方式达到过，追溯到头一定是某个瞬移到的点（因为图中没有环），“追溯”的过程就是这一条路径。

#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;bool fl=false;
    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=1608;
const int M=15000+5;
const int inf=0x3f3f3f3f;
int n,m,s,t;
struct node{
    int nxt,to;
    int w,v;
}e[2*(N+M+N)];
int hd[N],cnt=1;
void add(int x,int y,int w,int v){
    e[++cnt].nxt=hd[x];
    e[cnt].to=y;
    e[cnt].w=w;
    e[cnt].v=v;
    hd[x]=cnt;
    
    e[++cnt].nxt=hd[y];
    e[cnt].to=x;
    e[cnt].w=0;
    e[cnt].v=-v;
    hd[y]=cnt;
}
int incf[N],dis[N];
int pre[N];
bool vis[N];
queue<int>q;
bool spfa(){
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof vis);
    memset(dis,inf,sizeof dis);
    dis[s]=0;
    incf[s]=inf;
    pre[s]=0;
    q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=0;
        for(reg i=hd[x];i;i=e[i].nxt){
            int y=e[i].to;
            if(e[i].w&&dis[y]>dis[x]+e[i].v){
                dis[y]=dis[x]+e[i].v;
                pre[y]=i;
                incf[y]=min(e[i].w,incf[x]);
                if(!vis[y]){
                    vis[y]=1;
                    q.push(y);
                }
            }    
        }
    }
    if(dis[t]==inf) return false;
    return true;
}
int ans,maxflow;
void upda(){
    int x=t;
    while(pre[x]){
        e[pre[x]].w-=incf[t];
        e[pre[x]^1].w+=incf[t];
        x=e[pre[x]^1].to;
    }
    ans+=incf[t]*dis[t];
    maxflow+=incf[t];
    //cout<<" ans "<<ans<<" "<<maxflow<<endl;
}
int main(){
    rd(n);rd(m);
    s=0,t=2*n+1;
    int x;
    for(reg i=1;i<=n;++i){
        rd(x);
        add(s,i+n,1,x);
        add(i+n,t,1,0);
        add(s,i,1,0);
    }
    int y,z;
    for(reg i=1;i<=m;++i){
        rd(x);rd(y);rd(z);
        if(x>y) swap(x,y);
        add(x,y+n,1,z);
    }
    while(spfa()) upda();
    //cout<<" liu "<<maxflow<<endl;
    cout<<ans;
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2018/12/14 11:29:33
*/