upc 兔最小生成树-白红宇的个人博客

upc 兔最小生成树

发布日期：2021-09-25 23:57:51 浏览次数：6 分类：技术文章

本文共 1687 字，大约阅读时间需要 5 分钟。

兔

时间限制: 1 Sec 内存限制: 128 MB

[提交] [状态]

题目描述

小粉兔用集训队的奖金买下了一片地。

这片地上有 n 个房子，有些房子之间有道路，有些房子之间则是杂草。

她可以花费一定的代价拆毁一条道路，或是啃光一片草使得两个房子间可以通行（大雾）。

她喜欢生成树，所以她要让所有道路形成一棵生成树。

求最小花费。

输入

第一行一个数，n。

接下来 n 行，每行 n 个数，代表 ai,j。如果为正数，说明它们之间没有道路，需要 ai,j的花费来修建；如果为负数，说明它们之间有道路，需要 −ai,j的花费来拆毁。

输出

一行一个数，代表最小花费。

样例输入 Copy

0 1 -3

1 0 5

-3 5 0

样例输出 Copy

提示

对于 100% 的数据，5≤n≤1000,1≤|ai,j(i≠j)|≤1000，保证所有 ai,i=0且 ai,j=aj,i 。

题意就是让你在给定条件下，生成一棵树，可以在某些点之间建边，也可以删给定的边。

先不考虑建边，先考虑已经有的边，这些已经有的边，本着能不删就不删的原则 ( 这是显然的，因为删去的话可能需要重新建一条边 ) ，从大到小枚举已经有的边，能加入并查集合并的就合并，如果当前边连接的两个点已经在同一个集合当中，这个时候，因为树的结构的限制，一定需要删除这条边，而且我们是从大到小枚举的，所以删除边的代价是最小的。

至此，我们能留下的原有的边是最多的，现在需要做的就是补充完树的结构，对于可以建的边做一遍最小生成树即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;int p[N*N*2];int g[N][N];struct Node{ int a,b; int w; bool operator < (const Node &s) const { return w
                
                 >n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { int x; scanf("%d",&x); if(i<=j) continue; if(x>0) edge1[++tot]={ i,j,x}; else edge2[++cnt]={ i,j,-x}; } init(max(tot,cnt)); sort(edge2+1,edge2+1+cnt); for(int i=cnt;i>=1;i--) { int a=edge2[i].a,b=edge2[i].b; int pa=find(a),pb=find(b); int w=edge2[i].w; if(pa!=pb) p[pa]=pb; else cos+=w; } sort(edge1+1,edge1+1+tot); for(int i=1;i<=tot;i++) { int a=edge1[i].a,b=edge1[i].b; int w=edge1[i].w; int pa=find(a),pb=find(b); if(pa!=pb) { cos+=w; p[pa]=pb; } } cout<
                 
                  <

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106246073 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：P2184 贪婪大陆线段树 + 区间覆盖

下一篇：ZOJ - 3591 Nim 尼姆博弈 + 前缀和

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章