本文共 1735 字，大约阅读时间需要 5 分钟。
分析
代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int inf = INT_MAX;int n,m,f[40010],mf[40010],pre[40010],from[40010];int head[40010],nxt[40010],to[40010];int cost[40010],ath[40010],fr[40010],cnt;int d[40010];bool iq[40010];int s,t,Ans;int q[400100],fi,la;inline void add(int x,int y,int z,int c){ nxt[++cnt]=head[x]; head[x]=cnt; to[cnt]=y; f[cnt]=z; cost[cnt]=c; fr[cnt]=x; nxt[++cnt]=head[y]; head[y]=cnt; to[cnt]=x; f[cnt]=0; cost[cnt]=-c; fr[cnt]=y; ath[cnt]=cnt-1;ath[cnt-1]=cnt;}inline void go(){ register int i; while(1){ for(i=s;i<=t;i+=4)d[i]=d[i+1]=d[i+2]=d[i+3]=inf; fi=la=100001; q[fi]=s; d[s]=0; iq[s]=1; int flow=inf; while(fi<=la){ int x=q[fi]; fi++; iq[x]=0; if(d[x]>=inf)continue; for(i=head[x];i;i=nxt[i]){ if(f[i]&&d[to[i]]>d[x]+cost[i]){ d[to[i]]=d[x]+cost[i]; pre[to[i]]=i; flow=min(flow,f[i]); if(!iq[to[i]]){ if(d[to[i]]>d[q[fi]])q[++la]=to[i]; else q[--fi]=to[i]; iq[to[i]]=1; } } } } if(d[t]>=inf)return; int wh=pre[t]; while(wh){ f[wh]-=flow; f[ath[wh]]+=flow; Ans+=flow*cost[wh]; wh=pre[fr[wh]]; } }}inline int ra(){ int x=0,f=1;char s=getchar(); while(!isdigit(s)){ if(s=='-')f=-1;s=getchar();} while(isdigit(s))x=(x<<3)+(x<<1)+(s-'0'),s=getchar(); return x*f;}int main(){ register int i; n=ra(),m=ra(); s=0,t=n+2; for(i=1;i<=n;++i){ int x; x=ra(); add(i,i+1,inf-x,0); } add(s,1,inf,0),add(n+1,n+2,inf,0); for(i=1;i<=m;++i){ int x,y,z; x=ra(),y=ra(),z=ra(); add(x,y+1,inf,z); } go(); printf("%d\n",Ans); return 0;}
转载于:https://www.cnblogs.com/yzxverygood/p/9973454.html