费用流。
因为有能力爆发这种鬼东西。。每次能力爆发就相当于重新开始一条路径...除此以外就和一般的题一样了。。
拆点，每个点从出点往能到达的入点连流量正无穷，费用为航行时间的边。
每个点从入点往出点连一条流量为1，费用为0的边限制。
S往入点，出点往T连流量为1，费用为0的边。
S往出点连流量为1，费用为能力爆发所需时间的边。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int maxn=1623,inf=1002333333; 7 struct zs{int too,pre,dis,flow;}e[42333];int tot,last[maxn]; 8 int dis[maxn],dl[200233]; 9 bool u[maxn],ins[maxn]; 10 int i,j,k,n,m,s,t,ans; 11 12 int ra;char rx; 13 inline int read(){ 14 rx=getchar(),ra=0; 15 while(rx<'0'||rx>'9')rx=getchar(); 16 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 17 } 18 19 inline bool spfa(){ 20 memset(dis,60,(t+1)<<2);//printf(" %d ",dis[0]);return 0; 21 int l=0,r=1,i,now;dl[1]=s,dis[s]=0; 22 while(l<r) 23 for(i=last[now=dl[++l]],u[now]=0;i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]>dis[now]+e[i].dis){ 24 dis[e[i].too]=dis[now]+e[i].dis; 25 if(!u[e[i].too])u[e[i].too]=1,dl[++r]=e[i].too; 26 } 27 return dis[t]<inf; 28 } 29 inline int min(int a,int b){return a<b?a:b;} 30 int dfs(int x,int mx){ 31 if(x==t)return mx; 32 int i,used=0,w;ins[x]=1; 33 for(i=last[x];i;i=e[i].pre)if(e[i].flow&&dis[e[i].too]==dis[x]+e[i].dis&&!ins[e[i].too]){ 34 w=dfs(e[i].too,min(mx-used,e[i].flow));if(w){ 35 e[i].flow-=w,e[i^1].flow+=w,used+=w,ans+=w*e[i].dis; 36 if(used==mx){ins[x]=0;return mx;} 37 } 38 } 39 ins[x]=0,dis[x]=inf;return used; 40 } 41 inline void insert(int a,int b,int c,int d){ 42 e[++tot].too=b,e[tot].flow=c,e[tot].dis= d,e[tot].pre=last[a],last[a]=tot; 43 e[++tot].too=a,e[tot].flow=0,e[tot].dis=-d,e[tot].pre=last[b],last[b]=tot; 44 } 45 46 int main(){ 47 n=read(),m=read(); 48 s=0,t=n+n+1,tot=1; 49 for(i=1;i<=n;i++)insert(s,i+n,1,0),insert(s,i,1,read()),insert(i,t,1,0); 50 for(i=1;i<=m;i++){ 51 j=read(),k=read(); 52 if(j>k)swap(j,k); 53 insert(j+n,k,1,read()); 54 } 55 while(spfa())dfs(s,1<<23); 56 printf("%d ",ans); 57 }