jzoj 5669[GDSOI 2018シミュレーション4.19]配列

Description
n個の数x 1~xnがある.m個の条件を満たし、x_のような各条件を満たす配列を見つける必要があります.aはx_でなければならないbの前に.これに基づいて、この配列の最大サブセグメントとを最大化します.
Subtask 1 (5pts):n<=10. Subtask 2 (20pts):n<=20. Subtask 3(19 pts):m=n-1であり、x 1は必ず配列の1位である.Subtask 4(56 pts):特に制限はありません.全データについて、n<=500、m<=1000、|x i|<=1000であり、少なくとも1つの配列が存在することを保証する.
Solution
今日の試合はとても退廃的だと言えます(でもお金が痛いですね.
これまでn<=100のネットワークストリームについて話していましたが、500でもいいようです(滑稽です)
各点を分解し、正点連(s,i)および(i’,t)に対して、容量は点権対負点連(i,i’)、容量は点権絶対値対制限条件(x,y)、連(x,y)および(x’,y’)、容量はINF
一波を観察すると,このように構築図が切り取られたのは条件を満たす連続セグメントであり,先頭と末尾が正数であり,正負の重みだけが切り取られ,s−>i−>i′−>tのようなエッジを考慮し,3つのエッジを切り取ったのはそれぞれ3つの異なるセグメントに現れたことを表している.
Code

#include 
#include 
#include 
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))

const int INF=0x3f3f3f3f;
const int N=20005;
const int E=200005;

struct edge {int x,y,w,next;} e[E];

int dis[N],queue[N];
int cur[N],ls[N],edCnt=1;

void add_edge(int x,int y,int w) {
    e[++edCnt]=(edge) {x,y,w,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge) {y,x,0,ls[y]}; ls[y]=edCnt;
}

bool bfs(int st,int ed) {
    fill(dis,-1); dis[st]=1;
    int head=1,tail=1; queue[1]=st;
    while (head<=tail) {
        int now=queue[head++];
        if (now==ed) return true;
        for (int i=ls[now];i;i=e[i].next) {
            if (e[i].w>0&&dis[e[i].y]==-1) {
                dis[e[i].y]=dis[now]+1;
                queue[++tail]=e[i].y;
            }
        }
    }
    return false;
}

int find(int now,int ed,int mn) {
    if (now==ed||!mn) return mn;
    int ret=0;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].w>0&&dis[now]+1==dis[e[i].y]) {
            int d=find(e[i].y,ed,std:: min(mn-ret,e[i].w));
            e[i].w-=d; e[i^1].w+=d; ret+=d;
            if (ret==mn) break;
        }
    }
    return ret;
}

int dinic(int st,int ed) {
    int ret=0;
    while (bfs(st,ed))
        ret+=find(st,ed,INF);
    return ret;
}

int main(void) {
    freopen("permutation.in","r",stdin);
    freopen("permutation.out","w",stdout);
    int n,m; scanf("%d%d",&n,&m);
    int ans=0;
    rep(i,1,n) {
        int x; scanf("%d",&x);
        if (x<0) add_edge(i,i+n,-x);
        else {
            ans+=x;
            add_edge(0,i,x);
            add_edge(i+n,n*2+1,x);
        }
    }
    rep(i,1,m) {
        int x,y; scanf("%d%d",&x,&y);
        add_edge(x,y,INF);
        add_edge(x+n,y+n,INF);
    }
    printf("%d
", ans-dinic(0,n*2+1));
    return 0;
}