首页 > 代码库 > CodeForces 723F st-Spanning Tree
CodeForces 723F st-Spanning Tree
$dfs$，构造。
类似于$k$度限制生成树的想法，可以将$s$和$t$先从图中删去，将剩下的部分求连通块，每个连通块内部很容易构造生成树，每个连通块缩成一个点来处理。
连通块分三种：
$1$.只与$s$有边
$2$.只与$t$有边
$3$.与$s$和$t$都有边
前两种没办法，只能和$s$和$t$相连。如果没有第三种，那么$s$和$t$之前需要连一条边。如果有第三种，在第三种里面选出一个来和$s$、$t$连，其余的当做第一种和第二种处理。
连边的过程中判断$s$和$t$的度是否满足条件即可。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-10;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}struct Edge{ int a,b,nx;}e[800010];int h[200010];int n,m,sz,s,t,ds,dt;int belong[200010],block;vector<int>ansx,ansy;struct X{ int e1,e2;}w[200010];set<int>SS,TT;void add(int a,int b){ e[sz].a=a; e[sz].b=b; e[sz].nx=h[a]; h[a]=sz++;}void dfs(int x){ belong[x]=block; for(int i=h[x];i!=-1;i=e[i].nx) { int to=e[i].b; if(belong[to]!=0) continue; if(to==s) continue; if(to==t) continue; ansx.push_back(x); ansy.push_back(to); dfs(to); }}int main(){ cin>>n>>m; memset(h,-1,sizeof h); for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; add(a,b); add(b,a); } cin>>s>>t>>ds>>dt; for(int i=1;i<=n;i++) { if(i==s) continue; if(i==t) continue; if(belong[i]!=0) continue; block++; dfs(i); } for(int i=1;i<=block;i++) w[i].e1=w[i].e2=-1; for(int i=0;i<sz;i=i+2) { if(e[i].a==s&&(e[i].b!=s&&e[i].b!=t)) { SS.insert(belong[e[i].b]); if(w[belong[e[i].b]].e1==-1) w[belong[e[i].b]].e1=i; } if(e[i].b==s&&(e[i].a!=s&&e[i].a!=t)) { SS.insert(belong[e[i].a]); if(w[belong[e[i].a]].e1==-1) w[belong[e[i].a]].e1=i; } if(e[i].a==t&&(e[i].b!=s&&e[i].b!=t)) { TT.insert(belong[e[i].b]); if(w[belong[e[i].b]].e2==-1) w[belong[e[i].b]].e2=i; } if(e[i].b==t&&(e[i].a!=s&&e[i].a!=t)) { TT.insert(belong[e[i].a]); if(w[belong[e[i].a]].e2==-1) w[belong[e[i].a]].e2=i; } } int sum=0; vector<int>tmp; for(int i=1;i<=block;i++) { if(SS.count(i)&&TT.count(i)) { tmp.push_back(i); continue; } if(SS.count(i)) { ansx.push_back(e[w[i].e1].a); ansy.push_back(e[w[i].e1].b); ds--; } else { ansx.push_back(e[w[i].e2].a); ansy.push_back(e[w[i].e2].b); dt--; } } if(tmp.size()==0) { ansx.push_back(s); ansy.push_back(t); ds--; dt--; } else { ansx.push_back(e[w[tmp[0]].e1].a); ansy.push_back(e[w[tmp[0]].e1].b); ansx.push_back(e[w[tmp[0]].e2].a); ansy.push_back(e[w[tmp[0]].e2].b); ds--; dt--; for(int i=1;i<tmp.size();i++) { if(ds>0) { ansx.push_back(e[w[tmp[i]].e1].a); ansy.push_back(e[w[tmp[i]].e1].b); ds--; } else if(dt>0) { ansx.push_back(e[w[tmp[i]].e2].a); ansy.push_back(e[w[tmp[i]].e2].b); dt--; } } } if(ds<0||dt<0||ansx.size()!=n-1) printf("No\n"); else { printf("Yes\n"); for(int i=0;i<ansx.size();i++) printf("%d %d\n",ansx[i],ansy[i]); } return 0;}
CodeForces 723F st-Spanning Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。