发现它的本质是求一个费用最小的路径覆盖
最小路径覆盖是网络流23题中的一个比较典型的模型
所以考虑相似的建边
因为每一个点要恰好经过一次，是一个有上下界的网络流，故拆点，星球\(i\)拆成\(A_i,B_i\)两个点，\(S->B_i , A_i -> T\)，原图中的边\((i,j)\)变为\(B_i -> A_j\)，费用不变。
接下来我们需要考虑费用的设置
首先\(S->B_i\)的边的费用显然是通过空间跳跃到达这个点需要的时间\(a_i\)。
但有一个问题：在上面以最小路径覆盖问题为模板建立出的模型中，点\(B_i\)的出度流对应的实际上只是一条路径上的一条边\((i,j)\)而并非一整条路径。这意味着一条路径上除了终点以外所有点的\(a_i\)在费用流中都被加了进来。
考虑怎么减掉这个额外出现的空间跳跃费用。不难想到将\(A_i -> T\)边的费用设置为\(-a_i\)。这样非起点非终点的所有点\(a_i\)的贡献就会变为\(0\)。但是在这种情况下终点\(a_i\)的贡献却又是\(-a_i\)。
发现问题在于\(S->B_i\)边没有流。那么加上\(B_i -> T\)、流量1费用0的边，这样\(S->B_i\)就会有\(1\)的流，终点的空间跳跃时间就会变为\(0\)，就能保证路径上所有点空间跳跃时间是正确的了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
#define INF 0x3f3f3f3f
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = 1;
c = getchar();
}
if(c == EOF)
exit(0);
while(isdigit(c)){
a = (a << 3) + (a << 1) + (c ^ '0');
c = getchar();
}
return f ? -a : a;
}
const int MAXN = 2e4 + 3 , MAXM = 1e5 + 3;
struct Edge{
int end , upEd , f , c;
}Ed[MAXM];
int head[MAXN] , cur[MAXN] , dep[MAXN] , dis[MAXN] , pre[MAXN] , flo[MAXN];
int N , M , S , T , cntEd = 1;
bool vis[MAXN];
queue < int > q;
inline void addEd(int a , int b , int c , int d = 0){
Ed[++cntEd].end = b;
Ed[cntEd].upEd = head[a];
Ed[cntEd].f = c;
Ed[cntEd].c = d;
head[a] = cntEd;
}
inline bool bfs(){
while(!q.empty())
q.pop();
q.push(S);
memset(dep , 0 , sizeof(dep));
dep[S] = 1;
while(!q.empty()){
int t = q.front();
q.pop();
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(Ed[i].f && !dep[Ed[i].end]){
dep[Ed[i].end] = dep[t] + 1;
if(Ed[i].end == T){
memcpy(cur , head , sizeof(head));
return 1;
}
q.push(Ed[i].end);
}
}
return 0;
}
inline int dfs(int x , int mF){
if(x == T)
return mF;
int sum = 0;
for(int &i = cur[x] ; i ; i = Ed[i].upEd)
if(Ed[i].f && dep[Ed[i].end] == dep[x] + 1){
int t = dfs(Ed[i].end , min(mF - sum , Ed[i].f));
if(t){
Ed[i].f -= t;
Ed[i ^ 1].f += t;
sum += t;
if(sum == mF)
break;
}
}
return sum;
}
int Dinic(){
int ans = 0;
while(bfs())
ans += dfs(S , INF);
return ans;
}
inline bool SPFA(){
memset(dis , 0x3f , sizeof(dis));
dis[S] = 0;
while(!q.empty())
q.pop();
q.push(S);
flo[S] = INF;
while(!q.empty()){
int t = q.front();
q.pop();
vis[t] = 0;
for(int i = head[t] ; i ; i = Ed[i].upEd)
if(Ed[i].f && dis[Ed[i].end] > dis[t] + Ed[i].c){
dis[Ed[i].end] = dis[t] + Ed[i].c;
flo[Ed[i].end] = min(Ed[i].f , flo[t]);
pre[Ed[i].end] = i;
if(!vis[Ed[i].end]){
vis[Ed[i].end] = 1;
q.push(Ed[i].end);
}
}
}
return dis[T] != dis[T + 1];
}
int EK(){
int ans = 0;
while(SPFA()){
int cur = T , sum = 0;
while(cur != S){
sum += Ed[pre[cur]].c;
Ed[pre[cur]].f -= flo[T];
Ed[pre[cur] ^ 1].f += flo[T];
cur = Ed[pre[cur] ^ 1].end;
}
ans += sum * flo[T];
}
return ans;
}
bool in[MAXN];
int nxt[MAXN];
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
N = read();
M = read();
T = 2 * N + 2;
for(int i = 1 ; i <= N ; ++i){
int a = read();
addEd(S , i + N , 1 , a);
addEd(i + N , S , 0 , -a);
addEd(i , T , 1 , -a);
addEd(T , i , 0 , a);
addEd(i + N , T - 1 , 1);
addEd(T - 1 , i + N , 0);
}
addEd(T - 1 , T , INF);
addEd(T , T - 1 , 0);
for(int i = 1 ; i <= M ; ++i){
int a = read() , b = read() , c = read();
if(a > b)
swap(a , b);
addEd(a + N , b , 1 , c);
addEd(b , a + N , 0 , -c);
}
cout << EK();
return 0;
}