求助玄学问题

P3376 【模板】网络最大流

AfterFullStop @ 2023-08-04 22:13:50

这是一份#10会TLE的代码:

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const ll maxn=2e2+5,maxm=1e4+5,inf=2147483647;
int n,m,s,t;
int cnt,head[maxn],nxt[maxm],to[maxm];
ll bq[maxm];
void add(int u,int v,int w){
    ++cnt;
    to[cnt]=v;
    nxt[cnt]=head[u];
    bq[cnt]=w;
    head[u]=cnt;
}
int flag[maxn][maxn];
ll flow;
ll dis[maxn],pre[maxn];
bool vis[maxn];
bool bfs(){
    memset(vis,0,sizeof(vis));
    for(ri i=1;i<=n;i++)dis[i]=inf;
    memset(pre,0,sizeof(pre));
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(ri e=head[u];e;e=nxt[e]){
            int v=to[e];
            ll w=bq[e];
            if(!w||vis[v])continue;
            pre[v]=u;
            dis[v]=min(dis[u],w);
            vis[v]=1;
            q.push(v);
            if(v==t)return 1;
        }
    }return 0;
}
void update(){
    int v=t;
    while(v^s){
        int u=pre[v];int b=flag[u][v];
        bq[b]-=dis[t];bq[b^1]+=dis[t];
        v=u;
    }flow+=dis[t];
}
void EK(){
    while(bfs()){
        update();
    }
}
signed main(){
    //freopen("lg.in","r",stdin);
    //freopen("lg.out","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n>>m>>s>>t;
    cnt=1;
    for(ri i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        if(flag[u][v]){
            bq[flag[u][v]]+=w;
        }else{
            add(u,v,w);
            flag[u][v]=cnt;
            add(v,u,0);
        }
    }
    EK();
    cout<<flow;
    //fclose(stdout);
    return 0;
}

可是当我把 if(!w||vis[v])continue; 改成 if(w<=0||vis[v])continue; 时,居然神奇的AC了

这也就意味着有w是负的,但是似乎没有一个地方会把w变负,于是就蒙圈了。

本来想着可能是炸了int,结果define了还是TLE

哪位大佬能解释一下?谢谢


by _Haoomff_ @ 2023-08-05 08:00:43

@ChrysanthBlossom 我感觉不是的,!w 表示的是 w 不为 0,那么也就可以为正数,正数的时候 continue……


by AfterFullStop @ 2023-08-05 08:04:51

@Haoomff 可是我把!w改成w==0照样会T(


by _Haoomff_ @ 2023-08-05 08:06:11

@ChrysanthBlossom 说明会出现负数

bq[b]-=dis[t];

这步可能会减出负吧


by AfterFullStop @ 2023-08-05 08:14:21

@Haoomff

可是理论上来说bq[e]应该比dis[t]要大啊。

照这样看可能是flag整错了,但好像也没问题啊


by 阿丑 @ 2023-08-05 08:20:10

反向边也要赋 flag


by AfterFullStop @ 2023-08-05 08:39:41

@阿丑 谢谢,wssb


|