解为基环树森林
证明其具有拟阵的性质：
1、空集独立
2、基环树森林的子集仍然是基环树森林，满足遗传特性
3、对于基环树森林A，B，若|A|<|B| （边数），一定可以找到一条边e∈B，∉A，使A∪e仍然是基环树森林，满足扩充特性
扩充特性证明：
枚举A中的联通块
1、若A中这个联通块的边数<B中对应联通块的边数，显然存在一条满足要求的边
2、否则B中存在一条边连接了A的两个联通块。枚举B中这样的边，若这两个联通块至少有一个不是基环树，则该边满足要求。
否则，A中这两个联通块都是基环树，B中不是基环树，因此B中这个联通块的边数<A中这两个联通块的边数和。所以还存在其他的联通块之间的边满足要求
所以本题解法：
按边权从大到小排序，先构造出一颗最大权值基环树
然后按边权从大到小枚举之前没有用过的边u--v
首先明确不会存在原来联通块是树，加上这条边变成基环树的情况
因为之前已经构造了最大权值基环树
1、若u和v在同一个联通块，该联通块一定是基环树，那么新加的这条边可以替换环上的任意一条边，也可以替换u和v到环的路径上的一条边
2、若u和v不在同一个联通块，那么这两个联通块都是基环树，这条边可以替换两个环上的任意一条边，也可以替换u和v到环的路径上的一条边
无论哪种情况，都是用当前边去替换最大权值基环树上的边
遇上已经被替换过一次的边则停止替换，因为之前用的边的边权不会比现在的边的边权小
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; #define N 200001 struct node { int u,v,w; int id; bool use; }e[N]; LL ans[N]; int fa[N],siz_p[N],siz_e[N]; int circle[N];//基环的环在哪儿 struct graph { int from,to,id,w; int nxt; }g[N<<1]; int tot,front[N]; int pre[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } bool cmp(node p,node q) { return p.w>q.w; } int find(int i) { return fa[i]==i ? i : fa[i]=find(fa[i]); } void unionn(int u,int v) { int fu=find(u),fv=find(v); if(fu==fv) { circle[fu]=u; siz_e[fu]++; return; } fa[fu]=fv; siz_e[fv]+=siz_e[fu]+1; siz_p[fv]+=siz_p[fu]; circle[fv]|=circle[fu]; } void add(int u,int v,int t) { g[++tot].from=u; g[tot].to=v; g[tot].id=e[t].id; g[tot].w=e[t].w; g[tot].nxt=front[u]; front[u]=tot; g[++tot].from=v; g[tot].to=u; g[tot].id=e[t].id; g[tot].w=e[t].w; g[tot].nxt=front[v]; front[v]=tot; } int dfs(int now,int last) { int tmp=0,t; for(int i=front[now];i;i=g[i].nxt) { t=g[i].to; if(t==last) continue; if(pre[t]==-1) tmp=i; if(pre[t]) continue; pre[t]=i; tmp|=dfs(t,now); } return tmp; } void concat(int x,int w) { int now; while(1) { now=pre[x]; if(ans[g[now].id]) break; ans[g[now].id]=ans[0]-g[now].w+w; x=g[now].from; } } void out(LL x) { if(x>9) out(x/10); putchar(x%10+'0'); } int main() { freopen("journey.in","r",stdin); freopen("journey.out","w",stdout); int n,m; read(n); read(m); for(int i=1;i<=m;++i) { read(e[i].u); read(e[i].v); read(e[i].w); e[i].id=i; } sort(e+1,e+m+1,cmp); for(int i=1;i<=n;++i) { fa[i]=i; siz_p[i]=1; } int fu,fv; for(int i=1;i<=m;++i) { fu=find(e[i].u); fv=find(e[i].v); if(siz_p[fu]==siz_e[fu] && siz_p[fv]==siz_e[fv]) continue; ans[0]+=e[i].w; e[i].use=true; unionn(e[i].u,e[i].v); add(e[i].u,e[i].v,i); } int u; for(int i=1;i<=n;++i) { u=find(i); if(circle[u]) u=circle[u]; if(!pre[u]) { pre[u]=-1; pre[u]=dfs(u,-1); } } for(int i=1;i<=m;++i) { if(e[i].use) continue; ans[e[i].id]=ans[0]; concat(e[i].u,e[i].w); concat(e[i].v,e[i].w); } for(int i=1;i<=m;++i) if(!ans[e[i].id]) ans[e[i].id]=ans[0]-e[i].w; for(int i=1;i<=m;++i) out(ans[i]),putchar(' '); }