文章目录

题目题目大意分析代码

题目

st-Spanning Tree

题目大意

给出一个$n$（$2\le n\le 200000$）个点$m$（$1\le m\le 400000$）条边的图（连通，无重边，无自环）和$s,t,d_s,d_t$。输出该图的一个生成树，使得$s$点的度数不超过$d_s$，$t$点度数不超过$d_t$。

分析

先把$s$点$t$点扯掉，使图变成几个连通块。由于两棵树之间任意连一条边就变成了一棵树，所以我们可以先把这几个连通块分别做生成树，然后再通过$s$和$t$使它们变成一棵树。

把缩过的点分成下面三种情况：

只和$s$相连（下图中的$A$）只和$t$相连（下图中的$B$）和$s$，$t$都相连（下图中的$C$）

当然，如果有点，既不和$s$也不和$t$相连，就无解。 显然$A-s$、$B-t$的边全部要选，否则图将不连通。 接下来只需要考虑$C$类的点。 那么只需要让某个点$C_x$把两边的边（$C_x-s$，$C_x-t$）都保留，剩下的点只留一边的边即可。

具体来说，先要判断现在的$d_x$和$d_y$是否满足$d_x+d_y-1\ge \text{cnt}$（$\text{cnt}$是$C$类点的个数）（减一是有两个边连在同一个点$C_x$上，大于等于是因为度数不超过$d_x$、$d_t$都行），不满足就不可能。 然后，你可以直接把$t$的度数用完，因为$s$的度数完全可以是$1$。 当然，如果这个时候$d_x$或者$d_t$为$0$，就不可能了。

还有一种情况，$s$与$t$之间有一条边且这条边是割边，那么必须加入边$s-t$。但是你不用写Tarjan来判断，只需要看最后的图连不连通（因为原图保证了连通，所以这时候肯定有解）（即，选出的边数是否等于$n-1$），不连通就把$s-t$放进去就行了。

代码

没有用并查集，有点慢。

#include<bits/stdc++.h> using namespace std; int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9') f|=c=='-',c=getchar(); while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar(); return f?-x:x; } #define MAXN 200000 #define NO return puts("No"),0 vector<int> G[MAXN+5]; vector<pair<int,int> > Ans; int Block[MAXN+5],NodeS[MAXN+5],NodeT[MAXN+5]; void dfs(int u,int id){ Block[u]=id; for(int v:G[u]) if(!Block[v]){ Ans.push_back({u,v}); dfs(v,id); } } int main(){ int N=read(),M=read(); for(int i=1;i<=M;i++){ int u=read(),v=read(); G[u].push_back(v); G[v].push_back(u); } int S=read(),T=read(),DS=read(),DT=read(); int id=0; Block[S]=-1,Block[T]=-2;//把s,t拆出来 for(int i=1;i<=N;i++) if(!Block[i]) dfs(i,++id);//对每个连通块生成树 set<int> toS,toT,OneS,OneT,Two; for(int v:G[S]) if(v!=T) toS.insert(Block[v]),NodeS[Block[v]]=v; for(int v:G[T]) if(v!=S) toT.insert(Block[v]),NodeT[Block[v]]=v; //缩点连边 for(int i=1;i<=id;i++){ if(toS.count(i)&&toT.count(i)) Two.insert(i); else if(toS.count(i)) OneS.insert(i); else if(toT.count(i)) OneT.insert(i); else NO; } //上面说的三种情况 if(OneS.size()>DS||OneT.size()>DT) NO; for(int i:OneS) Ans.push_back({S,NodeS[i]}); for(int i:OneT) Ans.push_back({T,NodeT[i]}); DS-=OneS.size(),DT-=OneT.size(); //只有一边的全部连 if(!DS||!DT||DS+DT-1<Two.size()) NO; DT=min(DT,int(Two.size()));//t尽量全部连 for(int i:Two){ if(DT>0) Ans.push_back({T,NodeT[i]}),DT--; if(DT==0) Ans.push_back({S,NodeS[i]});//s与t有一个重合的 } if(Ans.size()<N-1) Ans.push_back({S,T});//看加不加s-t的边 puts("Yes"); for(auto i:Ans) printf("%d %d\n",i.first,i.second); }