QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #870058 | #4809. Maximum Range | XuYueming | WA | 19ms | 12772kb | C++20 | 9.5kb | 2025-01-25 14:37:42 | 2025-01-25 14:37:53 |
Judging History
answer
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 100010;
struct node {
int to, nxt, len;
} edge[M << 1];
int head[N], tot = 1;
void add(int u, int v, int w) {
edge[++tot] = {
.to = v, .nxt = head[u], .len = w
}, head[u] = tot;
}
int n, m;
int dfn[N], low[N], timer;
int stack[N], top;
int scnt, sccno[N];
void tarjan(int u, int f) {
dfn[u] = low[u] = ++timer;
stack[++top] = u;
for (int i = head[u]; i; i = edge[i].nxt) {
if ((i ^ f) == 1) continue;
int v = edge[i].to;
if (!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
++scnt;
do {
int v = stack[top--];
sccno[v] = scnt;
// printf("%d: %d\n", scnt, v);
} while (stack[top + 1] != u);
}
}
int mx[N], mi[N], xp[N], ip[N];
// bool ins[N << 1], vis[N];
// bool dfs(int u, int fr, vector<int>& vec, int target) {
// vis[u] = true;
// if (u == target) return vec.emplace_back(u), true;
// for (int i = head[u]; i; i = edge[i].nxt) {
// if (i == (fr ^ 1)) continue;
// if (ins[i]) continue;
// int v = edge[i].to;
// if (vis[v]) continue;
// bool res = dfs(v, i, vec, target);
// if (res) {
// ins[i] = ins[i ^ 1] = true;
// vec.emplace_back(u);
// return true;
// }
// }
// return false;
// }
vector<int> ans;
int xxx, iii, u1, u2, v1, v2;
// bool intree[M << 1], vis[N];
// int FA[N], DOWN;
// void dfs(int u, int fr) {
// vis[u] = true;
// if (u == v1) FA[u1] = u, dfs(u1, xxx);
// if (u == u2 && fr != iii) FA[v2] = u, DOWN = v2, dfs(v2, iii ^ 1);
// if (u == v2 && fr != (iii ^ 1)) FA[u2] = u, DOWN = u2, dfs(u2, iii);
// for (int i = head[u]; i; i = edge[i].nxt) {
// if (i == (fr ^ 1)) continue;
// if (i == (xxx ^ 1)) continue;
// if (i == iii) continue;
// if (i == (iii ^ 1)) continue;
// int v = edge[i].to;
// if (vis[v]) continue;
// FA[v] = u;
// intree[i] = intree[i ^ 1] = true;
// dfs(v, i);
// }
// }
// bool can[N];
// int fff[N];
// bool dfs(int u) {
// if (can[u]) {
// // printf("fff[5] = %d\n", fff[5]);
// // printf("fff[4] = %d\n", fff[4]);
// for (int x = u; x; x = fff[x])
// ans.emplace_back(x);
// reverse(ans.begin(), ans.end());
// return true;
// }
// for (int i = head[u]; i; i = edge[i].nxt) {
// if (!intree[i]) continue;
// int v = edge[i].to;
// if (v == FA[u]) continue;
// bool rr = dfs(v);
// if (rr) {
// ans.emplace_back(u);
// return true;
// }
// }
// return false;
// }
struct Net_Max_Flow {
struct Graph {
struct node {
int to, flow, cap, nxt;
} edge[M << 1];
int tot = 1, head[N];
inline void add(int u, int v, int w) {
edge[++tot] = {v, 0, w, head[u]};
head[u] = tot;
}
inline node & operator [] (const int x) {
return edge[x];
}
} xym;
int n;
inline void init(int _n) {
n = _n, xym.tot = 1;
memset(xym.head + 1, 0x00, sizeof (int) * n);
}
inline void add(int u, int v, int fl) {
xym.add(u, v, fl), xym.add(v, u, 0);
}
int dpt[N], cur[N];
bool BFS(int S, int T) {
queue<int> Q;
memset(dpt + 1, 0x00, sizeof (int) * n);
dpt[S] = 1, Q.push(S);
while (!Q.empty()) {
int now = Q.front(); Q.pop();
// printf("now = %d, T = %d\n", now, T);
for (int i = xym.head[now]; i; i = xym[i].nxt) {
int to = xym[i].to;
if (!dpt[to] && xym[i].cap > xym[i].flow) {
dpt[to] = dpt[now] + 1;
Q.push(to);
}
}
}
return dpt[T];
}
int dfs(int now, int T, int lim) {
if (now == T || !lim) return lim;
int flow = 0;
for (int &i = cur[now]; i; i = xym[i].nxt) {
int to = xym[i].to;
if (dpt[to] != dpt[now] + 1) continue;
int res = dfs(to, T, min(lim - flow, xym[i].cap - xym[i].flow));
xym[i].flow += res, xym[i ^ 1].flow -= res;
flow += res;
if (flow == lim) break;
}
return flow;
}
long long solve(int S, int T) {
long long flow = 0;
while (BFS(S, T)) {
// puts("dfskldfuslitgudgfshgdfk");
memcpy(cur + 1, xym.head + 1, sizeof (int) * n);
flow += dfs(S, T, 2 - flow);
if (flow == 2) break;
}
return flow;
}
} yzh;
signed main() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
tarjan(i, 0);
for (int i = 1; i <= scnt; ++i) {
mx[i] = -0x3f3f3f3f;
mi[i] = 0x3f3f3f3f;
}
for (int u = 1; u <= n; ++u)
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (sccno[v] != sccno[u]) continue;
int w = edge[i].len;
// printf("====== %d\n", w);
int x = sccno[u];
if (w > mx[x])
mx[x] = w, xp[x] = i;
if (w < mi[x])
mi[x] = w, ip[x] = i;
}
int mm = 0, idx = -1;
for (int i = 1; i <= scnt; ++i)
if (mx[i] - mi[i] > mm) {
mm = mx[i] - mi[i];
idx = i;
}
printf("%d\n", mm);
int X = xp[idx], I = ip[idx];
u1 = edge[X].to, v1 = edge[X ^ 1].to;
u2 = edge[I].to, v2 = edge[I ^ 1].to;
if (u1 == v2) swap(u2, v2), I ^= 1;
if (v1 == u2) swap(u1, v1), X ^= 1;
if (v1 == v2) swap(u2, v2), I ^= 1, swap(u1, v1), X ^= 1;
fprintf(stderr, "(%d, %d): %d\n", u1, v1, edge[X].len);
fprintf(stderr, "(%d, %d): %d\n", u2, v2, edge[I].len);
iii = I, xxx = X;
int III = n + 1, XXX = n + 2;
yzh.init(n + 2);
yzh.add(III, u1, 1);
yzh.add(III, v1, 1);
yzh.add(u2, XXX, 1);
yzh.add(v2, XXX, 1);
for (int u = 1; u <= n; ++u)
if (sccno[u] == idx)
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (sccno[v] != idx) continue;
if (v > u) continue;
// puts("dfsdfsdfsdfsdfs");
yzh.add(u, v, 1);
yzh.add(v, u, 1);
}
int res = yzh.solve(III, XXX);
fprintf(stderr, "maxflow = %d\n", res);
assert(res == 2);
int TTTTTTTT = 0;
for (int u = u1; u != XXX; ) {
ans.push_back(u);
for (int i = yzh.xym.head[u]; i; i = yzh.xym.edge[i].nxt) {
int v = yzh.xym.edge[i].to;
if (yzh.xym.edge[i].flow != 1) continue;
if (v == III) continue;
if (v == XXX) {
TTTTTTTT = u2 ^ v2 ^ u;
}
u = v;
break;
}
}
vector<int> tmp;
for (int u = TTTTTTTT; u != III; ) {
// printf("u = %d\n", u);
tmp.push_back(u);
for (int i = yzh.xym.head[u]; i; i = yzh.xym.edge[i].nxt) {
int v = yzh.xym.edge[i].to;
if (yzh.xym.edge[i ^ 1].flow != 1) continue;
if (v == XXX) continue;
u = v;
break;
}
}
reverse(tmp.begin(), tmp.end());
for (int x : tmp) ans.push_back(x);
// intree[X] = intree[X ^ 1] = true;
// intree[I] = intree[I ^ 1] = true;
// dfs(v1, 0);
// // for (int u = 1; u <= n; ++u)
// // printf(">>> %d %d\n", u, FA[u]);
// queue<int> Q;
// Q.push(v1), can[v1] = true;
// while (!Q.empty()) {
// int u = Q.front(); Q.pop();
// for (int i = head[u]; i; i = edge[i].nxt) {
// if (!intree[i]) continue;
// int v = edge[i].to;
// if (v == FA[u]) continue;
// Q.push(v);
// }
// if (can[u]) {
// for (int i = head[u]; i; i = edge[i].nxt) {
// if (intree[i]) continue;
// int v = edge[i].to;
// if (can[v]) continue;
// can[v] = true;
// fff[v] = u;
// }
// }
// }
// // printf("DOWN = %d\n", DOWN);
// bool rerrr = dfs(DOWN);
// assert(rerrr);
// for (int x = FA[DOWN]; FA[x]; x = FA[x])
// ans.emplace_back(x);
// assert(can[DOWN]);
printf("%d\n", int(ans.size()));
for (int x : ans) printf("%d ", x);
// vector<int> vec1, vec2;
// ins[X] = ins[X ^ 1] = true;
// ins[I] = ins[I ^ 1] = true;
// bool res1 = dfs(u1, 0, vec1, u2);
// assert(res1);
// memset(vis, 0x00, sizeof(vis));
// bool res2 = dfs(v2, 0, vec2, v1);
// if (!res2) {
// swap(u2, v2);
// fprintf(stderr, "(%d, %d): %d\n", u1, v1, edge[X].len);
// fprintf(stderr, "(%d, %d): %d\n", u2, v2, edge[I].len);
// vec1.clear();
// memset(vis, 0x00, sizeof(vis));
// memset(ins, 0x00, sizeof(ins));
// ins[X] = ins[X ^ 1] = true;
// ins[I] = ins[I ^ 1] = true;
// res1 = dfs(u1, 0, vec1, u2);
// assert(res1);
// memset(vis, 0x00, sizeof(vis));
// res2 = dfs(v2, 0, vec2, v1);
// assert(res2);
// }
// printf("%d\n", int(vec1.size() + vec2.size()));
// // assert(res2);
// for (int x : vec2) printf("%d ", x);
// for (int x : vec1) printf("%d ", x);
// // puts("");
// // reverse(vec2.begin(), vec2.end());
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12108kb
input:
5 7 1 2 1 1 3 -2 2 3 1 3 4 3 4 5 1 1 5 -1 2 5 2
output:
5 4 3 4 5 1
result:
ok ok
Test #2:
score: -100
Wrong Answer
time: 19ms
memory: 12772kb
input:
99997 100000 12238 99016 352755196 99016 25485 -412473602 25485 2440 991507552 2440 31171 -181894654 36970 2440 -800167579 2440 41865 -148191946 96629 31171 847888506 36970 95740 395546542 27992 2440 647886610 99016 29557 369124914 80795 27992 -673871966 36970 3509 573208857 57672 29557 874406776 41...
output:
1959330954 37 96048 4697 44442 68883 69259 57672 29557 99016 25485 2440 31171 94991 86274 74677 92617 86665 76022 72089 22074 96230 87712 51491 72825 3463 84407 67966 89628 84997 54073 68523 30288 88289 37694 96778 46301 34883 95092
result:
wrong answer Edge 31171-94991 does not appear in original graph