2019.2.14 t3 车辆销售

绝地灬酷狼 2022-01-09 07:39 176阅读 0赞

![1597764-20190214210325079-854976076.png][]![1597764-20190214210333838-531980084.png][]

*  用算法求最大生成树，在并查集合并时，把原本的一个根连向另一个 根改成两个根都连向一个新建的节点，并把当前正在处理的边的权值赋给这个新 节点做点权。这样形成的结构会是一棵树。 一个点的答案大致上是树的根到自己的路径上，相邻两个节点的子树叶节点 数的平方和。需要注意的是父子两个节点权值相同的情况，这个部分需要特殊处理。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/wmq12138/p/10380846.html

[1597764-20190214210325079-854976076.png]: https://img2018.cnblogs.com/blog/1597764/201902/1597764-20190214210325079-854976076.png
[1597764-20190214210333838-531980084.png]: /images/20220109/101bb098cdbb434c8d98b1c9b687d30f.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/e9d7360afb7e4988917fe938f93fa914.png