\u4e00\u5f00\u59cbYY\u4e86\u4e00\u79cd\u8fde\u8fb9\u65b9\u5f0f\uff0c\u5c31\u662f\u6e90\u70b9\u5411\u7b2c\u4e00\u4e2a\u70b9\u8fde\u8fb9\uff0c\u7b2c\u4e00\u4e2a\u70b9\u5411\u6700\u540e\u4e00\u4e2a\u70b9\u8fde\u8fb9\uff0c\u6bcf\u4e2a\u8fb9\u7684\u6d41\u91cf\u662f1\uff0c\u5e0c\u671b\u80fd\u901a\u8fc7\u4e00\u4e9b\u5947\u5947\u602a\u602a\u7684\u7ea6\u675f\u6761\u4ef6\u6765\u4fdd\u8bc1\u80fd\u4ece1\u8dd1\u5230n\u3002
\n\u4f46\u662f\u5f88\u5feb\u8fd9\u4e2a\u60f3\u6cd5\u5c31\u88ab\u67aa\u6bd9\u4e86\u2014\u2014\u6bcf\u4e00\u5929\u9700\u8981\u6d88\u8017\u7684\u4eba\u529b\u662f\u4e0d\u540c\u7684\u3002
\n\u600e\u4e48\u529e\u5462\uff1f
\n\u6211\u4eec\u53ef\u4ee5\u8003\u8651\u4e00\u79cd\uff08\u6211\u778e\u53d6\u540d\u53eb\uff09\u66ff\u6362\u6cd5\u7684\u5efa\u6a21\u65b9\u6cd5\u3002
\n\u5177\u4f53\u6765\u8bf4\u5c31\u662f\uff0c\u5148\u786e\u5b9a\u4e00\u4e2a\u6700\u5927\u6d41\uff0c\u7136\u540e\u5c06\u5176\u4e2d\u7684\u4e00\u4e9b\u6d41\u91cf\u66ff\u6362\u4e3a\u5fc5\u987b\u8981\u901a\u8fc7\u5b9e\u9645\u9700\u8981\u7684\u8def\u5f84\u624d\u80fd\u8dd1\u8fc7\uff0c\u8fd9\u6837\u5c31\u4fdd\u8bc1\u4e86\u7b54\u6848\u7684\u5408\u6cd5\u6027\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<queue>\n\nconst int INF = 0x3f3f3f3f;\ninline int Min(int A,int B){\n\treturn A<B?A:B;\n}\ninline int Max(int A,int B){\n\treturn A>B?A:B;\n}\n\nstruct ee{\n\tint v;\n\tint w;\n\tint c;\n\tint nxt;\n}e[400005];\nint h[20005],et=-1;\ninline void Eadd(int U,int V,int W,int C){\n\te[++et]=(ee){V,W,C,h[U]};\n\th[U]=et;\n}\ninline void add(int U,int V,int W,int C){\n\tEadd(U,V,W,C);\n\tEadd(V,U,0,-C);\n}\nint n,m,s,t,vis[20005],dis[20005],val[20005],nw[20005],fa[20005];\nstd::queue<int> q;\ninline bool SPFA(){\n\tfor(int i=1;i<=t;++i){\n\t\tvis[i]=0,dis[i]=INF,val[i]=INF;\n\t}\n\tdis[s]=0,vis[s]=1,fa[t]=-1;\n\tq.push(s);\n\tint p;\n\twhile(!q.empty()){\n\t\tp=q.front();\n\t\tq.pop();\n\t\tvis[p]=0;\n\t\tfor(int i=h[p];i>=0;i=e[i].nxt){\n\t\t\tif(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){\n\t\t\t\tdis[e[i].v]=dis[p]+e[i].c;\n\t\t\t\tfa[e[i].v]=p;\n\t\t\t\tnw[e[i].v]=i;\n\t\t\t\tval[e[i].v]=Min(e[i].w,val[p]);\n\t\t\t\tif(!vis[e[i].v]){\n\t\t\t\t\tvis[e[i].v]=1;\n\t\t\t\t\tq.push(e[i].v);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\treturn fa[t]!=-1;\n}\n\nlong long ans=0,ans2=0;\ninline void EK(){\n\tint p;\n\twhile(SPFA()){\n\t\tp=t;\n\t\tans2+=val[t];\n\t\tans+=val[t]*dis[t];\n\t\twhile(p!=s){\n\t\t\te[nw[p]].w-=val[t];\n\t\t\te[nw[p]^1].w+=val[t];\n\t\t\tp=fa[p];\n\t\t}\n\t}\n}\nint a[20005],tot=0;\n\/\/tot\u4e0d\u80fd\u60f3\u5f53\u7136\u5730\u53d6\u6700\u5927\u503c\uff0c\u800c\u5e94\u8be5\u53d6\u548c\u3002\n\/\/\u8fd9\u662f\u56e0\u4e3a\uff0c\u8fc7\u7a0b\u4e2d\u53ef\u80fd\u5b58\u5728\u4e00\u4e9b\u60c5\u51b5\uff0c\u4f7f\u5f97\u5148\u96c7\u4f63\u67d0\u4e2a\u5fd7\u613f\u8005\u4f1a\u66f4\u4f18\u3002 \nvoid init(){\n\tscanf(\"%d%d\",&n,&m);\n\ts=n+2,t=n+3;\n\tfor(int i=1;i<=t;++i){\n\t\th[i]=-1;\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%d\",&a[i]);\n\t\ttot+=a[i];\n\t}\n\t++tot;\n\tadd(s,1,tot,0),add(n+1,t,tot,0);\n\tfor(int i=1;i<=n;++i){\n\t\tadd(i,i+1,tot-a[i],0);\n\t}\n\tint l,r,c;\n\tfor(int i=1;i<=m;++i){\n\t\tscanf(\"%d%d%d\",&l,&r,&c);\n\t\tadd(l,r+1,tot,c);\n\t}\n\tEK();\n\tprintf(\"%lld\\n\",ans);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u4e00\u5f00\u59cbYY\u4e86\u4e00\u79cd\u8fde\u8fb9\u65b9\u5f0f\uff0c\u5c31\u662f\u6e90\u70b9\u5411\u7b2c\u4e00\u4e2a\u70b9\u8fde\u8fb9\uff0c\u7b2c\u4e00\u4e2a\u70b9\u5411\u6700\u540e\u4e00\u4e2a\u70b9\u8fde\u8fb9\uff0c\u6bcf\u4e2a\u8fb9\u7684\u6d41\u91cf\u662f1\uff0c\u5e0c\u671b\u80fd\u901a\u8fc7\u4e00\u4e9b\u5947 … <\/p>\n