社区讨论

新人求助,修车那题,本机没AC提交RE

P2053[SCOI2007] 修车参与者 6已保存回复 25

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
25 条
当前快照
1 份
快照标识符
@mi7rs77k
此快照首次捕获于
2025/11/21 02:33
4 个月前
此快照最后确认于
2025/11/21 02:45
4 个月前
查看原帖
RUN ID15886373
以下是我的代码:
CPP
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#define maxn 605
#define maxm 60005
#define Inf (0x3f3f3f3f)
inline int read() {
    int d=0;char ch=getchar();while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)){d=d*10+ch-48;ch=getchar();}return d;
}
inline int mmin(int x, int y) {
    return x < y ? x : y;
}

int M, N;
int mp[65][15];
int n, s, t;
int head[maxn], ver[maxm], edge[maxm], dis[maxm], nxt[maxm], tot = -1;
int h[maxn], cur[maxn], cnt, cst;
std::queue<int> q;
bool vis[maxn];
#define val(u, v) ((u-1)*N+v)
#define add(u, v, w, z) ver[++tot] = v, edge[tot] = w, dis[tot] = z, nxt[tot] = head[u], head[u] = tot,\
                        ver[++tot] = u, edge[tot] = 0, dis[tot] = -z, nxt[tot] = head[v], head[v] = tot

bool spfa() {
    memset(h, 0x3f, sizeof(h)), memcpy(cur, head, sizeof(cur));
    q.push(s), h[s] = 0;
    int u, v;
    while(!q.empty()) {
        u = q.front(), q.pop();
        vis[u] = 0;
        for(int p = head[u]; p != -1; p = nxt[p]) {
            v = ver[p];
            if(edge[p] > 0 && h[v] > h[u] + dis[p]) {
                h[v] = h[u] + dis[p];
                if(!vis[v]) q.push(v), vis[v] = 1;
            }
        }
    }
    return h[t] < Inf;
}

int dfs(int u, int fl) {
    if(u == t) return fl;
    int rt = 0, now, v;
    vis[u] = 1;
    for(int p = cur[u]; p != -1; p = nxt[p]) {
        cur[u] = p, v = ver[p];
        if(edge[p] > 0 && (!vis[v]) && h[v] == h[u] + dis[p]) {
            now = dfs(v, mmin(edge[p], fl-rt));
            edge[p] -= now;
            edge[p^1] += now;
            cst += now*dis[p];
            rt += now;
            if(fl == rt) break;
        }
    }
    vis[u] = 0;
    if(!rt) h[u] = Inf;
    return rt;
}

int main() {
    M = read(), N = read();
    memset(head, -1, sizeof(head));
    n = N*M+N+2;
    s = n-1, t = n;
    for(int i = 1; i <= N; ++i)
    for(int j = 1; j <= M; ++j) {
        mp[i][j] = read();
        for(int k = 1; k <= N; ++k)
            add(N*M+i, val(j, k), 1, mp[i][j]*k);
    }
    for(int i = 1; i <= N; ++i) {
        add(s, N*M+i, 1, 0);
        for(int j = 1; j <= M; ++j)
            add(val(j, i), t, 1, 0);
    }
    while(spfa()) cnt += dfs(s, Inf);
    printf("%.2lf", (double)cst/(double)N);
    return 0;
}
话说其它9个点都AC了然而#2RE了 qwq
调不出来了qwq

回复

25 条回复,欢迎继续交流。

正在加载回复...