QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693794#6619. Line Graph MatchingMENDAX#RE 1ms7888kbC++201.6kb2024-10-31 16:45:432024-10-31 16:45:49

Judging History

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

  • [2024-10-31 16:45:49]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7888kb
  • [2024-10-31 16:45:43]
  • 提交

answer

#include <bits/stdc++.h>

#define endl '\n'
#define pii pair<int,int>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 1e5 + 10;
vector <pii> G[N];
int n,m;
ll ans;

int low[N],dfn[N],cntt[N],fat[N],qwq[N];
bool bri[N];

int hd[N],to[N],nxt[N],tot = 1;
ll val[N];
void add(int x,int y,int w) {
	to[++tot] = y;nxt[tot] = hd[x];val[tot] = w;hd[x] = tot;
}
void addedge(int x,int y,int w) {
	add(x,y,w);add(y,x,w);
}

int dfscnt;
void tarjan(int x,int ine) {
    dfn[x] = low[x] = ++dfscnt;
    for (int i = hd[x];i;i = nxt[i]) {
        int y = to[i];
        if (!dfn[y]) {
            tarjan(y,i);
            cntt[x] += cntt[y]+1;
            low[x] = min(low[x],low[y]);
            if (low[y] > dfn[x]) bri[i] = bri[i ^ 1] = 1,qwq[i] = qwq[i^1] = y;
        } else if (i != (ine ^ 1)) {
            low[x] = min(low[x],dfn[y]);
        }
    }
}

void solve() {
	cin >> n >> m;
	for (int i = 1;i <= m;++i) {
		ll u,v,w;
		cin >> u >> v >> w;
		addedge(u,v,w);
		ans += (ll)w;
	}
	tarjan(1,0);
	ll qe = 0x3f3f3f3f;
	for (int i = 2;i <= tot;i += 2) {
		if (bri[i]) {
			if (cntt[qwq[i]] % 2 == 0) {
				qe = min(qe,val[i]);
			}
		} else {
			qe = min(qe,val[i]);
		}
	}
	//for (int i = 1;i <= n;++i) printf("%d ",cntt[i]);
	//printf("qwq:%d\n",qe);
	if (m % 2) printf("%lld\n",ans-qe);
	else printf("%lld",ans);
}
/*
6
1234 2345
1234 0123
1234 2267
1234 3401
1234 1344
1234 2468
*/
signed main() {
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr);
	//cout.tie(nullptr);
	int T = 1;
	while (T--) solve();
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5900kb

input:

5 6
1 2 1
1 3 2
1 4 3
4 3 4
4 5 5
2 5 6

output:

21

result:

ok 1 number(s): "21"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5816kb

input:

6 5
1 2 4
2 3 1
3 4 3
4 5 2
5 6 5

output:

12

result:

ok 1 number(s): "12"

Test #3:

score: 0
Accepted
time: 0ms
memory: 5860kb

input:

5 5
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5

output:

14

result:

ok 1 number(s): "14"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5904kb

input:

3 2
1 2 1
2 3 2

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7888kb

input:

3 3
1 2 3
2 3 1
3 1 2

output:

5

result:

ok 1 number(s): "5"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5824kb

input:

6 7
1 2 1
2 3 2
3 4 3
4 1 4
4 5 5
5 6 6
6 4 7

output:

27

result:

ok 1 number(s): "27"

Test #7:

score: -100
Runtime Error

input:

100000 99999
54273 5761 179909546
6472 21601 924153552
610 22693 767540137
37784 2454 951330587
24457 93770 781030280
36098 27 448166069
21292 43394 244510129
58047 86330 869927899
18770 83124 20504174
24036 92856 8370757
92492 21932 734860719
43776 77624 226721931
15746 70738 429430538
71204 87185 ...

output:


result: