leetcode 3600. 升级后最大生成树稳定性 困难

给你一个整数n，表示编号从 0 到n - 1的n个节点，以及一个edges列表，其中edges[i] = [ui, vi, si, musti]：

• ui和vi表示节点ui和vi之间的一条无向边。
• si是该边的强度。
• musti是一个整数（0 或 1）。如果musti == 1，则该边必须包含在生成树中，且不能升级。

你还有一个整数k，表示你可以执行的最多升级次数。每次升级会使边的强度翻倍，且每条可升级边（即musti == 0）最多只能升级一次。

一个生成树的稳定性定义为其中所有边的最小强度。

返回任何有效生成树可能达到的最大稳定性。如果无法连接所有节点，返回-1。

注意：图的一个生成树（spanning tree）是该图中边的一个子集，它满足以下条件：

• 将所有节点连接在一起（即图是连通的）。
• 不形成任何环。
• 包含恰好n - 1条边，其中n是图中节点的数量。

示例 1：

输入：n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1

输出：2

解释：

• 边[0,1]强度为 2，必须包含在生成树中。
• 边[1,2]是可选的，可以使用一次升级将其强度从 3 提升到 6。
• 最终的生成树包含这两条边，强度分别为 2 和 6。
• 生成树中的最小强度是 2，即最大可能稳定性。

示例 2：

输入：n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2

输出：6

解释：

• 所有边都是可选的，且最多可以进行k = 2次升级。
• 将边[0,1]从 4 升级到 8，将边[1,2]从 3 升级到 6。
• 生成树包含这两条边，强度分别为 8 和 6。
• 生成树中的最小强度是 6，即最大可能稳定性。

示例 3：

输入：n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0

输出：-1

解释：

• 所有边都是必选的，构成了一个环，这违反了生成树无环的性质。因此返回 -1。

提示：

• 2 <= n <= 10^5
• 1 <= edges.length <= 10^5
• edges[i] = [ui, vi, si, musti]
• 0 <= ui, vi < n
• ui != vi
• 1 <= si <= 105
• musti是0或1。
• 0 <= k <= n
• 没有重复的边。

分析：用 krustral 算法，在包含所有 must=1 的边的情况下，建立最小生成树。对于树中所有的边，把边权最小的 k 条边边权乘以 2，再把操作后最小的边权作为答案返回即可。

class Solution { public: typedef struct node { int u,v,s,must; bool operator<(const node& other)const { return s<other.s; // 按 s 从小到大排序 } }node; int find_father(int v,int father[]) { if(father[v]!=v) { int f=find_father(father[v],father); father[v]=f; return f; } return father[v]; } void merge(int u,int v,int father[]) { int father_u=find_father(u,father),father_v=find_father(v,father); if(father_u==father_v)return; else { father[father_u]=father_v; father_u=find_father(u,father); } } static bool cmp(const node& a,const node& b) { return a.s>b.s; } int maxStability(int n, vector<vector<int>>& edges, int k) { int cnt=0,ret=0x7fffffff,father[n+5]; for(int i=0;i<=n;++i)father[i]=i; priority_queue<node>vec; vector<node>maps; for(int i=0;i<edges.size();++i) { if(edges[i][3]==1) { if(find_father(edges[i][0],father)==find_father(edges[i][1],father)) return -1; merge(edges[i][0],edges[i][1],father); ret=min(ret,edges[i][2]),cnt++; } else { node temp;temp.u=edges[i][0],temp.v=edges[i][1],temp.s=edges[i][2],temp.must=edges[i][3]; vec.push(temp); // maps.push_back(temp); } } if(cnt==n-1)return ret; if(cnt>n-1||(cnt<n-1&&vec.size()==0))return -1; while(cnt<n-1&&!vec.empty()) { node temp=vec.top();vec.pop(); if(find_father(temp.u,father)!=find_father(temp.v,father)) { merge(temp.u,temp.v,father),cnt++; maps.push_back(temp); } else continue; } if(cnt==n-1) { sort(maps.begin(),maps.end(),cmp); printf("map.size=%d\n",maps.size()); for(int i=maps.size()-1,t=0;i>=0;--i,++t) { if(t<k)maps[i].s*=2; printf("i=%d maps[i].s=%d ret=%d\n",i,maps[i].s,ret); ret=min(ret,maps[i].s); } return ret; } return -1; } };