社区讨论
新人求助,修车那题,本机没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
调不出来了qwq
回复
共 25 条回复,欢迎继续交流。
正在加载回复...