题意：给定一张有向图，边均由编号较大的点连向编号较小的点，每个点都有一个权值a，表示可以从任意一个点转移到i点，花费a[i]的费用。求遍历每个点一次且仅一次的最小费用，起点终点任意，保证有解。

题解：拆点，费用流决定经过的点的顺序，由于瞬移到i的费用与之前经过的点无关，所以可以直接从S向每个点i连流量为1费用为a[i]的边。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define S 0#define T (2*N+1)#define INF 1061109567 const int MAXN=2000+6;const int MAXM=40000+6;struct Hash{ int u; Hash *Next; Hash(){} Hash(int _u,Hash *_Next):u(_u),Next(_Next){}}*Tab[MAXN],Mem[MAXM],*From[MAXN];struct Edge{ int u,v,c,w; Edge(){} Edge(int _u,int _v,int _c,int _w):u(_u),v(_v),c(_c),w(_w){}}e[MAXM];int N,M,cnt,d[MAXN];bool Flag[MAXN];deque
             
               q; void Insert(int u,int v,int c,int w){ Tab[u]=&(Mem[cnt]=Hash(cnt,Tab[u])),e[cnt++]=Edge(u,v,c,w); Tab[v]=&(Mem[cnt]=Hash(cnt,Tab[v])),e[cnt++]=Edge(v,u,0,-w);} bool SPFA(int s,int t){ memset(d,0X3F,sizeof(d)); d[s]=0,Flag[s]=1,q.push_back(s); int x; while(!q.empty()){ x=q.front(),q.pop_front(); for(Hash *p=Tab[x];p;p=p->Next) if(e[p->u].c && d[e[p->u].v]>d[x]+e[p->u].w){ d[e[p->u].v]=d[x]+e[p->u].w,From[e[p->u].v]=p; if(Flag[e[p->u].v]) continue; Flag[e[p->u].v]=1; if(!q.empty() && d[e[p->u].v]
              
               u].v); else q.push_back(e[p->u].v); } Flag[x]=0; } return d[t]
               
                u].u]) x=min(x,e[p->u].c); for(Hash *p=From[t];p;p=From[e[p->u].u]) e[p->u].c-=x,e[p->u^1].c+=x,Ret+=x*e[p->u].w; return Ret;} int MCMF(int s,int t){ int Ans=0; while(SPFA(s,t)) Ans+=Calc(s,t); return Ans;} int main(){ scanf("%d %d",&N,&M); for(int i=1,a;i<=N;i++){ scanf("%d",&a); Insert(S,N+i,1,a); } for(int i=1,u,v,w;i<=M;i++){ scanf("%d %d %d",&u,&v,&w); if(u>v) swap(u,v); Insert(u,N+v,1,w); } for(int i=1;i<=N;i++) Insert(N+i,T,1,0),Insert(S,i,1,0); cout << MCMF(S,T) << endl; return 0;}