<output id="qn6qe"></output>

    1. <output id="qn6qe"><tt id="qn6qe"></tt></output>
    2. <strike id="qn6qe"></strike>

      亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12

      帶權并查集

      帶權并查集

      【概述】    1、定義:帶權并查集即是結點存有權值信息的并查集。

            2、適用:當兩個元素之間的關系可以量化,并且關系可以合并時,可以使用帶權并查集來維護元素之間的關系。

            3、權值:帶權并查集每個元素的權通常描述其與并查集中祖先的關系,這種關系如何合并,路徑壓縮時就如何壓縮。

            4、與并查集的區別:帶權并查集可以推算集合內點的關系,而一般并查集只能判斷屬于某個集合。

      【具體實現】 

       

      例:https://hihocoder.com/problemset/problem/1515

      #include <iostream>
      #include <cstdio>
      
      using namespace std;
      const int maxn=100005;
      int n,m,q;
      int f[maxn],v[maxn];//i的父親,i與v[i]之間的關系;
      
      void init()
      {
          for(int i=1;i<=n;i++){
              f[i]=i,v[i]=0;
          }
      }
      int fin(int x)
      {
          if(x!=f[x]){
              int fa=f[x];
              f[x]=fin(f[x]);
              v[x]+=v[fa];
          }
          return f[x];
      }
      int unit(int x,int y,int s)
      {
          int fa=fin(x);
          int fb=fin(y);
          if(fa!=fb){
              f[fa]=fb;
              v[fa]=s-v[x]+v[y];
          }
      }
      bool same(int x,int y)
      {
          return fin(x)==fin(y);
      }
      
      int main()
      {
          scanf("%d%d%d",&n,&m,&q);
          int a,b,c;
          init();
          for(int i=0;i<m;i++)
          {
              scanf("%d%d%d",&a,&b,&c);
              unit(a,b,c);
          }
          for(int i=0;i<q;i++)
          {
              scanf("%d%d",&a,&b);
              if(!same(a,b)){
                  printf("-1\n");
              }else{
                  printf("%d\n",v[a]-v[b]);
              }
          }
          return 0;
      }
      posted @ 2018-09-24 16:00  Akmpfen  閱讀(816)  評論(0)    收藏  舉報
      主站蜘蛛池模板: 经典国产乱子伦精品视频| 深夜福利资源在线观看| 91在线国内在线播放老师 | 精品综合久久久久久98| 国产成人高清亚洲一区91| 色综合久久婷婷88| 精品国产午夜福利在线观看| 韩国19禁无遮挡啪啪无码网站 | 久久精品国产一区二区三区| 欧美视频精品免费覌看| 国产在线精品一区二区夜色| 亚洲国产成人无码AV在线影院L| 精品精品亚洲高清a毛片| 通榆县| 国产激情文学亚洲区综合| 亚洲成亚洲成网| 国产69精品久久久久99尤物 | 色www永久免费视频| 中文文字幕文字幕亚洲色| 一区二区三区无码免费看| 97欧美精品系列一区二区| 好硬好湿好爽再深一点动态图视频| 国产熟女一区二区三区四区| 狠狠人妻久久久久久综合九色| 欧美成人精品三级在线观看| 精品无码国产自产拍在线观看蜜 | 欧洲国产成人久久精品综合 | 亚洲高清aⅴ日本欧美视频| 女人与牲口性恔配视频免费| 国产精品久久久天天影视香蕉 | 日本a在线播放| 丰满熟妇乱又伦在线无码视频| 激情综合色综合啪啪开心| 国产乱人伦无无码视频试看| 麻豆成人传媒一区二区| 摸丰满大乳奶水www免费| 国产精品夜夜春夜夜爽久久小说| 国产精品偷乱一区二区三区| 极品少妇被后入内射视| 亚洲一区二区偷拍精品| 亚洲 成人 无码 在线观看|