Minimum spanning tree for each edge CodeForces - 609E

點選打開連結

先求最小生成樹的邊 這些邊的對應值就是生成樹的權值 再用這些邊建圖 對所有非生成樹上的邊的兩點 去掉兩者路徑上的最長邊 然後換為目前邊的權值 這個過程求個lca即可

這應該是貪心 最小生成樹已經是最優解(克魯斯卡爾方法中 就是從小邊找起 感覺也有貪心的意思) 每換下任何一條邊都會增權重重(可能不變) 既然非要換至少一條邊 那就隻換一條就夠了

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct node1
{
	int id;
	int u;
	int v;
	ll w;
	ll ans;
};

struct node2
{
	int v;
	ll w;
	int next;
};

node1 pre[200010];
node2 edge[400010];
ll maxx[200010][20];
int dp[200010][20];
int first[200010],f[200010],book[200010],deep[200010];
int n,m,num;

bool cmpI(node1 n1,node1 n2)
{
	return n1.w<n2.w;
}

bool cmpII(node1 n1,node1 n2)
{
	return n1.id<n2.id;
}

void addedge(int u,int v,ll w)
{
	edge[num].v=v;
	edge[num].w=w;
	edge[num].next=first[u];
	first[u]=num++;
	return;
}

int getf(int p)
{
	if(f[p]==p) return p;
	else
	{
		f[p]=getf(f[p]);
		return f[p];
	}
}

bool unite(int u,int v)
{
	int fu,fv;
	fu=getf(u);
	fv=getf(v);
	if(fu!=fv)
	{
		f[fv]=fu;
		return true;
	}
	else return false;
}

void dfs(int cur,int pre)
{
	ll w;
    int i,v;
    for(i=first[cur];i!=-1;i=edge[i].next)
    {
        v=edge[i].v,w=edge[i].w;
        if(v!=pre)
        {
            dp[v][0]=cur;
            maxx[v][0]=w;
            deep[v]=deep[cur]+1;
            dfs(v,cur);
        }
    }
    return;
}

void solve()
{
    int i,j;
    memset(dp,0,sizeof(dp));
    memset(maxx,0,sizeof(maxx));
    memset(deep,0,sizeof(deep));
    dp[1][0]=1;
    deep[1]=1;
    dfs(1,-1);
    for(j=1;(1<<j)<=n;j++)
    {
        for(i=1;i<=n;i++)
        {
            dp[i][j]=dp[dp[i][j-1]][j-1];
            maxx[i][j]=max(maxx[i][j-1],maxx[dp[i][j-1]][j-1]);
        }
    }
    return;
}

int getlca(int u,int v)
{
    int i;
    if(deep[u]<deep[v]) swap(u,v);
    for(i=log2(n);i>=0;i--)
    {
        if(deep[dp[u][i]]>=deep[v])
        {
            u=dp[u][i];
        }
    }
    if(u==v) return u;
    for(i=log2(n);i>=0;i--)
    {
        if(dp[u][i]!=dp[v][i])
        {
            u=dp[u][i];
            v=dp[v][i];
        }
    }
    return dp[u][0];
}

ll getmax(int p,int lca)
{
	ll res;
	int i;
	res=0;
	for(i=log2(n);i>=0;i--)
	{
		if(deep[dp[p][i]]>=deep[lca])
		{
			res=max(res,maxx[p][i]);
			p=dp[p][i];
		}
	}
	return res;
}

int main()
{
	ll sum;
	int i,cnt,lca;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=m;i++)
		{
			pre[i].id=i;
			scanf("%d%d%lld",&pre[i].u,&pre[i].v,&pre[i].w);
		}
		for(i=1;i<=n;i++)
		{
			f[i]=i;
		}
		memset(book,0,sizeof(book));
		sort(pre+1,pre+m+1,cmpI);
		cnt=0,sum=0;
		for(i=1;i<=m;i++)
		{
			if(unite(pre[i].u,pre[i].v))
			{
				book[i]=1;
				cnt++,sum+=pre[i].w;
			}
			if(cnt==n-1) break;
		}
		memset(first,-1,sizeof(first));
		num=0;
		for(i=1;i<=m;i++)
		{
			if(book[i])
			{
				addedge(pre[i].u,pre[i].v,pre[i].w);
				addedge(pre[i].v,pre[i].u,pre[i].w);
				pre[i].ans=sum;
			}
		}
		solve();
		for(i=1;i<=m;i++)
		{
			if(!book[i])
			{
				lca=getlca(pre[i].u,pre[i].v);
				int res=max(getmax(pre[i].v,lca),getmax(pre[i].u,lca));
				pre[i].ans=sum-res+pre[i].w;
			}
		}
		sort(pre+1,pre+m+1,cmpII);
		for(i=1;i<=m;i++)
		{
			printf("%lld\n",pre[i].ans);
		}
	}
	return 0;
}