DinicWA了7,8,9,10,求助

P3376 【模板】网络最大流

YBT_mail @ 2020-08-27 08:41:49

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
}; 
int n,m,s,t;
vector <Edge> edges;
vector <int> G[10003];
int d[1003],cur[1003],mm;
bool vis[1003];
void add(int from,int to,int cap){
    edges.push_back(Edge(from,to,cap,0));
    edges.push_back(Edge(to,from,0,0));
    mm=edges.size();
    G[from].push_back(mm-2);
    G[to].push_back(mm-1);
}
bool bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    vis[s]=1;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=0;i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if(!vis[e.to]&&e.cap>e.flow){
                vis[e.to]=1;
                d[e.to]=d[x]+1;
                Q.push(e.to);
            }
        } 
    }
    return vis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int flow=0,f;
    for(int& i=cur[x];i<G[x].size();i++){
        Edge& e=edges[G[x][i]];
        if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
            e.flow+=f;
            edges[G[x][i]^1].flow-=f;
            flow+=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}
int Maxflow(int ss,int tt){
    s=ss,t=tt;
    int flow=0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        flow+=dfs(s,100000000);
    }
    return flow;
}
int main(){
    int ss,tt,x,y,c;
    cin>>n>>m>>ss>>tt;
    for(int i=1;i<=m;i++){
         scanf("%d%d%d",&x,&y,&c);
         add(x,y,c);
    }
    cout<<Maxflow(ss,tt);
    return 0;
} 

by YBT_mail @ 2020-08-27 08:45:04

我贴的是第一次交的代码,有些地方还有漏洞,改过了还是没过。太蒻了


by 灵茶山艾府 @ 2020-08-27 08:53:13

flow+=dfs(s,100000000) 这个传小了吧,你看看数据范围


by Prean @ 2020-08-27 08:58:36

不开 ____ 见祖宗


by hanyuchen2019 @ 2020-08-27 09:34:10

不开 ____ 见祖宗


by YBT_mail @ 2020-09-17 15:27:19

调到我眼瞎


by YBT_mail @ 2020-09-17 15:30:09

不开long long见祖宗


by YBT_mail @ 2020-09-17 15:37:06

多谢


|