P1031 · OFFICIAL SOLUTION

P1031 雨霖铃官方题解

Gioush OJ · P1031 雨霖铃

雨霖铃

【题意简述】

给定一张无向图，每条边类型为 $0$ 或 $1$ 。要求构造一棵生成树，使其中恰好有 $k$ 条类型为 $0$ 的边；若不存在则输出 no solution。

【Hint】

先判断类型 $0$ 边的数量下界，再判断上界。下界来自“先用类型 $1$ 边尽量连通后仍必须使用多少条类型 $0$ 边”。

【提示】

若先加入所有能加入的类型 $1$ 边，剩下为了连通而加入的类型 $0$ 边数量就是最少需求。

【解法】

先用 Kruskal 思想求必须使用的类型 $0$ 边数量。将类型 $1$ 边优先加入并查集，之后为了连通而加入的类型 $0$ 边记为 $Must$ 。若 $Must>k$ ，无解。

再构造答案：优先加入必要的类型 $0$ 边，并继续补充类型 $0$ 边直到数量达到 $k$ ；最后用类型 $1$ 边补齐生成树。若无法得到 $n-1$ 条边，则无解。

这个过程本质上是在生成树交换空间中控制类型 $0$ 边数量。先满足必要边，再补足可选边，可以保证不会因为较晚加入类型 $1$ 边破坏已经达到的 $k$ 条限制。

【上下界与构造】

先尽量加入类型 $1$ 边，之后为了连通而不得不加入的类型 $0$ 边数记为 $\operatorname{Must}$ ，它是任意生成树中类型 $0$ 边数的下界。若 $\operatorname{Must}>k$ ，无解。

随后重新维护并查集：先加入构成下界所需的类型 $0$ 边，再继续加入不会成环的类型 $0$ 边，直到恰有 $k$ 条；最后用类型 $1$ 边补成生成树。每一步都保持无环，且下界阶段留下了足够的连通空间，因此构造结束时得到的正是所求生成树。

【复杂度】

排序两次或按类型分组后处理，时间复杂度为 $\mathcal{O}(m\log m)$ ，空间复杂度为 $\mathcal{O}(n+m)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/234Name:rainbell.cpp5You steal,I kill.6*/7#include <vector>8#include <cstdio>9#include <cstring>10#include <algorithm>11#define MAXN 2001012#define MAXM 10001013using namespace std;14int Fa[MAXN],Must,n,m,Can=0,k;15struct edge{16    int St,Ed;17    int Type;18}Edge[MAXM];19vector <edge> Ans;20bool cmpa(edge a,edge b){return a.Type<b.Type;}21bool cmpb(edge a,edge b){return a.Type>b.Type;}22int Find(int x){return Fa[x]==x?Fa[x]:Fa[x]=Find(Fa[x]);}23void Merge(int x,int y){Fa[Find(x)]=Find(y);}24bool Get_Tog(){25    int Tag;26    for(int i=1;i<=n;i++) Fa[i]=i;27    for(int i=1;i<=m;i++){28        if(Find(Edge[i].St)==Find(Edge[i].Ed)) continue;29        Merge(Edge[i].St,Edge[i].Ed);30    }31    Tag=Find(1);32    for(int i=1;i<=n;i++){if(Tag!=Find(i)) return false; }33    return true;34}35void Kruskal1(){36    sort(Edge+1,Edge+m+1,cmpb);37    for(int i=1;i<=n;i++) Fa[i]=i;38    int Count=0,i;39    for(i=1;i<=m;i++){40        if(Edge[i].Type==0) break;41        if(Find(Edge[i].St)==Find(Edge[i].Ed)) continue;42        Count++;43        Merge(Edge[i].St,Edge[i].Ed);44    }45    for(i;i<=m;i++){46        if(Find(Edge[i].St)==Find(Edge[i].Ed)) continue;47        Merge(Edge[i].St,Edge[i].Ed);48        Ans.push_back(Edge[i]);49    }50    Must=n-1-Count;51}52bool Kruskal2(){53    sort(Edge+1,Edge+m+1,cmpa);54    for(int i=1;i<=n;i++) Fa[i]=i;55    k-=Must;56    for(int i=0;i<(int)Ans.size();i++){57        Merge(Ans[i].Ed,Ans[i].St);58    }59    for(int i=1;i<=m;i++){60        if(Edge[i].Type==0&&(!k)) continue;61        if(Edge[i].Type==1&&(k)) return false;62        if(Find(Edge[i].St)==Find(Edge[i].Ed)) continue;63        Merge(Edge[i].St,Edge[i].Ed);64        Ans.push_back(Edge[i]);65        if(Edge[i].Type==0) k--;66    }67    return (int)Ans.size()==n-1;68}69void Solve(){70    int In1,In2,In3;71    Ans.clear();Can=0;Must=0;72    scanf("%d%d%d",&n,&m,&k);73    for(int i=1;i<=m;i++){74        scanf("%d%d%d",&In1,&In2,&In3);75        Edge[i]={In1,In2,In3};76        if(In3==0) Can++;77    }78    if(!Get_Tog()){79        puts("no solution");80        return;81    }82    Kruskal1();83    if(Must>k) {puts("no solution");return;}84    if(!Kruskal2()){puts("no solution");return;}85    for(int i=0;i<(int)Ans.size();i++){86        printf("%d %d %d\n",Ans[i].St,Ans[i].Ed,Ans[i].Type);87    }88    return;89}90int main(){91    int c,T;92    freopen("rainbell.in","r",stdin);93    freopen("rainbell.out","w",stdout);94    scanf("%d%d",&c,&T);95    while(T-->0) Solve();96    return 0;97}