社区讨论

dinic优化假了求助

题目总版参与者 7已保存回复 15

讨论操作

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

当前回复
15 条
当前快照
1 份
快照标识符
@lo374wf5
此快照首次捕获于
2023/10/24 01:53
2 年前
此快照最后确认于
2023/10/24 01:53
2 年前
查看原帖
模板能过,但是除了模板都过不了!!!(因为模板数据特别水吗?)
做24题的时候T到飞起......
CPP
%:include<bits/stdc++.h>
template <typename L> inline void Read(L &X)<%
    char c=getchar();L zhi=0,fu=1;
    while(not isdigit(c))<%if(c=='-')fu=-1;c=getchar();%>
    while(isdigit(c))<%zhi=(zhi<<1)+(zhi<<3)+c-'0';c=getchar();%>
    X=fu*zhi;
%>
template <typename L> inline void Write(L X)<%
    if(X<0) putchar('-'),X=-X;
    if(X>9) Write(X/10);
    putchar(X%10^48);
%>
template <typename L> inline L Max(L X,L Y){return X>Y?X:Y;}
template <typename L> inline L Min(L X,L Y){return X<Y?X:Y;}
struct edge{int to,nxt; long long val;}a[4000001];
int n,m,s,t,num=1,head[1000001],d[1000001],p[1000001];
long long ans,inf=172929189189631083;
inline void add(int u,int v,long long w){a[++num].to=v; a[num].val=w; a[num].nxt=head[u]; head[u]=num;}
std::queue<int>q;
inline bool bfs(){
    memset(d,0,sizeof(d));
    while(!q.empty()) q.pop();
    q.push(s); d[s]=1;
    while(!q.empty()){
        int u=q.front(); q.pop(); p[u]=head[u];
        for(register int i=head[u];i;i=a[i].nxt){
            int v=a[i].to; long long fl=a[i].val;
            if(!fl||d[v]) continue;
            d[v]=d[u]+1; q.push(v);
            if(v==t) return true;
        }
    }
    return false;
}
inline long long dfs(int u,long long flow){
    if(!flow||u==t) return flow;
    long long now=flow;
    for(register int i=p[u];i&&now;i=a[i].nxt){
        int v=a[i].to; long long fl=a[i].val;
        p[u]=i;
        if(!fl||d[v]!=d[u]+1) continue;
        long long k=dfs(v,Min(now,fl));
        a[i].val-=k; a[i^1].val+=k; now-=k;
    }
    return flow-now;
}
int main()<%
    Read(n); Read(m); Read(s); Read(t);
    for(register int i=1;i<=m;++i){
        int u,v,w;
        Read(u); Read(v); Read(w);
        add(u,v,w); add(v,u,0);
    }
    while(bfs()) ans+=dfs(s,inf);
    Write(ans);
    exit(0);
%>

回复

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

正在加载回复...