文章目录题目题目大意分析代码
题目
st-SpanningTree
题目大意
给出一个nnn（2≤n≤200 0002\leqn\leq200\0002≤n≤200 000）个点mmm（1≤m≤400 0001\leqm\leq400\0001≤m≤400 000）条边的图（连通，无重边，无自环）和s,t,ds,dts,t,d_s,d_ts,t,ds,dt。输出该图的一个生成树，使得sss点的度数不超过dsd_sds，ttt点度数不超过dtd_tdt。
分析
先把sss点ttt点扯掉，使图变成几个连通块。由于两棵树之间任意连一条边就变成了一棵树，所以我们可以先把这几个连通块分别做生成树，然后再通过sss和ttt使它们变成一棵树。
把缩过的点分成下面三种情况：
只和sss相连（下图中的AAA）只和ttt相连（下图中的BBB）和sss，ttt都相连（下图中的CCC）
当然，如果有点，既不和sss也不和ttt相连，就无解。显然A−sA-sA−s、B−tB-tB−t的边全部要选，否则图将不连通。接下来只需要考虑CCC类的点。那么只需要让某个点CxC_xCx把两边的边（Cx−sC_x-sCx−s，Cx−tC_x-tCx−t）都保留，剩下的点只留一边的边即可。
具体来说，先要判断现在的dxd_xdx和dyd_ydy是否满足dx+dy−1≥cntd_x+d_y-1\geq\text{cnt}dx+dy−1≥cnt（cnt\text{cnt}cnt是CCC类点的个数）（减一是有两个边连在同一个点CxC_xCx上，大于等于是因为度数不超过dxd_xdx、dtd_tdt都行），不满足就不可能。然后，你可以直接把ttt的度数用完，因为sss的度数完全可以是111。当然，如果这个时候dxd_xdx或者dtd_tdt为000，就不可能了。
还有一种情况，sss与ttt之间有一条边且这条边是割边，那么必须加入边s−ts-ts−t。但是你不用写Tarjan来判断，只需要看最后的图连不连通（因为原图保证了连通，所以这时候肯定有解）（即，选出的边数是否等于n−1n-1n−1），不连通就把s−ts-ts−t放进去就行了。
代码
没有用并查集，有点慢。
#include<bits/stdc++.h>usingnamespacestd;intread(){intx=0;boolf=0;charc=getchar();while(c<'0'||c>'9')f|=c=='-',c=getchar();while(c>='0'&&c<='9')x=x*10+(c^48),c=getchar();returnf?-x:x;}#defineMAXN200000#defineNOreturnputs("No"),0vector<int>G[MAXN+5];vector<pair<int,int>>Ans;intBlock[MAXN+5],NodeS[MAXN+5],NodeT[MAXN+5];voiddfs(intu,intid){Block[u]=id;for(intv:G[u])if(!Block[v]){Ans.push_back({u,v});dfs(v,id);}}intmain(){intN=read(),M=read();for(inti=1;i<=M;i++){intu=read(),v=read();G[u].push_back(v);G[v].push_back(u);}intS=read(),T=read(),DS=read(),DT=read();intid=0;Block[S]=-1,Block[T]=-2;//把s,t拆出来for(inti=1;i<=N;i++)if(!Block[i])dfs(i,++id);//对每个连通块生成树set<int>toS,toT,OneS,OneT,Two;for(intv:G[S])if(v!=T)toS.insert(Block[v]),NodeS[Block[v]]=v;for(intv:G[T])if(v!=S)toT.insert(Block[v]),NodeT[Block[v]]=v;//缩点连边for(inti=1;i<=id;i++){if(toS.count(i)&&toT.count(i))Two.insert(i);elseif(toS.count(i))OneS.insert(i);elseif(toT.count(i))OneT.insert(i);elseNO;}//上面说的三种情况if(OneS.size()>DS||OneT.size()>DT)NO;for(inti:OneS)Ans.push_back({S,NodeS[i]});for(inti: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(inti: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(autoi:Ans)printf("%d%d\n",i.first,i.second);}
