HLPP 都 炸 了 QAQ

zhoukangyang @ 2020-05-29 20:48:27

#include<bits/stdc++.h>
#define inf (0x3f3f3f3f)
#define N 11010
#define M 120010
using namespace std;
int n,m,s,t,sum,cc[N],use[N],yflow[N],flag[N],cntcc[N];
struct cmp {
    bool operator()(int a,int b) const {
        return cc[a]<cc[b];
    }
};
priority_queue<int,vector<int>,cmp> q;
struct node {
    int to,next,val;
} e[M<<1];
int head[N],last[N];
void add(int x,int y,int val,int id) {
    if(head[x]==0) head[x]=id;
    else e[last[x]].next=id;
    last[x]=id,e[id].val=val,e[id].to=y;
} 
void bfs() {
    for(int i = 1; i <= n; i++) cc[i] = inf;
    use[1]=t,cc[t]=0;
    int u=0,v=1;
    while(u<v) {
        ++u;
        int fst=use[u];
        for(int i = head[fst]; i != 0; i = e[i].next) {
            if(cc[e[i].to]!=inf) continue;
            if(e[i^1].val==0) continue;
            ++v,cc[e[i].to]=cc[fst]+1,use[v]=e[i].to;
        }
    }
    use[s]=n;
}
void HLPP() {
    bfs();
    if(cc[s]==inf) return;
    cc[s]=n;
    for(int i = 1; i <= n; i++) if(cc[i] != inf) cntcc[cc[i]]++;
    for(int i = head[s]; i != 0; i = e[i].next) {
        yflow[e[i].to] = e[i].val , e[i^1].val += e[i].val , e[i].val = 0;
        if(e[i].to!=s&&e[i].to!=t&&flag[e[i].to]==0) flag[e[i].to]=1,q.push(e[i].to);
    }
    while(!q.empty()) {
        int now = q.top();
        q.pop();
        flag[now]=0;
        for(int i = head[now]; i != 0; i = e[i].next) if(cc[now]==cc[e[i].to]+1) {
            int flow=min(yflow[now],e[i].val);
            if(flow == 0) continue;
            e[i].val-=flow,e[i^1].val+=flow;
            yflow[now]-=flow,yflow[e[i].to]+=flow;
            if(e[i].to!=s&&e[i].to!=t&&flag[e[i].to]==0) flag[e[i].to]=1,q.push(e[i].to);
        }
        if(yflow[now]) {
            --cntcc[cc[now]];
            cc[now]=n+1;
            for(int i = head[now]; i != 0; i = e[i].next) if(e[i].val) cc[now]=min(cc[e[i].to]+1,cc[now]);
            ++cntcc[cc[now]];
            flag[now]=1,q.push(now);
        }       
    }
}
signed main() {
    int x,y,z;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z,i*2);
        add(y,x,0,i*2+1);
    }
    HLPP();
    printf("%d\n",yflow[t]);
    return 0;
}

by UltiMadow @ 2020-05-29 20:49:31

dinic 和 EK 不香嘛（

by zhoukangyang @ 2020-05-29 20:50:14

@UltiMadow 我本来想做加强版的，我用dinic已经过了

by zhoukangyang @ 2020-05-29 20:51:55

顺便带个贴

by zhoukangyang @ 2020-05-29 20:54:57

好像是死循环

by zhoukangyang @ 2020-05-29 20:58:19

if(cc[now]==n+1) continue; 加了这句话，90

#include<bits/stdc++.h>
#define inf (0x3f3f3f3f)
#define N 11010
#define M 120010
using namespace std;
int n,m,s,t,sum,cc[N],use[N],yflow[N],flag[N],cntcc[N];
struct cmp {
    bool operator()(int a,int b) const {
        return cc[a]<cc[b];
    }
};
priority_queue<int,vector<int>,cmp> q;
struct node {
    int to,next,val;
} e[M<<1];
int head[N],last[N];
void add(int x,int y,int val,int id) {
    if(head[x]==0) head[x]=id;
    else e[last[x]].next=id;
    last[x]=id,e[id].val=val,e[id].to=y;
} 
void bfs() {
    for(int i = 1; i <= n; i++) cc[i] = inf;
    use[1]=t,cc[t]=0;
    int u=0,v=1;
    while(u<v) {
        ++u;
        int fst=use[u];
        for(int i = head[fst]; i != 0; i = e[i].next) {
            if(cc[e[i].to]!=inf) continue;
            if(e[i^1].val==0) continue;
            ++v,cc[e[i].to]=cc[fst]+1,use[v]=e[i].to;
        }
    }
    use[s]=n;
}
void HLPP() {
    bfs();
    if(cc[s]==inf) return;
    cc[s]=n;
    for(int i = 1; i <= n; i++) if(cc[i] != inf) cntcc[cc[i]]++;
    for(int i = head[s]; i != 0; i = e[i].next) {
        yflow[e[i].to] = e[i].val , e[i^1].val += e[i].val , e[i].val = 0;
        if(e[i].to!=s&&e[i].to!=t&&flag[e[i].to]==0) flag[e[i].to]=1,q.push(e[i].to);
    }
    while(!q.empty()) {
        int now = q.top();
        q.pop();
        flag[now]=0;
        if(cc[now]==n+1) continue;
        for(int i = head[now]; i != 0; i = e[i].next) if(cc[now]==cc[e[i].to]+1) {
            int flow=min(yflow[now],e[i].val);
            if(flow == 0) continue;
            e[i].val-=flow,e[i^1].val+=flow;
            yflow[now]-=flow,yflow[e[i].to]+=flow;
            if(e[i].to!=s&&e[i].to!=t&&flag[e[i].to]==0) flag[e[i].to]=1,q.push(e[i].to);
        }
        if(yflow[now]) {
            --cntcc[cc[now]];
            if(cntcc[cc[now]]==0) for(int i = 1; i <= n; i++) if(cc[i]>cc[now]&&i!=s&&i!=t) cc[now]=n+1;
            cc[now]=n+1;
            for(int i = head[now]; i != 0; i = e[i].next) if(e[i].val) cc[now]=min(cc[e[i].to]+1,cc[now]);
            ++cntcc[cc[now]];
            flag[now]=1,q.push(now);
        }       
    }
}
signed main() {
    int x,y,z;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z,i*2);
        add(y,x,0,i*2+1);
    }
    HLPP();
    printf("%d\n",yflow[t]);
    return 0;
}

by lgswdn_SA @ 2020-05-29 21:02:00

TLE？

by zhoukangyang @ 2020-05-29 21:02:27

@foin 是的/kk

by lgswdn_SA @ 2020-05-29 21:05:09

我就无能为力/kk