1 #include
     
       2 #include
      
        3 #define M 1605 4 #define S 3000005 5 using namespace std; 6 int q[S],f[M],n,m,ans,a[M],head[M],next[S],u[S],v[S],c[S],fr[S],cnt=1,d[M],fro[M],T; 7 void jia(int a1,int a2,int a3,int a4) 8 { 9     cnt++;10     next[cnt]=head[a1];11     head[a1]=cnt;12     u[cnt]=a2;13     v[cnt]=a3;14     c[cnt]=a4;15     fr[cnt]=a1;16     return;17 }18 bool bfs()19 {20     for(int i=1;i<=T;i++)21       d[i]=0x7fffffff;22     f[0]=1;23     int h=0,t=1;24     q[1]=0;25     for(;h!=t;)26       {27         h++;28         int p=q[h];29         f[p]=0;30         for(int i=head[p];i;i=next[i])31           if(v[i]&&d[u[i]]>d[p]+c[i])32             {33                 fro[u[i]]=i;34                 d[u[i]]=d[p]+c[i];35                 if(!f[u[i]])36                   {37                     t++;38                     q[t]=u[i];39                   }40             }41       }42     if(d[T]==0x7fffffff)43       return 0;44     else45       return 1;46 }47 void zhao()48 {49     int ma=0x7fffffff;50     for(int i=fro[T];i;i=fro[fr[i]])51       ma=min(ma,v[i]);52     for(int i=fro[T];i;i=fro[fr[i]])53       {54         v[i]-=ma;55         v[i^1]+=ma;56         ans+=ma*c[i];57       }58     return;59 }60 int main()61 {62     scanf("%d%d",&n,&m);63     T=2*n+1;64     for(int i=1;i<=n;i++)65       scanf("%d",&a[i]);66     for(int i=1;i<=n;i++)67       {68         jia(0,i,1,0);69         jia(i,0,0,0);70         jia(i+n,T,1,0);71         jia(T,i+n,0,0);72         jia(0,i+n,1,a[i]);73         jia(i+n,0,0,-a[i]);74       }75     for(int i=1;i<=m;i++)76       {77         int a1,a2,a3;78         scanf("%d%d%d",&a1,&a2,&a3);79         if(a1>a2)80           swap(a1,a2);81         jia(a1,a2+n,1,a3);82         jia(a2+n,a1,0,-a3);83       }84     for(;bfs();)85       zhao();86     printf("%d\n",ans);87     return 0;88 }
      
     

费用流，拆点 源点分别向拆出的点连费用为0，费用为定位费的点，再把原有的航路建出来。