商业营销厅装修公司,宁波seo网站推广软件,网站建设sem,简洁文章网站模板下载P2619 [国家集训队]Tree I 一张 \(n\) 个点 \(m\) 条边的带权无向联通图#xff0c;每条边是黑色或白色。求一棵最小权的恰好有 \(need\) 条白色边的生成树#xff0c;题目保证有解。 \(n\le 5\times 10^4,m\le 10^5,val\in[1,100]\)。 \(\color{yellow}{\bigstar\texttt{Tri… P2619 [国家集训队]Tree I 一张 \(n\) 个点 \(m\) 条边的带权无向联通图每条边是黑色或白色。求一棵最小权的恰好有 \(need\) 条白色边的生成树题目保证有解。 \(n\le 5\times 10^4,m\le 10^5,val\in[1,100]\)。 \(\color{yellow}{\bigstar\texttt{Trick}}\)这种限制选择 \(need\) 个物品的问题可以考虑 WQS 二分(或者直接叫 二分) 将所有白边从小到大排序后每条边权值加上一个 \(x\) 之后再进行最小生成树。 可以发现随着增加值 \(x\) 的增大我们选择的白边的数量不断减少完全可以二分找到最接近选择 \(need\) 条白边的那个 \(x\)。 那么我们二分 \(k\)如果发现 \(choseneed\)就增大 \(k\)否则减小 \(k\)。 代码实现的时候有一个细节上的小技巧二分不一定能够准确的二分到 \(need\)这是因为有白边和黑边权值相同取到了黑边。 不妨先二分出最接近 \(need\) 的一个 \(x\)由于题目保证有解此时多出来的白边一定有相同权值的黑边可以代替。 为什么若不存在相同权值的黑边可以代替我们选择 \(need\) 数量的白边必须要舍弃较小权值 \(wh\) 的白边再选择较大权值 \(bl\) 的黑边确保交换的 \(bl-wh\) 最小。那么完全可以在二分的时候 \(x\) 变为 \(xbl-wh1\)使得二分后这条 \(bl\) 黑边就在 \(wh\) 白边后面(一定不存在新的替换因为 \(bl-wh\) 最小)这使得二分出选择的白边数量减少 \(1\)与一开始二分出的白边数量最接近与 \(need\) 矛盾不成立。因此一定存在相同权值的黑边可以替代。 只用将白边与黑边权值相同时钦定白边优先这样可以将一些的白边“替换”为黑边(贡献不变意会即可)。 此题代码 // 白边是 0黑边是 1。
#define Maxn 50005
#define Maxm 100005
int n,m,ned,cnt0,cnt1,ansinf,Now,mid;
int fa[Maxn];
struct EDGE
{int u,v,c,opt;EDGE(int U0,int V0,int C0,int OPT0):u(U),v(V),c(C),opt(OPT){}bool friend operator (EDGE x,EDGE y){ return (x.c!y.c)?x.cy.c:(x.opty.opt); }
}wh[Maxm],bl[Maxm],tmp[Maxm];
int Find(int x){ return (fa[x]x)?x:(fa[x]Find(fa[x])); }
inline bool merge(int x,int y)
{xFind(x),yFind(y);if(x!y) { fa[x]y; return true; }return false;
}
inline bool check()
{int used0;for(int i1;in;i) fa[i]i;for(int i1;icnt0;i) wh[i].cmid;merge(bl1,blcnt11,wh1,whcnt01,tmp1);for(int i1;im;i) if(merge(tmp[i].u,tmp[i].v))Nowtmp[i].c,used(tmp[i].opt^1);for(int i1;icnt0;i) wh[i].c-mid;Now-mid*ned;return usedned;
}
int main()
{nrd(),mrd(),nedrd();for(int i1,s,t,c,col;im;i){srd()1,trd()1,crd(),colrd();if(!col) wh[cnt0]EDGE(s,t,c,0);else bl[cnt1]EDGE(s,t,c,1);}sort(wh1,whcnt01),sort(bl1,blcnt11);int nl-101,nr101;while(nlnr){mid(nlnr)1,Now0;if(check()) nlmid1,ansNow;else nrmid-1;}printf(%d\n,ans);return 0;
} P5633 最小度限制生成树 其实就是上面的弱化为限制单点相邻的白边数量但是增添了无解的情况。 无解可以这样判断将于这个点相邻的边全部断开如果分开后连通块数量 \(need\) 则无解其他一定有解。
