上代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,set[200005],head[200005],cnt=0;
int d[200005],p[200005][30];
long long w[200004][30];
int visit[200005];
long long dis=0;
struct node1
{
int start,end;
long long g;
}a[200005<<1],b[200005<<1];
struct node2
{
int to,next;
long long w;
}e[200005<<1];
inline bool cmp(node1 x,node1 y)
{
if(x.g<y.g) return true;
return false;
}
inline int Find(int x)
{
if(x==set[x])
return x;
else
return set[x]=Find(set[x]);
}
inline void jiantu(int u,int v,long long w)
{
e[++cnt].next=head[u];
e[cnt].to=v;
e[cnt].w=w;
head[u]=cnt;
}
inline void kruskal()
{
for(int i=1;i<=n;i++)
set[i]=i;
sort(a+1,a+m+1,cmp);
int c=1;
int ccnt=0;
while(c<m)
{
int qq=Find(a[c].start);
int zz=Find(a[c].end);
if(qq!=zz)
{
jiantu(qq,zz,a[c].g);
jiantu(zz,qq,a[c].g);
set[qq]=zz;
dis+=a[c].g;
ccnt++;
if(ccnt==n-1) break;
}
c++;
}
return ;
}
void dfs(int u,int v,long long ww)
{
d[u]=d[v]+1;
p[u][0]=v;
w[u][0]=ww;
for(int i=1;i<=21;i++)
{
p[u][i]=p[p[u][i-1]][i-1];
w[u][i]=max(w[u][i-1],w[p[u][i-1]][i-1]);
}
for(register int i=head[u];i;i=e[i].next)
{
int vv=e[i].to;
if(vv!=v)
dfs(vv,u,e[i].w);
}
}
inline long long LCA(int a,int b)
{
long long ans=0;
if(d[a]>d[b]) swap(a,b);
for(register int i=21;i>=0;i--)
if(d[a]<=d[b]-(1<<i))
{
ans=max(ans,w[b][i]);
b=p[b][i];
}
if(a==b) return ans;
for(register int i=21;i>=0;i--)
if(p[b][i]==p[a][i]) continue;
else
{
ans=max(ans,max(w[a][i],w[b][i]));
b=p[b][i],a=p[a][i];
}
return max(ans,max(w[a][0],w[b][0]));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld",&a[i].start,&a[i].end,&a[i].g);
b[i].start=a[i].start;
b[i].end=a[i].end;
b[i].g=a[i].g;
}
kruskal();
dfs(1,0,0);
int long long ans=0;
for(int i=1;i<=m;i++)
{
ans=dis+b[i].g-LCA(b[i].start,b[i].end);
cout<<ans<<endl;
}
return 0;
}
VAN全一样的代码。。交了两遍。。。第一次第10个点WA了。过了30分钟后再次提交就AC了!!!!!! 代码一个字没改。。
这不是重点
重点是我把AC了的代码再交几遍。。就都没有AC了!!!!(玄学!!!!!)
本题过法:趁测评姬不注意