又菜又可爱的萌新求助题目/kel

常规
1

image
image929×749 33.7 KB

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
namespace Syxqwq {
	inline int read() {
		int x = 0, s = 1;
		char c = getchar();
		while (c > '9' || c < '0') {
			if (c == '-') s = -1;
			c = getchar();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c - '0');
			c = getchar();
		}
		return x * s;
	}
	void Write(int x) {
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		if (x > 9) Write(x / 10);
		putchar(x % 10 + '0');
	}
	inline void write(int x, char c) {
		Write(x), putchar(c);
	}
}
using namespace Syxqwq;
using ll = long long;
const int N = 1e5 + 19, M = 2e5 + 19;
ll head[N], nxt[M], edge[M], idx, n, d[N], w[M], vis[N], cnt;
ll a[N];
ll ans;
vector<pair<int, int> > qwq[N];
ll topsort() {
	ll ret = 0x3f3f3f3f;
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (d[i] == 1) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int x = q.front(), y = 0;
		q.pop();
		if (vis[x])continue;
		vis[x] = 1;
		for (int i = head[x]; i; i = nxt[i]) {
			int v = edge[i];
			if (!vis[v]) {
				y = v;
				ret = min(ret, w[i]);
				break;
			}
		}
		if (y == 0) {
			puts("no answer");
			exit(0);
		}
		vis[y] = 2;
		for (int i = head[y]; i; i = nxt[i]) {
			int v = edge[i];
			if (!vis[v]) {
				d[v]--;
				if (d[v] == 1) {
					q.push(v);
				}
			}
		}
	}
	return ret;
}
void insert (int x, int y, int z) {
	edge[++idx] = y;
	nxt[idx] = head[x];
	w[idx] = z;
	head[x] = idx;
}
void fd(int pls, int last) {
	vis[pls] = 3;
	bool flag = 1;
	for (const auto& i : qwq[pls]) {
		int v = i.first;
		if (v == last)continue;
		if (vis[v]) {
			if (flag)a[0] = i.second, flag = 1;
			continue;
		}
		a[++cnt] = i.second;
		fd(v, pls);
	}
}
int main() {
	n = read();
	for (int i = 1; i <= n; ++i) {
		int u = read(), v = read(), w = read();
		insert(u, v, w);
		insert(v, u, w);
		qwq[u].emplace_back(v, w), qwq[v].emplace_back(u, w);
		d[u]++, d[v]++;
	}
	ans = topsort();
	int pls = 0;
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			pls = i;
			break;
		}
	}
	if (pls == 0) return puts("no answer"), 0;
	fd(pls, 0);
	ll ans1 = ans, ans2 = ans;
	for (int i = 0; i <= cnt; ++i) {
		if (i % 2 == 0) ans1 = min(ans1, a[i]);
		else ans2 = min(ans2, a[i]);
	}
	write(max(ans1, ans2), '\n');
	return 0;
}
2 个赞
2

调崩了一天，只有 20 分。

2 个赞
3

思路是先拓扑，再跑环

2 个赞
4

什么难度的？

  • 黑色
  • 紫色
  • 蓝色
  • 白色
0 投票人
2 个赞
5

红题

2 个赞
6

题号是啥

2 个赞
7

比赛题，已结束/kk

3 个赞
8

image
image2020×350 33.1 KB

3 个赞
9

你这叫菜

3 个赞
10

？？？

3 个赞
11

咋了

3 个赞
12

人家敲可爱的啦

3 个赞
13

:face_vomiting: :face_vomiting:

4 个赞
14

hhh

4 个赞
15

所以帮我调代码（悲

4 个赞
16
  • 这题我能帮你
  • 这题我不会
0 投票人
4 个赞
17

此帖结，死因：一遍拓扑就有答案我输出了 no answer

5 个赞
18

6666

3 个赞
19

标题对自己的评价只评价对了一半（

3 个赞