http://codeforces.com/contest/723/problem/F
You are given an undirected connected graph consisting of n vertices and m edges. There are no loops and no multiple edges in the graph.
You are also given two distinct vertices s and t, and two values ds and dt. Your task is to build any spanning tree of the given graph (note that the graph is not weighted), such that the degree of the vertex s doesn't exceed ds, and the degree of the vertex t doesn't exceed dt, or determine, that there is no such spanning tree.
The spanning tree of the graph G is a subgraph which is a tree and contains all vertices of the graph G. In other words, it is a connected graph which contains n - 1 edges and can be obtained by removing some of the edges from G.
The degree of a vertex is the number of edges incident to this vertex.
Input
The first line of the input contains two integers n and m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ min(400 000, n·(n - 1) / 2)) — the number of vertices and the number of edges in the graph.
The next m lines contain the descriptions of the graph's edges. Each of the lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) — the ends of the corresponding edge. It is guaranteed that the graph contains no loops and no multiple edges and that it is connected.
The last line contains four integers s, t, ds, dt (1 ≤ s, t ≤ n, s ≠ t, 1 ≤ ds, dt ≤ n - 1).
Output
If the answer doesn't exist print "No" (without quotes) in the only line of the output.
Otherwise, in the first line print "Yes" (without quotes). In the each of the next (n - 1) lines print two integers — the description of the edges of the spanning tree. Each of the edges of the spanning tree must be printed exactly once.
You can output edges in any order. You can output the ends of each edge in any order.
If there are several solutions, print any of them.
题意：
给定一个无向图，构造一个生成树，使得s的度数不超过ds，t的度数不超过dt。
思路：
即选择若干边使得图连通且不含环，使得s的度数不超过ds，t的度数不超过dt。
1.先把所有不影响s，t的度数的边所连的点都并起来，用并查集。这一步之后，形成了若干个集合，包括s，t以及其他集合，“其他集合”之间不能连通，必须通过s，t连通。
这一步之后的大致状况：（打√的是最后选中的边）
2.维护所有的集合是否与s，t有边相连。对于所有只与s或t相连的集合，必须连s或t，否则图不能连通。过程中如果度数超过就结束。
3.对于与s，t均相连的集合，选任一个与s，t均相连，然后s，t就在一个集合里了，剩下的只连s或t就行了，注意这里连s或t的情况，如果s以及度数满了而t还可以连，当然连t，而不能连s返回失败。
4.最后考虑s和t直接相连的情况（与3相比），因为直接连st导致s和t的度数均加1，选一个中间集合连st也是s和t度数均加1，显然优先选一个中间结点。但如果不存在与s，t均相连的集合，就需要直接连s，t。
细节不少。
#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+1000
int n,m,s,t,ds,dt,p[maxn];
bool ls[maxn],lt[maxn],link;
int links[maxn],linkt[maxn];
vector<int> G[maxn];
vector<pair<int,int> > ans;
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
bool solve()
{
for(int u=1;u<=n;u++)if(u!=s&&u!=t)
{
for(int j=0;j<G[u].size();j++)
{
int v=G[u][j];
if(v!=s&&v!=t)
{
int x=find(u),y=find(v);
if(x!=y)p[x]=y,ans.push_back(make_pair(u,v));
}
}
}
for(int j=0;j<G[s].size();j++)if(G[s][j]!=t){int x=find(G[s][j]);ls[x]=1;links[x]=G[s][j];}
for(int j=0;j<G[t].size();j++)if(G[t][j]!=s){int x=find(G[t][j]);lt[x]=1;linkt[x]=G[t][j];}
for(int i=1;i<=n;i++)
{
if(ls[i]&&!lt[i])ds--,p[find(s)]=i,ans.push_back(make_pair(s,links[i]));
else if(!ls[i]&<[i])dt--,p[find(t)]=i,ans.push_back(make_pair(t,linkt[i]));
if(ds<0||dt<0)return false;
}
for(int i=1;i<=n;i++)if(ls[i]&<[i])
{
if(find(s)!=find(i)&&ds)
{
ds--;
p[find(s)]=i;
ans.push_back(make_pair(s,links[i]));
}
if(find(t)!=find(i)&&dt)
{
dt--;
p[find(t)]=i;
ans.push_back(make_pair(t,linkt[i]));
}
if(find(s)!=i||find(t)!=i)return false;
}
bool ok=1;
for(int i=2;i<=n;i++)if(find(i)!=find(1))ok=0;
if(ok)return 1;
for(int j=0;j<G[s].size();j++)if(G[s][j]==t)link=1;
if(ds&&dt&&link)p[find(s)]=find(t),ans.push_back(make_pair(s,t));
ok=1;
for(int i=2;i<=n;i++)if(find(i)!=find(1))ok=0;
return ok;
}
void input()
{
cin>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
scanf("%d%d%d%d",&s,&t,&ds,&dt);
for(int i=1;i<=n;i++)p[i]=i;
}
int main()
{
//freopen("input.in","r",stdin);
input();
if(solve()==0)puts("No");
else
{
puts("Yes");
for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);
}
return 0;
}
京公网安备 11010502036488号