91pts WA on #10 with Dinic algo.

P3376 【模板】网络最大流

2020kanade @ 2022-03-04 16:20:31

目测问题出在增广?

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N1=5000,N2=3e5+10,inf=LLONG_MAX-1;
struct edge {LL to,nxt,cap;}G[N1<<1];
LL head[N1<<1],dis[N1],cnt,n,m,rad[N1],s,t;
inline void add_edge(LL &ct,LL u,LL v,LL val) {G[ct].to=v,G[ct].cap=val,G[ct].nxt=head[u],head[u]=ct,++ct;}
inline bool delaminate(LL st,LL t)
{
    memset(dis,0,sizeof(dis));dis[st]=1;
    queue<LL> q;q.push(st);
    while(!q.empty())
    {
        LL u=q.front();q.pop();rad[u]=head[u];
        for(LL i=head[u];i!=-1;i=G[i].nxt) {LL v=G[i].to;if(!dis[v] && G[i].cap) dis[v]=dis[u]+1,q.push(v);}
    }
    return dis[t];
}
inline LL augment(LL u,LL ref,LL t)
{
    if(u==t || !ref) return ref;
    LL nrf=ref;for(LL i=rad[u];i!=-1 && nrf;i=G[i].nxt)
    {
        LL v=G[i].to;rad[u]=i;
        if(dis[v]==dis[u]+1 && G[i].cap)
        {
            LL aug_min=min(G[i].cap,nrf),dlta=augment(v,aug_min,t);G[i].cap-=dlta,G[i^1].cap-=dlta;nrf-=dlta;if(!nrf) break;
        }
    }return ref-nrf;
}
inline LL dinic(LL s,LL t)
{
    LL ans=0;
    while(delaminate(s,t)) ans+=augment(s,inf,t);
    return ans;
}
inline LL qread()
{
    LL a=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {a=a*10+ch-'0';ch=getchar();}
    return a*f;
}
inline void qwrite(LL x)
{
    if(x==0) {putchar('0'),putchar('\n');return;}
    char w[128];LL cnt=0;
    if(x<0) putchar('-'),x*=-1;
    while(x) {w[cnt++]=(x%10)+'0';x/=10;}
    while(cnt--) putchar(w[cnt]);putchar('\n');
}
int main()
{
    memset(head,-1,sizeof(head));
    n=qread(),m=qread(),s=qread(),t=qread();
    for(LL i=1;i<=m;i++) {LL u=qread(),v=qread(),val=qread();add_edge(cnt,u,v,val),add_edge(cnt,v,u,0);}
    qwrite(dinic(s,t));
    return 0;
}

by strcmp @ 2022-03-05 12:56:35

建议提高一下代码可读性Orz

LL aug_min = min(G[i].cap, nrf), dlta = augment(v, aug_min, t); 
            G[i].cap -= dlta, G[i ^ 1].cap -= dlta;
            nrf -= dlta; if (!nrf) break;

改成这样

LL aug_min = min(G[i].cap, nrf), dlta = augment(v, aug_min, t); 
            G[i].cap -= dlta, G[i ^ 1].cap += dlta;
            nrf -= dlta; if (!nrf) break;

by strcmp @ 2022-03-05 12:59:50

@wql463 AC记录


by 2020kanade @ 2022-03-05 16:20:28

@wql463 多谢

反向弧写成减流竟硬是没看出来,WTCL

可读性应该是洛谷的锅,实在不行回头发上来的时候打个换行


|