这个网络流的建模非常妙，我是按照之前做过的某个题目来想的

题意

有\(n\)个数 \(x_1\cdots x_n\) 。你需要找出它们的一个排列，满足\(m\)个条件，每个条件形如\(x_a\)必须在\(x_b\)之前。在此基础上，你要最大化这个排列的最大子段和。

\(1\leq n\leq 500\)，\(1\leq m \leq 1000\)，\(1\leq |x_i|\leq 1000\)

分析

看数据范围猜算法，一看就知道是网络流

首先，我们考虑最终选择的是一个最终合法排列中连续的一段，我们先假定全部正数都被选了，负数都没选，那么我们接下来就考虑当前的这个约束会给我们什么样的影响。

调整当前我们的选择，有三种策略，即某一条链上的正数被挤到前面而选不到；挤到后面而选不到；在中间（序列中的位置）选出一个负数，这三种都会让答案减小。

考虑这样建图：拆点，对于所有正数，因为考虑到是“放弃”，那我们拆点，然后起点终点分别连边（即起点连一个，终点连一个）。对于所有负数，我们对于拆出来两个点之间连上一条为这个数绝对值的边。对于所有限制，我们只需要直接连上两条（拆点的分别两条）流量无穷的边就行了。

实际上来说，正确性要看出也是不难的，最主要是这个用操作和限制来连边建图的方式很骚……

# include 
    
     # define mem(x,v) memset(x,v,sizeof(x))# define reg(i,x) for(int i=last[x];i;i=e[i].nxt)# define INF 100000010# define il inlineusing namespace std;typedef long long ll;const int maxn = 10010;struct edge{ int to,nxt,v; } e[maxn<<1]; int c=0;int last[maxn];int S,T;il void insert(int u,int v,int w){    e[++c] = (edge){v,last[u],w}; last[u]=c;    e[++c] = (edge){u,last[v],0}; last[v]=c;}int q[maxn],h[maxn];il bool bfs(){    int head=0,tail=1,now;    mem(h,-1); q[0]=S; h[S]=0;    while (head
     
      0){            ans+=x;            insert(S,i+i+1,x);            insert(i+i+2,T,x);        } else insert(i+i+1,i+i+2,-x);    }    for (int i=1;i<=m;++i){        int u,v; scanf("%d%d",&u,&v);        insert(u+u+1,v+v+1,INF);        insert(u+u+2,v+v+2,INF);    }    dinic();    printf("%lld\n",ans);    return 0;}