QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287542#5048. All Pair Maximum FlowjeefyWA 4ms24084kbC++142.2kb2023-12-20 18:39:082023-12-20 18:39:08

Judging History

你现在查看的是最新测评结果

  • [2023-12-20 18:39:08]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:24084kb
  • [2023-12-20 18:39:08]
  • 提交

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});
	}

	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: 2ms
memory: 24084kb

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: 4ms
memory: 22476kb

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'