• 用算法求最大生成樹，在并查集合并時，把原本的一個根連向另一個 根改成兩個根都連向一個新建的節點，并把當前正在處理的邊的權值賦給這個新 節點做點權。這樣形成的結構會是一棵樹。 一個點的答案大致上是樹的根到自己的路徑上，相鄰兩個節點的子樹葉節點 數的平方和。需要注意的是父子兩個節點權值相同的情況，這個部分需要特殊處理。

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <cctype> 7 using namespace std; 8 9 #define LL long long 10 #define res register int 11 inline int read() 12 { 13 int x(0),f(1); char ch; 14 while(!isdigit(ch=getchar())) if(ch=='-') f=-1; 15 while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); 16 return f*x; 17 } 18 int n,m; 19 const int N=500000+5; 20 int head[N],nxt[N<<1],ver[N<<1],tot; 21 struct E{ 22 int u,v,w; 23 }e[N]; 24 int vis[N],fa[N]; 25 LL w[N],size[N],val[N]; 26 inline bool cmp(E a,E b) {return a.w>b.w;} 27 inline void add(int x,int y) { 28 ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; 29 ver[++tot]=x; nxt[tot]=head[y]; head[y]=tot; 30 } 31 32 inline int get(int x) { 33 if(x==fa[x]) return x; return fa[x]=get(fa[x]); 34 } 35 36 int cnt(0); 37 inline void Kruskal() 38 { 39 cnt=n; 40 sort(e+1,e+m+1,cmp); 41 for(res i=1 ; i<=n ; i++) fa[i]=i; 42 for(res i=1 ; i<=m ; i++) 43 { 44 int x=get(e[i].u),y=get(e[i].v),z=e[i].w; 45 if(x==y) continue; 46 val[++cnt]=z; 47 fa[cnt]=fa[x]=fa[y]=cnt; 48 add(x,cnt); add(y,cnt); 49 if(cnt==2*n-1) break; 50 } 51 } 52 53 inline void dfs(int x,int f) 54 { 55 vis[x]=1; 56 for(res i(head[x]) ; i ; i=nxt[i]) 57 { 58 int y=ver[i]; if(f==y) continue; 59 dfs(y,x); size[x]+=size[y]; 60 } 61 } 62 63 inline void dp(int x,int f) 64 { 65 for(res i(head[x]) ; i ; i=nxt[i]) 66 { 67 int y=ver[i]; if(f==y) continue; 68 if(val[x]==val[y]) size[y]=size[x]; 69 w[y]=w[x]+(size[x]-size[y])*(size[x]-size[y]); 70 dp(y,x); 71 } 72 } 73 74 inline void work() 75 { 76 for(res i=1 ; i<=n ; i++) size[i]=1; 77 for(res i=1 ; i<=cnt ; i++) 78 { 79 if(vis[i]) continue; 80 int x=get(i); 81 dfs(x,0); 82 dp(x,0); 83 } 84 } 85 86 int main() 87 { 88 freopen("car.in","r",stdin); 89 freopen("car.out","w",stdout); 90 n=read(); m=read()-1; 91 for(res i=1 ; i<=m ; i++) { 92 e[i].u=read(); e[i].v=read(); e[i].w=read(); 93 } 94 Kruskal(); 95 work(); 96 for(res i=1 ; i<=n ; i++) cout<<w[i]<<" ";//printf("%d ",w[i]); 97 puts(""); 98 return 0; 99 } View Code

?

轉載于:https://www.cnblogs.com/wmq12138/p/10380846.html

總結

以上是生活随笔為你收集整理的2019.2.14 t3 车辆销售的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。