蒟蒻求助

mrozhx @ 2020-04-19 20:23:23

#include<bits/stdc++.h>
using namespace std;
int n,m,x,tot=-1;
struct null{
    int next,to,flow;
}edge[4001];
int head[201],dep[201];
void add(int from,int to,int flow){
    edge[++tot].to=to;
    edge[tot].flow=flow;
    edge[tot].next=head[from];
    head[from]=tot;
}
bool bfs(int s,int t){
    memset(dep,-1,sizeof(dep));
    dep[s]=0;
    queue<int> p;
    p.push(s);
    while(!p.empty()){
        int now=p.front();
        p.pop();
        for(int i=head[now];i!=-1;i=edge[i].next){
            int to=edge[i].to;
            if(dep[to]==-1&&edge[i].flow>0){
                p.push(to);
                dep[to]=dep[now]+1;
            }
        }
    }
    return dep[t]!=-1;
}
int dfs(int s,int t,int minflow){
    if(s==t) return minflow;
    int now_flow;
    for(int i=head[s];i!=-1;i=edge[i].next){
        int to=edge[i].to;
        if(dep[to]==dep[s]+1&&edge[i].flow>0){
            now_flow=dfs(to,t,min(minflow,edge[i].flow));
            if(now_flow>0){
                edge[i].flow-=now_flow;
                edge[i^1].flow+=now_flow;
                return now_flow;
            }
        }
    }
    return 0;
}
void dinic(int s,int t){
    int re=0;
    while(bfs(s,t)){
        while(int ad=dfs(s,t,1e8)){
            re+=ad;
        }
    }
    cout<<re;
    return;
}
int main(){
    int from,to,flow;
    int s,t;
    memset(dep,-1,sizeof(dep));
    memset(head,-1,sizeof(head));
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>from>>to>>flow;
        add(from,to,flow);
        add(to,from,0);
    }
    dinic(s,t);
    return 0;
}

by 鏡音リン @ 2020-04-19 20:28:46

数据范围（

by mrozhx @ 2020-04-19 20:29:46

@鏡音リン 我连样例都没过……

by 鏡音リン @ 2020-04-19 20:32:47

@醉水 我这跑样例能过啊（

by serene_analysis @ 2020-04-19 21:00:08

@醉水 tot的问题？我初始化成0会WA三个点但是初始化成1就A了？

by serene_analysis @ 2020-04-19 21:02:22

@醉水 您对照我的看看吧

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long
#define function void
#undef int
struct node{
    int to;
    int next;
    int w;
}qxx[200005];
int tot=1;
int h[100005];
int n,m,s,k;
int d[100005];
int ans;
int x,y,z;
int sth;
void add(int x,int y,int z){
    qxx[++tot]=(node){y,h[x],z};
    h[x]=tot;
}
//bool operator==(int a,int b){
//  return (a-5)==(b-5);
//}
bool bfs(){
    std::queue<int>q;
    memset(d,0,sizeof d);
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=qxx[i].next){
            int v=qxx[i].to;
            if(!d[v]&&qxx[i].w){
                q.push(v);
                d[v]=d[x]+1;
                if(v==k)return 1;
            }
        }
    }
    return 0;
}
int dfs(int u,int flow){
    if(u==k)return flow;
    int rest=flow;
    for(int i=h[u];i&&rest;i=qxx[i].next){
        int v=qxx[i].to;
        if(d[v]==d[u]+1&&qxx[i].w){
            int tmp=dfs(v,std::min(rest,qxx[i].w));
            if(!tmp)d[v]=0;
            rest-=tmp;
            qxx[i].w-=tmp;
            qxx[i^1].w+=tmp;
        }
    }
    return flow-rest;
}
signed main(){
    scanf("%d%d%d%d",&n,&m,&s,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    while(bfs())while(sth=dfs(s,1e9))ans+=sth;
    if(!ans){
        puts("Orz Ni Jinan Saint Cow!");
        return 0;
    }
    printf("%d",ans);
    return 0;
}

别在意码风

by serene_analysis @ 2020-04-19 21:02:51

还有这道题是我A了 地震逃生 之后交的，拿了双倍经验