咱们的程序怎么也停不下来了

P3376 【模板】网络最大流

王茗仟 @ 2022-11-04 20:28:48


#define int long long 
#define re  register
#define in inline
#define max(a,b) ((a)>(b)?a:b)
#define min(a,b) ((a)<(b)?a:b)
using namespace std;
const int MAXN=1e4+10;
const int MAXM=2e5+19;
const int INF=0x3f3f3f3f3f;

in int read(){
    re int x=0,f=0;re char c=getchar();
    while(!isdigit(c)) f|=(c=='-'),c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f?-x:x;
}

int n,m,s,t,dis[MAXN],cur[MAXN];

struct edge{
    int u,v,w;
    int nx;
}e[MAXM];
int head[MAXN],tot;

in void  add(int u,int v,int w){
    e[tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nx=head[u];
    head[u]=tot++;
}

bool bfs(){
//广搜一下测一下剩下点的深度,顺便找出增广路
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(s);
    dis[s]=0;
    cur[s]=head[s];//cur是当前弧优化的宝贝
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=e[i].nx){
            int v=e[i].v;
            if(dis[v]==-1&&e[i].w){
                dis[v]=dis[u]+1;
                cur[v]=head[v];
                if(v==t){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;//不存在增广路了,可以结束le
}

int dfs(int u,int lim){
// 当前节点     能增加的最大流量
//深搜??也就是增广一下,给下流
    if(u==t){
        return lim;
    }

    int flow=0;//从u点分出去的
    for(int i=cur[u];~i;i=e[i].nx){
        cur[i]=i;//当前弧优化,很新对你来说,(走过就不再走了)
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].w){
            int minf=dfs(v,min(e[i].w,lim-flow));//求要给v多少
//limit-flow给这条边能分的最多有多少
            e[i].w-=minf;
            e[i^1].w+=minf;
            flow+=minf;
            if(flow==lim){
            //全分完了直接结束吧
                return flow;
            }
        }   
    }
    return flow;

}

int dinic(){
    int ans=0;
    while(bfs()){
    //  cout<<ans<<endl;
        ans+=dfs(s,INF);
    }
    return ans;
}

signed main(){
    n=read();m=read();s=read();t=read();
    memset(head,-1,sizeof(head));
    for(re int i=1;i<=m;i++){
        int u,v,w;
        u=read();v=read();w=read();
        add(u,v,w);add(v,u,0);
    }
    cout<<dinic()<<endl;
    return 0;
}

by 王茗仟 @ 2022-11-04 20:29:09

他是怎样陷入无限循环的


by treeqwq @ 2022-11-04 20:31:34

加了当前弧优化就必须改成

    for(int i=cur[u];~i&&flow<lim;i=e[i].nx){
        cur[i]=i;//当前弧优化,很新对你来说,(走过就不再走了)
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].w){
            int minf=dfs(v,min(e[i].w,lim-flow));//求要给v多少
//limit-flow给这条边能分的最多有多少
            e[i].w-=minf;
            e[i^1].w+=minf;
            flow+=minf;
            if(flow==lim){
            //全分完了直接结束吧
                return flow;
            }
        }   
    }

要不然 cur 会一直更新


by treeqwq @ 2022-11-04 20:31:44

@王茗仟


by IceYukino @ 2022-11-04 20:35:25

没看出来您改了啥?


by 王茗仟 @ 2022-11-04 20:35:55

@LSOT

您是不是只改了for里面那一点


by treeqwq @ 2022-11-04 20:36:20

@王茗仟 对


by 王茗仟 @ 2022-11-04 20:37:42

@LSOT

并不是那里的问题


by 王茗仟 @ 2022-11-04 20:38:46

@gqh_juruo

他改了for的条件


by 野生林登万 @ 2022-11-04 20:39:01

您的for(int i=head[u];~i;i=e[i].nx)为什么不写成for(int i=head[u];i;i=e[i].nx)呢?咱不知道为什么要写~i
修改以后答案依然不对,但是不会TLE了,另外,可以增加剪枝:

if(u==t || lim == 0){
   return lim;
}

by treeqwq @ 2022-11-04 20:39:13

@王茗仟 啊,那就不知道了,不过你不该这里也过不去(((


| 下一页