0分求调
查看原帖
0分求调
476487
tangml楼主2024/6/19 11:26

为什么会RE啊

#include<bits/stdc++.h>
#define AC return 0
#define int long long

using namespace std;

const int N=5e5+100;

int n,m;
int tot; 
int ans[N],p[N];
int fa[N][32],deep[N];
int d1[N][32],d2[N][32];
int e[N*2],ne[N*2],h[N],w[N*2],idx;

struct node {
	int a,b,v;
	bool f;
	bool operator<(const node aa)const{
		return v<aa.v;
	}
}dt[N];

int find(int x)
{
	if(x!=p[x])	p[x]=find(p[x]);
	return p[x];
}

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int kurskal();
void dfs(int u,int father);
int lca(int x,int y);
int maxm(int x,int y,int& max1,int& max2);

signed main() 
{
	ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0); 
	cin>>n>>m;
	for(int i=1;i<=m;i++)	cin>>dt[i].a>>dt[i].b>>dt[i].v;
	sort(dt+1,dt+m+1);
	long long sum=kurskal();
 	deep[1] = 1;
    d1[1][0]=d2[1][0]=INT_MAX;
    dfs(1,-1);
    int ans=1e18;
    for(int i=1;i<=m;i++)
    	if(!dt[i].f)
    	{
    		int a=dt[i].a,b=dt[i].b,w=dt[i].v;
    		int t;
    		int max1,max2;
    		max1=max2=-INT_MAX;
    		int LCA=lca(a,b);
    		maxm(a,LCA,max1,max2); 
            maxm(b,LCA,max1,max2);
            if(w>max1)	t=sum+w-max1;
            else if(w>max2)	t=sum+w-max2;
            ans=min(ans,t);
		}
	cout<<ans;
	AC;
}

int kurskal()
{	
	for (int i=1;i<=n;i++) p[i]=i;
    memset(h,-1,sizeof h);
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        int a=dt[i].a,b=dt[i].b,w=dt[i].v;
        int pa=find(a),pb=find(b);
        if (pa!=pb)
        {
            p[pa]=pb;
            dt[i].f=true;
            add(a,b,w),add(b,a,w);
            sum+=w;
        }
    }
    return sum;
}
void dfs(int u, int father)
{
	fa[u][0]=father;
    deep[u]=deep[father]+1;
    for(int i=1;i<=16;i++)
    {
    	int anc=fa[u][i-1];
        fa[u][i]=fa[anc][i-1];
        int disc[4]={d1[u][i-1],d2[u][i-1],d1[anc][i-1],d2[anc][i-1]};
        d1[u][i]=d2[u][i]=-INT_MAX;
        for (int k=0;k<4;k++)
        {
            int t=disc[k];
            if(t>d1[u][i]) d2[u][i]=d1[u][i],d1[u][i]=t;
            else if(t>d2[u][i] && t!=d1[u][i]) d2[u][i]=t;
        }
	}
	for(int i=h[u];~i;i = ne[i])
    {
        int j=e[i];
        if (j==father) continue;
        d1[j][0]=w[i], d2[j][0]=-INT_MAX;
        dfs(j,u);
    }
}
int lca(int x,int y)
{
	if (deep[y]>deep[x]) swap(x,y);
    for (int i=16;i>=0;i--)
        if (deep[fa[x][i]]>=deep[y])
            x=fa[x][i];
    if(x==y) return x;
    for (int i=16;i>=0;i--)
        if (fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int maxm(int x,int y,int& max1,int& max2)
{
	if (deep[y]>deep[x]) swap(x,y);
	for (int i=16;i>=0;i--)
		if(deep[fa[x][i]]>=deep[y])
		{
			int dis[2]={d1[x][i],d2[x][i]};
			for(int k=0;k<2;k++)
			{
				int w=dis[k];
				if(w>max1)	max2=max1,max1=w;
				else if(w>max2 && w!=max1)	max2=w;
				x=fa[x][i];
			}
		}
}
2024/6/19 11:26
加载中...