求助，dinic迷之MLE。

zzzYheng @ 2021-02-24 14:28:00

#include<bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
int n,m,s,t;
int a[10005][3],last[250],len;
int d[250];
void add(int x,int y,int z){
    len++;
    a[len][0]=x;
    a[len][1]=last[y];
    a[len][2]=z;
    last[y]=len;
}
int bfs(){
    memset(d,0,sizeof(d));
    int i,j;
    queue<int> q;
    d[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(i=last[x];i;i=a[i][1]){
            int y=a[i][0];
            if(a[i][2]>0&&!d[y]){
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    return d[t];
}
int dfs(int s,int flow){
    int i,j;
    int tmp1=0,tmp2=flow;
    if(s==t)return flow;
    for(i=last[s];i;i=a[i][1]){
        int y=a[i][0];
        if(d[y]=d[s]+1&&a[i][2]>0){
            int f=dfs(y,min(flow,a[i][2]));
            tmp2-=f;
            tmp1+=f;
            a[i][2]-=f;
            a[i^1][2]+=f;
        }
        if(tmp2<=0)break;
    }
    return tmp1;
}
int main(){
    int i,j;
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(y,x,z);
        add(x,y,0);
    }
    long long ans=0;
    while(bfs()){
        ans+=dfs(s,INF);
    }
    cout<<ans;
    return 0;
}

by Guoyh @ 2021-02-24 14:40:37

@zhouyuheng2009 len的初值应该是1吧

by zzzYheng @ 2021-02-24 14:44:57

void add(int x,int y,int z){
    len++;
    a[len][0]=x;
    a[len][1]=last[y];
    a[len][2]=z;
    last[y]=len;
}

我是先++的

by zzzYheng @ 2021-02-24 14:45:40

@Guoyh

by Egg_eating_master @ 2021-02-24 14:57:39

边的编号是(2,3),(4,5)\cdots成对变换，所以1那条边不能存储

by zmza @ 2021-02-24 18:25:41

@zhouyuheng2009

#include<bits/stdc++.h>
#define int long long//开long long
using namespace std;
const int INF=0x7fffffffffff;
int n,m,s,t;
int a[10005][3],last[250],len = 1;//len=1
int d[250];
void add(int x,int y,int z){
    len++;
    a[len][0]=x;
    a[len][1]=last[y];
    a[len][2]=z;
    last[y]=len;
}
int bfs(){
    memset(d,0,sizeof(d));
    int i,j;
    queue<int> q;
    d[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(i=last[x];i;i=a[i][1]){
            int y=a[i][0];
            if(a[i][2]>0&&!d[y]){
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }
    return d[t];
}
int cur[10005];//当前弧优化
int dfs(int s,int flow){
    int tmp1=0;
    if(s==t)return flow;
    for(int &i=cur[s];i;i=a[i][1]){
        int y=a[i][0];
        if(d[y]==d[s]+1&&a[i][2]>0){//把=改成==
            int f=dfs(y,min(flow,a[i][2]));
            flow-=f;//直接用flow
            tmp1+=f;
            a[i][2]-=f;
            a[i^1][2]+=f;
            if(flow == 0)break;
        }
    }
    return tmp1;
}
signed main(){
    int i,j;
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(y,x,z);
        add(x,y,0);
    }
    long long ans=0;
    while(bfs()){
        for(int i = 1; i <= n; i++)cur[i] = last[i];
        ans+=dfs(s,INF);
    }
    cout<<ans;
    return 0;
}

by zzzYheng @ 2021-02-25 14:07:02

蟹蟹 @张茗祖

by zzzYheng @ 2021-02-25 15:26:58

本人已AC，此帖终结。