46分代码求调

Fated_Shadow @ 2023-02-09 19:53:34

by Fated_Shadow @ 2023-02-09 19:53:54

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#define min(a,b) a < b ? a : b
using namespace std;

const int N = 210;
const int M = 1e4 + 10;

int  n,m,s,t;
int h[N],e[M],ne[M],now[N],idx = 0;
long long w[M];
int q[N],l,r;
int dep[N];

inline long long read(){
    long long res = 0,f = 1;
    char ch = getchar();
    while(! isdigit(ch)){
    if(ch == '-')
    f = -1,ch = getchar();
    }
    while(isdigit(ch)){
    res = res * 10 + ch - 48,ch = getchar();
    }
    return res * f;
}
inline void print(long long x){
    if(x >= 10)
    print(x / 10);
    putchar(x % 10 + 48);
}
void add(int a,int b,long long c){
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

bool bfs()
{
    memset(q,0,sizeof q);
    memset(dep,0,sizeof dep);
    memcpy(now,h,sizeof now);
    l = 0,r = -1;
    q[++ r] = s;
    dep[s] = 1;
    while(l <= r)
    {
        long long u = q[l];
        ++ l;
        for(long long i = h[u];i != -1;i = ne[i])
        {
            long long v = e[i];
            if(w[i] && ! dep[v])
            {
                dep[v] = dep[u] + 1;
                q[++ r] = v;
                if(v == t) return true;
            }
        }
    }
    return false;
}

long long dfs(int u,long long last)
{
    if(u == t || ! last) return last;
    long long res = last;
    for(int i = now[u];i != -1;i = ne[i])
    {
        int v = e[i];
        now[u] = i;
        if(dep[v] == dep[u] + 1 && w[i])
        {
            long long k = min(res,w[i]);
            long long num = dfs(v,k);
            w[i] -= num,w[i ^ 1] += num;
            res -= num;
            if(! res) break;
        }

    }
    return last - res;
}

int main()
{
    memset(h,-1,sizeof h);
    n = read(),m = read(),s = read(),t = read();
    int x,y;
    long long z;
    while(m --)
    {
        x = read(),y = read(),z = read();
        add(x,y,z),add(y,x,0);
    }
    long long ans = 0;
    while(bfs()) ans += dfs(s,1e9);
    print(ans);
    return 0;
}

by lzyqwq @ 2023-02-09 19:57:35

@_FatedShadow 看到你这个感触很深，自己也因为这个错误调了通宵

题目中流量有 2^31 之大，你dfs每次源点给1e9的流量，是不能把当前残量网络增广路找完的，导致增广当前最短路要bfs好几遍，效率低下

建议改成1e18，如果还TLE建议炸点和当前弧

by Fated_Shadow @ 2023-02-09 20:00:29

感谢 dalao 在线指导（虽然还是没有过）（悲）！！！

应该是出了些奇怪的锅

by Fated_Shadow @ 2023-02-09 20:18:37

新测，本地 AC 提交 TLE。

by Fated_Shadow @ 2023-02-09 20:32:26

谢谢 dalao，最后查清了：快读有锅

（赶紧反思这种事真的是我该干的吗？）

感谢 @蒟蒻·廖子阳

by lzyqwq @ 2023-02-09 20:53:59

@_FatedShadow 不过我说的这个确实是一个问题，您可以试试

by Fated_Shadow @ 2023-02-09 21:08:09

@蒟蒻·廖子阳，之前试过了，不开 10^{18} 应该不会爆吧...

题目中给了，边权 < 2^{31}，而 last 记录单次路径最小值流量的最大值，应该不会爆 int (10^{9})（至于返回值是数据类型 int 和 long long 对不上就是另一回事了）

另附：没开 10^{18} 开了 10^{9} AC记录 link

by Fated_Shadow @ 2023-02-09 21:08:28

再来，@蒟蒻·廖子阳

by lzyqwq @ 2023-02-09 21:12:22

@_FatedShadow SPOJ 上有一道数据强一点但不要 HLPP 的 Dinic 模板题 Fast Maxflow，你如果把 1e18 打成 1e9 就会 TLE

by lzyqwq @ 2023-02-09 21:13:45

@蒟蒻·廖子阳 打错了 叫 FASTFLOW https://www.luogu.com.cn/problem/SP4110