Description

有 n 個數 x1 ~xn 。你需要找出它們的一個排列，滿足 m 個條件，每個條件形如 x_a 必須在x_b之前。在此基礎上，你要最大化這個排列的最大子段和。

Input

第一行兩個整數 n,m，第二行 n 個整數 x1 ~xn ，接下來 m 行每行兩個整數 a,b。

Output

輸出一行一個整數表示最大子段和。

Sample Input

5 4
2 3 -2 5 -3
1 5
2 3
3 4
5 3

Sample Output

6

Data Constraint

Subtask 1 (5pts)：n<=10。
Subtask 2 (20pts)：n<=20。
Subtask 3 (19pts)：m=n-1 且 x1 一定在排列的第一位。
Subtask 4 (56pts)：無特殊限制。 對于全部數據，n<=500，m<=1000，|x i |<=1000，保證存在至少一種排列。

Solution

• 先貼題解：

• 看到數據范圍，就應該想到網絡流！！！

• 先把權值為正的數放到一起，但全部選就意味著同時也要選很多負的，這樣不一定最優。

• 考慮把其中一些點扔走（往左右扔），或者干脆把中間的負點也選了算了。

• 于是向上面說的那樣連邊跑最小割，用正權值和-最小割即為答案。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=1005,inf=1e9; int s,t,ans,tot=1; int first[N],nex[N*6],en[N*6],w[N*6]; int dis[N],gap[N*6],cur[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48),ch=getchar();return w?-X:X; } inline int min(int x,int y) {return x<y?x:y; } inline void ins(int x,int y,int z) {nex[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline void insert(int x,int y,int z) {ins(x,y,z),ins(y,x,0); } int sap(int x,int y) {if(x==t) return y;int use=0;for(int i=first[x];i;i=nex[i])if(w[i] && dis[x]==dis[en[i]]+1){int sum=sap(en[i],min(y-use,w[i]));w[i]-=sum,w[i^1]+=sum,use+=sum;if(dis[s]>t || use==y) return use;}cur[x]=first[x];if(!--gap[dis[x]]) dis[s]=t+1;gap[++dis[x]]++;return use; } int main() {freopen("permutation.in","r",stdin);freopen("permutation.out","w",stdout);int n=read(),m=read();s=n<<1|1,t=s+1;for(int i=1;i<=n;i++){int x=read();if(x>0){ans+=x;insert(s,i,x);insert(i+n,t,x);}else insert(i,i+n,-x);}for(int i=1;i<=m;i++){int x=read(),y=read();insert(x,y,inf);insert(x+n,y+n,inf);}for(int i=1;i<=t;i++) cur[i]=first[i];gap[0]=t;while(dis[s]<=t) ans-=sap(s,inf);printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5669. 【GDSOI2018模拟4.19】排列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。