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
可读性应该是洛谷的锅,实在不行回头发上来的时候打个换行