Blog Description & message board

Better reading experience & Latest updates see https://q779.github.io/

CSDN Articles will be updated synchronously on , But some articles will not be updated （ obviously ）

It may not be maintained in the future CSDN, It depends on me github.io Development

Welcome to leave a message .

It seems that too short articles are not allowed to be posted here , Then I'll post a few codes to recharge

// HLPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define INF 0x3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define N (int)(2e3+15)
#define M (int)(3e5+15)
#define SIZ (int)(1e5+5)
char buf1[SIZ];
char *p1=buf1,*p2=buf1;
char readchar()
{
    
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){
    x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    
    static T stk[66];T top=0;
    do{
    stk[top++]=k%10,k/=10;}while(k);
    while(top){
    pc(stk[--top]+'0');}
}
struct Edge{
    int v,w,next;};
vector<Edge> vec[N];
int n,m,s,t,now;
int gap[N],h[N],val[N],vis[N];
struct cmp
{
    
    bool operator()(int a,int b)
        {
    return h[a]<h[b];}
};
priority_queue<int,vector<int>,cmp> q;
queue<int> b;
bool bfs()
{
    
    memset(h,0x3f,(n+1)*sizeof(int));
    b.push(t);h[t]=0;vis[t]=1;
    while(!b.empty())
    {
    
        int u=b.front();b.pop();
        vis[u]=0;
        for(int i=0; i<vec[u].size(); i++)
        {
    
            int v=vec[u][i].v,j=vec[u][i].next;
            if(vec[v][j].w>0&&h[v]>h[u]+1)
            {
    
                h[v]=h[u]+1;
                if(!vis[v])
                    b.push(v),vis[v]=1;
            }
        }
    }
    return h[s]!=INF;
}
void relabel(int u)
{
    
    h[u]=INF;
    for(int i=0; i<vec[u].size(); i++)
    {
    
        int v=vec[u][i].v;
        if(vec[u][i].w>0&&h[u]>h[v]+1)
            h[u]=h[v]+1;
    }
}
int HLPP()
{
    
    if(!bfs())return -1;
    h[s]=n;
    for(int i=1; i<=n; i++)
        if(h[i]!=INF)++gap[h[i]];
    for(int i=0; i<vec[s].size(); i++)
    {
    
        int v=vec[s][i].v,w=vec[s][i].w,j=vec[s][i].next;
        if(w>0)
        {
    
            val[s]-=w;
            val[v]+=w;
            vec[s][i].w-=w;
            vec[v][j].w+=w;
            if(!vis[v]&&v!=t&&v!=s)
                q.push(v),vis[v]=1;
        }
    }
    while(!q.empty())
    {
    
        int u=q.top();
        q.pop();vis[u]=0;
        if(h[u]==INF)continue; // !!!!!!!!!!!
        for(int i=0; i<vec[u].size(); i++)
        {
    
            int v=vec[u][i].v,j=vec[u][i].next;
            if(vec[u][i].w>0&&h[u]==h[v]+1)
            {
    
                int w=min(vec[u][i].w,val[u]);
                val[u]-=w;
                val[v]+=w;
                vec[u][i].w-=w;
                vec[v][j].w+=w;
                if(!vis[v]&&v!=t&&v!=s)
                    q.push(v),vis[v]=1;
                if(!val[u])break;
            }
        }
        if(!val[u])continue;
        if(!--gap[h[u]])
        {
    
            for(int i=1; i<=n; i++)
                if(i!=s&&i!=t&&h[u]<h[i]&&h[i]<=n)
                    h[i]=n+1;
        }
        relabel(u);++gap[h[u]];
        q.push(u);vis[u]=1;
    }
    return val[t];
}
signed main()
{
    
    read(n);read(m);read(s);read(t);
    for(int i=1,u,v,w; i<=m; i++)
    {
    
        read(u);read(v);read(w);
        vec[u].push_back({
    v,w,(int)vec[v].size()});
        vec[v].push_back({
    u,0,(int)vec[u].size()-1});
    }
    write(HLPP());pc('\n');
    return 0;
}