TLE+WA+RE求调
查看原帖
TLE+WA+RE求调
324412
Filberte楼主2024/1/4 12:47

33pts,知道一组TILE的数据死在EK()函数中的第二层for循环(两个注释之间)里,求助

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int inf = 1e9;
int n, m, S, T;
struct E{
    int ver, nxt, c, w;
}e[N << 1];int idx = 1;
int h[N];
void add(int u, int v, int c, int w){
    e[++idx].ver = v, e[idx].nxt = h[u];
    e[idx].c = c, e[idx].w = w;
    h[u] = idx;
    e[++idx].ver = u, e[idx].nxt = h[v];
    e[idx].c = 0, e[idx].w = -w;
    h[v] = idx;
    return ;
}
int mf[N], d[N], pre[N];
bool inq[N];
bool SPFA(){
    for(int i = 0;i < N;i++) mf[i] = 0, d[i] = inf, inq[i] = 0;
    d[S] = 0, mf[S] = inf;
    queue<int> q;
    q.push(S);inq[S] = 1;
    while(q.size()){
        int u = q.front(); 
        q.pop();
        inq[u] = 0;
        for(int i = h[u];i;i = e[i].nxt){
            int v = e[i].ver, c = e[i].c, w = e[i].w;
            if(d[u] + w < d[v] && c){
                d[v] = d[u] + w;
                pre[v] = i;
                mf[v] = min(mf[u], c);
                if(!inq[v]){
                    inq[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return mf[T] > 0;
}
int flow, cost;
void EK(){
    int cnt;
    while(SPFA()){
        //cout << cnt << "in\n";
        int u = T;
        while(u != S){
            int i = pre[u];
            e[i].c -= mf[T];
            e[i ^ 1].c += mf[T];
            u = e[i ^ 1].ver;  
        }
        //cout << cnt << "out\n";
        flow += mf[T];
        cost += mf[T] * d[T];
    }
}
int avg, a[N];
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%d",&a[i]);
        avg += a[i];
    }
    S = 0, T = n + 1;
    avg /= n;   
    for(int i = 1;i <= n;i++) a[i] -= avg;
    for(int i = 1;i <= n;i++){
        if(i == n){add(n, 1, inf, 1);add(1, n, inf, 1);}
        else{add(i, i + 1, inf, 1);add(i + 1, i, inf, 1);}
        if(a[i] > 0) add(S, i, a[i], 0);
        if(a[i] < 0) add(i, T, -a[i], 0);
    }
    EK();
    printf("%d\n",cost);
}
2024/1/4 12:47
加载中...