QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152539 | #6619. Line Graph Matching | LFCode# | WA | 13ms | 11104kb | C++14 | 1.5kb | 2023-08-28 11:13:25 | 2023-08-28 11:13:27 |
Judging History
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'