求助MLE原因主要有哪些
查看原帖
求助MLE原因主要有哪些
394621
kikiCurry楼主2020/12/1 18:54

数组开的不大,应该是没有超的吧orz,还有什么情况下会全MLE呀?代码如下,大佬们不愿看代码,说说其他可能的原因也行啊orz

#include<bits/stdc++.h>
using namespace std;

const int N = 110, M = 2010;
const int INF = 0x3f3f3f3f;

int h[N], to[M], ne[M], idx;
double f[M], f_bak[M];
int q[N], level[N], cur[N];

int n, m, P, S = 1, T;
int maxflow, maxCost = -1;

void add(int x, int y, int z){
    to[idx] = y, f[idx] = z, ne[idx] = h[x], h[x] = idx++;
    to[idx] = x, f[idx] = 0, ne[idx] = h[y], h[y] = idx++;
}

bool bfs(){
    int tt = 0, hh = 0;
    memset(level, -1, sizeof level);
    //源点入队
    q[0] = S, level[S] = 0;
    while(hh <= tt){
        int now = q[hh ++];
        cur[now] = h[now];
        for(int i = h[now];~i;i = ne[i]){
            int tv = to[i];
            if(level[tv] < 0 && f[i]){ //未访问过 且 有残量
                level[tv] = level[now] + 1;
                q[++tt] = tv;
            }
        }
    }
    return level[T] != -1;
}

double dfs(int now, double flow){
    if(now == T) return flow;
    double used = 0;
    for(int i = cur[now];~i;i = ne[i]){
        cur[now] = i; //更新当前弧
        int tv = to[i];
        double tmpflow = 0;
        if(level[tv] = level[now] + 1 && f[i]){ //下一层级 且有残量
            if(tmpflow = dfs(tv, min(flow-used, f[i]))){
                used += tmpflow;
                //更新残量网络
                f[i] -= tmpflow;
                f[i^1] += tmpflow;
                if(used == flow) break;
            }
        }
    }
    return used;
}

double dinic(){
    double ans = 0;
    while(bfs()){
        int ff;
        while(ff = dfs(S, INF)){
            ans += ff;
        }
    }
    return ans;
}

int main(){
    scanf("%d%d%d", &n, &m, &P);
    T = n;
    memset(h, -1, sizeof h);
    for(int i = 0;i < m;i ++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    for(int i = 0;i < idx;i ++) f_bak[i] = f[i];
    maxflow = dinic();
    printf("%.0f\n", maxflow);

    double l = 0, r = 50000;
    double tmpMaxflow;
    while(r-l > 1e-6){
        double mid = (l+r)/2.0;
        for(int i = 0;i < idx;i ++) f[i] = min(f_bak[i], mid);
        tmpMaxflow = dinic();
        if(fabs(tmpMaxflow - maxflow) < 1e-6) r = mid; //存在满足要求的可行流时
        else l = mid;
    }
    printf("%.4f\n", l*P);
}
2020/12/1 18:54
加载中...