permutation

套路题
把最大子段和([l,r])变成去掉最小的前/后缀。
把前缀([1,l-1])内的数赋权(1)，([l,r])的赋权(2)，([r+1,n])赋权(3)、
如果一个数(x)是正数，则先把(ans+=x)，如果(x)赋权(1,3)，(ans-=x)
否则如果(x)赋权(2)，(ans-=x)。
考虑HNOI2013切糕那样子的建图，把每个点拆成(i,i')两个，建立(n)条(3)个点的链。
如果(x)是正数，则(s->i,i'->t)连接(x)
否则(i->i')连接(-x)。
对于题目的每个限制((x,y))，如果(x)赋权大于(y)赋权则不合法。
用HNOI2013切糕的方法连边限制即可。
(ans-)最小割就是答案。

#include<bits/stdc++.h>
using namespace std;
#define M 100010
int h[M],nxt[M],v[M],w[M],s,t,dep[M],ec,m,n,ans;
void add(int a,int b,int c){v[++ec]=b;w[ec]=c;nxt[ec]=h[a];h[a]=ec;}
void adj(int a,int b,int c){
	add(a,b,c);
	add(b,a,0);
}
bool bfs(){
    queue<int>q;
	q.push(s);
    for(int i=1;i<=t;i++)
    	dep[i]=0;
	dep[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=h[x];i;i=nxt[i])
            if(w[i]&&!dep[v[i]]){
            	dep[v[i]]=dep[x]+1;
				q.push(v[i]);
            	if(v[i]==t)
					return 1;
			}
    }
	return 0;
}
int dfs(int x,int dis){
    if(x==t)
		return dis;
	int tp=dis;
    for(int i=h[x];i;i=nxt[i])
        if(dep[v[i]]==dep[x]+1&&w[i]){
            int f=dfs(v[i],min(tp,w[i]));
            if(!f)
				dep[v[i]]=0;
            tp-=f;
            w[i]-=f;
			w[i^1]+=f;
            if(!tp)break;
        }
    return dis-tp;
}
int din(){
    int aans=0;
    while(bfs()){
    	int v;
    	while(v=dfs(s,1e9))
			aans+=v;
	}
    return aans;
}
int main(){
	freopen("permutation.in","r",stdin);
	freopen("permutation.out","w",stdout);
	ec=1;
	scanf("%d%d",&n,&m);
	t=4*n+1;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(x>0){
			ans+=x;
			adj(s,2*i+1,x);
			adj(2*i+2,t,x);
		}
		else
			adj(2*i+1,2*i+2,-x);
	}
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		adj(2*x+1,2*y+1,1e9);
		adj(2*x+2,2*y+2,1e9);
	}
	printf("%d",ans-din());
}