QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152539#6619. Line Graph MatchingLFCode#WA 13ms11104kbC++141.5kb2023-08-28 11:13:252023-08-28 11:13:27

Judging History

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

  • [2023-08-28 11:13:27]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:11104kb
  • [2023-08-28 11:13:25]
  • 提交

answer

#include<cstdio>
const int N=200086;
int n,m,tot=1,dfncnt,tp,h[N],deg[N],dep[N],dfn[N],low[N],eu[N],ev[N],ew[N],cnt[N];
bool vis[N];
struct edge{int v,w,nxt;}e[N<<1];
int Min(int a,int b){return a<b?a:b;}
int Max(int a,int b){return a>b?a:b;}
bool Swap(int &a,int &b){a^=b^=a^=b;return true;}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool add(int u,int v,int w){deg[v]++;e[++tot].v=v;e[tot].w=w;e[tot].nxt=h[u];h[u]=tot;return true;}
bool tarjan(int np,int lst){
	dfn[np]=low[np]=++dfncnt;dep[np]=dep[lst]+1;
	for(int i=h[np];i;i=e[i].nxt){
		if(e[i].v==lst)continue;
		if(!dfn[e[i].v]){
			tarjan(e[i].v,np);
			low[np]=Min(low[np],low[e[i].v]);
			if(low[e[i].v]>dfn[np])vis[e[i].w]=true;
		}
		else low[np]=Min(low[np],dfn[e[i].v]);
	}
	return true;
}
bool dfs(int np,int lst){
	for(int i=h[np];i;i=e[i].nxt){
		if(dfn[e[i].v]<=dfn[np])continue;
		dfs(e[i].v,np);
		cnt[np]+=cnt[e[i].v];
	}
	return true;
}
int main(){
	n=read();m=read();long long ans=0;
	for(int i=1;i<=m;i++){
		int u=read();int v=read();int w=read();
		add(u,v,i);add(v,u,i);eu[i]=u;ev[i]=v;ew[i]=w;ans+=w;
	}
	if(m&1){
		long long lans=ans;ans=0;
		tarjan(1,0);
		for(int i=1;i<=m;i++){
			if(dep[eu[i]]>dep[ev[i]])Swap(eu[i],ev[i]);
			cnt[eu[i]]++;
		}
		dfs(1,0);
		for(int i=1;i<=m;i++){
			if(!vis[i])ans=Max(ans,lans-ew[i]);
			else if(!(cnt[ev[i]]&1))ans=Max(ans,lans-ew[i]);
		}
	}
	printf("%lld",ans);
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7560kb

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: 1ms
memory: 7680kb

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: 9704kb

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: 0ms
memory: 5524kb

input:

3 2
1 2 1
2 3 2

output:

3

result:

ok 1 number(s): "3"

Test #5:

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

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

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
Wrong Answer
time: 13ms
memory: 11104kb

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:

178219295

result:

wrong answer 1st numbers differ - expected: '49946352904479', found: '178219295'