QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#287587 | #5048. All Pair Maximum Flow | jeefy | WA | 3ms | 28048kb | C++14 | 2.2kb | 2023-12-20 19:43:05 | 2023-12-20 19:43:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int N = 4e5 + 7, inf = 1e9, mod = 998244353;
struct pli {
lint first, second;
bool operator < (const pli &p) const {
return first != p.first ? first < p.first : second < p.second;
}
};
int grp[N], siz[N];
int find(int x) {
return grp[x] == x ? x : grp[x] = find(grp[x]);
}
set<pli> cov, E[N];
int x[N], y[N], rem[N];
lint w[N];
void del(int e) {
cov.erase({w[e], e});
E[x[e]].erase({y[e], e});
E[y[e]].erase({x[e], e});
// cerr << "Del E " << e << ": " << x[e] << " - " << y[e] << " (" << w[e] << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(false);
int n, m; cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> x[i] >> y[i] >> w[i];
if (x[i] > y[i]) swap(x[i], y[i]);
if (x[i] + 1 == y[i] || (x[i] == 1 && y[i] == n)) cov.insert({w[i], i});
if (x[i] == 1 && y[i] == n) swap(x[i], y[i]);
E[x[i]].insert({y[i], i}), E[y[i]].insert({x[i], i});
// cerr << "Read " << i << x[i] << y[i] << " done \n";
}
int T = m - (n - 1);
while (T--) {
int e = cov.begin()->second;
// cerr << "Pop E " << e << " !\n";
del(e), rem[e] = 1;
int cur = x[e], prv = y[e];
while (cur != y[e]) {
auto it = E[cur].upper_bound({prv, inf}); // 顺时针遍历
if (it == E[cur].end()) it = E[cur].begin();
int i = it->second;
prv = cur, cur = it->first;
// cerr << "Nxt E " << i << '\n';
if (cov.find({w[i], i}) == cov.end()) {
w[i] += w[e];
cov.insert({w[i], i});
if (x[i] != cur) swap(x[i], y[i]); // 修改方向
// cerr << "Make IN " << i << ": " << x[i] << " - " << y[i] << '\n';
} else {
del(i);
w[i] += w[e];
}
// cerr << "Cur to " << cur << " prv " << prv << '\n';
}
}
cov.clear();
for (int i = 1; i <= m; ++i) {
if (!rem[i]) cov.insert({-w[i], i});
}
for (int i = 1; i <= n; ++i) grp[i] = i, siz[i] = 1;
int ans = 0;
for (auto it : cov) {
int e = it.second;
// cerr << "Rest e " << e << ": " << x[e] << ", " << e[y] << " (" << w[e] << '\n';
int u = find(x[e]), v = find(y[e]);
if (u == v) continue;
ans = (ans + 1ll * w[e] % mod * siz[u] % mod * siz[v]) % mod;
grp[u] = v, siz[v] += siz[u];
} cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 25988kb
input:
6 8 1 2 1 2 3 10 3 4 100 4 5 1000 5 6 10000 6 1 100000 1 4 1000000 1 5 10000000
output:
12343461
result:
ok 1 number(s): "12343461"
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 28048kb
input:
20 30 5 7 9066926 13 15 636587393 1 12 234024833 7 11 863853881 7 9 961926707 12 20 525748907 7 10 217196987 15 20 715248370 17 19 577652480 16 19 78750484 1 2 216519168 2 3 26083428 3 4 381598120 4 5 78513523 5 6 106643887 6 7 20069507 7 8 467260856 8 9 383736316 9 10 400897545 10 11 404258163 11 1...
output:
176644596
result:
wrong answer 1st numbers differ - expected: '858325335', found: '176644596'