社区讨论

我是怎么AC的

P3376【模板】网络最大流参与者 5已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi7xin9l
此快照首次捕获于
2025/11/21 05:14
4 个月前
此快照最后确认于
2025/11/21 05:14
4 个月前
查看原帖
rt (怀疑自己是不是好几次这样) https://www.luogu.org/recordnew/show/18240528 建议加强数据。。。(要不遗憾终生,跟自己学会了似的
CPP
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define R register int
#define getchar() *S++
const int Inf=0x3f3f3f3f,N=10010,M=200010;
char RR[500000005],*S=RR;
using namespace std;
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
int n,m,s,t,cnt,mx,fl;//cnt没有初始化成1
int vr[M],w[M],nxt[M],fir[N],incf[N],d[N];
queue<int>q;
inline void add(int u,int v,int ww) {
    vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;
    vr[++cnt]=u,w[cnt]=0,nxt[cnt]=fir[u],fir[u]=cnt;//什么垃圾加边fir[u]=cnt?fir[v]=cnt
}
inline bool bfs() {
    memset(d,0,sizeof(d)); while(q.size()) q.pop();
    q.push(s); d[s]=1;
    while(q.size()) { R u=q.front(); q.pop();
        for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
            if(w[i]&&!d[v]) {
                q.push(v),d[v]=d[u]+1;
                if(v==t) return true;
            }
        }
    } return false;
}
inline int dinic(int u,int fl) {
    if(u==t) return fl; R res=fl;
    for(R i=fir[u];i&&res;i=nxt[i]) { R v=vr[i];
        if(w[i]&&d[v]==d[u]+1) {
            R k=dinic(v,min(res,w[i]));
            if(!k) d[v]=0;
            w[i]-=k,w[i^1]+=k,res-=k;
        }	
    } return fl-res;
}
signed main() { 
    fread(RR,1,sizeof(RR),stdin);
    n=g(),m=g(),s=g(),t=g();
    for(R i=1,u,v,w;i<=m;++i) u=g(),v=g(),w=g(),add(u,v,w);
    while(bfs()) while(fl=dinic(s,Inf)) mx+=fl;
    printf("%d\n",mx);
}

回复

7 条回复,欢迎继续交流。

正在加载回复...