70分求解谢谢大佬

浥轻尘 @ 2019-07-19 20:04:33

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int x,y,tot,z,n,m,s,t,maxflow,dep[1000010];
const int inf=9999999;
struct node{
    int to,v,next;
}edge[1000050];
int head[1000050];
queue<int>q;
void add(int x,int y,int z){
    edge[++tot].to=y;
    edge[tot].v=z;
    edge[tot].next=head[x];
    head[x]=tot;
}
int bfs(){
    while(!q.empty()) q.pop();
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    do{
            int u=q.front();
        q.pop();
        for(int i=head[u];i;i=edge[i].next){
            if(edge[i].v&&dep[edge[i].to]==0){
                dep[edge[i].to]=dep[u]+1;
                q.push(edge[i].to);
            }
        }
    }while(!q.empty());

    if(dep[t]!=0) return 1;
    else return 0;
}
int dfs(int u,int dis){
    if(u==t) return dis;
    for(int i=head[u];i;i=edge[i].next){
        if((dep[edge[i].to]==dep[u]+1)&&(edge[i].v!=0)){
            int di=dfs(edge[i].to,min(dis,edge[i].v));
            if(di>0){
                edge[i].v-=di;
                edge[i^1].v+=di;
                return di;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs()){
        while(int ti=dfs(s,inf))
         ans+=ti;   
    }
    return ans;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    printf("%d\n",dinic());
}

by 冥诺在线发呆 @ 2019-07-19 20:07:10

tot初始化1

by LordLeft @ 2019-07-19 20:07:24

@浥轻尘

E?

你存边是从1开始的,i^1 这是错误的写法

by 冥诺在线发呆 @ 2019-07-19 20:07:33

@浥轻尘 要从2开始

by huayucaiji @ 2019-07-19 20:09:06

@浥轻尘 从0或2开始

by 冥诺在线发呆 @ 2019-07-19 20:10:30

@浥轻尘 从1开始的话1^1=0，然而没有0这条边。我就是这么WA的

by Smile_Cindy @ 2019-07-19 20:20:53

@浥轻尘

帮你改了一下

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int x,y,tot,z,n,m,s,t,maxflow,dep[1000010];
const int inf=9999999;
struct node{
    int to,v,next;
}edge[1000050];
int head[1000050];
queue<int>q;
void add(int x,int y,int z){
    edge[tot].to=y;
    edge[tot].v=z;
    edge[tot].next=head[x];
    head[x]=tot;
    tot++;
}
int bfs(){
    while(!q.empty()) q.pop();
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    do{
            int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next){
            if(edge[i].v&&dep[edge[i].to]==0){
                dep[edge[i].to]=dep[u]+1;
                q.push(edge[i].to);
            }
        }
    }while(!q.empty());

    if(dep[t]!=0) return 1;
    else return 0;
}
int dfs(int u,int dis){
    if(u==t) return dis;
    for(int i=head[u];i!=-1;i=edge[i].next){
        if((dep[edge[i].to]==dep[u]+1)&&(edge[i].v!=0)){
            int di=dfs(edge[i].to,min(dis,edge[i].v));
            if(di>0){
                edge[i].v-=di;
                edge[i^1].v+=di;
                return di;
            }
        }
    }
    return 0;
}
int dinic(){
    int ans=0;
    while(bfs()){
        while(int ti=dfs(s,inf))
         ans+=ti;   
    }
    return ans;
}
int main(){
    memset(head,-1,sizeof(head)); 
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,0);
    }
    printf("%d\n",dinic());
}

by 浥轻尘 @ 2019-07-20 18:19:31

@冥诺在线发呆 十分感谢！！！

by 浥轻尘 @ 2019-07-20 18:19:53

@Alpha 谢谢大佬%%%%

by 浥轻尘 @ 2019-07-20 18:20:06

@huayucaiji 好的谢谢！！！

by lsy263 @ 2019-07-30 23:32:12

@浥轻尘 考古，正在学网络流，同样的错误，然而我有个建议，您也可以写成edge[i+(i&1)]，依旧使用从1开始存边