假的Dinic

7KByte @ 2020-06-17 16:53:01

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 205
#define M 5005
typedef long long ll; 
using namespace std;
int h[N],tot=1;
struct edge{
    int to,nxt,cap;
}e[M<<1];
void add(int x,int y,int z){
    e[++tot].nxt=h[x];h[x]=tot;e[tot].cap=z;e[tot].to=y;
}
int n,m,s,t,d[N],cur[N];
queue<int>q;
bool bfs(){
    memset(d,0,sizeof(d));
    d[s]=1;q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        cur[x]=h[x];
        for(int i=h[x];i;i=e[i].nxt)
            if(e[i].cap&&!d[e[i].to])
                d[e[i].to]=d[x]+1,q.push(e[i].to);
    }
    return d[t];
}
int dfs(int x,int flow){
    if(x==t)return flow;
    int res=flow;
    for(int &i=cur[x];i;i=e[i].nxt){
        if(!res)return flow;
        if(e[i].cap&&d[x]+1==d[e[i].to]){
            int now=dfs(e[i].to,min(res,e[i].cap));
            if(!now)d[e[i].to]=1;
            else{
                e[i].cap-=now;
                e[i^1].cap+=now;
                res-=now;
            }
        }
    }
    return flow-res;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    rep(i,1,m){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,0);
    }
    ll ans=0;
    while(bfs())ans+=dfs(s,0x7fffffff);
    printf("%lld\n",ans);
    return 0;
}

by LeavingZzz @ 2020-06-17 16:54:41

@Inf_Voltage 我觉得...是不是..要把 e[i].cap 也开个ll啊（
（反正我开了）

by WYXkk @ 2020-06-17 16:55:27

@Inf_Voltage

ans+=dfs(s,0x7fffffff);

max 开小了吧，开 0x7fffffffffffffffll才够吧？

by 7KByte @ 2020-06-17 16:55:36

@_Leaving 估计不是ll的问题，我Define了ll还是TLE

by WYXkk @ 2020-06-17 16:56:00

建议把所有涉及到 flow 的全部开 long long

by 7KByte @ 2020-06-17 16:57:09

@WYXkk 记录还是TLE

by smarthehe @ 2020-06-17 17:00:07

我也遇到同样情况了，和朋友代码对着找茬才发现 /kk

int dfs(int x,int flow){
    if(x==t)return flow;
    int res=flow;
    for(int &i=cur[x];i;i=e[i].nxt){
        //if(!res)return flow; <--原来在这里
        if(e[i].cap&&d[x]+1==d[e[i].to]){
            int now=dfs(e[i].to,min(res,e[i].cap));
            if(!now)d[e[i].to]=1;
            else{
                e[i].cap-=now;
                e[i^1].cap+=now;
                res-=now;
            }
        }
        if(!res)return flow;// <-- 应该在这里
    }
    return flow-res;
}

@Inf_Voltage

by 7KByte @ 2020-06-17 17:04:14

@smarthehe 已经调出来，谢谢神仙

by 7KByte @ 2020-06-17 17:09:59

@smarthehe 位置变一下貌似没有区别啊

by AgrumeStly @ 2020-06-17 17:16:09

@Inf_Voltage 有区别，一个是当!res时直接退出了，另一个是先执行完

if(e[i].cap&&d[x]+1==d[e[i].to]){
            int now=dfs(e[i].to,min(res,e[i].cap));
            if(!now)d[e[i].to]=1;
            else{
                e[i].cap-=now;
                e[i^1].cap+=now;
                res-=now;
            }
        }

这一堆，然后再当!res时退出。

by 几何之舞丶 @ 2020-06-17 17:30:35

jie lou wo de dai ma bu xi yang 80fen xi le yang qi 0fen zhe shi wei shen me ne ?