构造具有度约束
问题描述:
我们需要构造与每个N个顶点的二分图中的任意二分图,在两个部分,并与等于M.构造具有度约束
- 左侧的顶点编号的总数边缘从1到N.
- 右边的顶点也从1到N编号。
- 每个顶点的度数大于或等于X,小于或等于Y.即,对于全部v,X≤deg(v)≤Y
给定四个整数N,M,X,Y,我们需要构造满足这个性质的二部图。如果不存在任何这样的图,那么也告诉相同的。 (1,1),(2,2)和(1,2) )
如果N = 2,M = 3,X = 1且Y = 1,则不存在二部图。
X * N <= M <= Y * N
否则,就不会有解决办法:
如何,如果
1 ≤ N ≤ 100
1 ≤ X ≤ Y ≤ N
0 ≤ M ≤ N * N
原来的问题link
答
显然,变量需要满足这个问题得到解决。
寻找边缘可以用波浪来完成。首先将第一组中的每个节点i
连接到第二组中的相应节点i
。在下一波中,将i
与(i + 1) mod N
连接起来。然后i
与(i + 2) mod N
等等。这将增加每个波的每个顶点的度数。每当你构建了M
边缘时停止。这也可能发生在一波。
答
ACM ICPC 2016印度预赛回合问题。
的比赛现在结束。我无法提交答案(即将在结束前10秒提交代码,并且我的互联网停止工作)。
d
相当于OP的版本问题中的X
。
D
相当于OP的版本问题中的Y
。
t
是测试用例的数量。
我根据链接中的原始问题制作了代码。
逻辑类似于 Nico Schertler的一个。我的复杂性会更复杂一点,因为我没有连接 th节点到x
th迭代中的i
,而是使用了一组找到未连接的范围[1..N]
中的第一个元素并将它们连接起来。
这是我的代码:
#include <bits/stdc++.h>
using namespace std;
int main() {
int t, n, m, d, D;
cin >> t;
while(t--) {
cin >> n >> m >> d >> D;
if(n*D < m || n*d > m)
printf("-1\n");
else {
vector <set <int> > v(n);
int edges = 0, count = 0;
while(count != d) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(v[i].find(j) == v[i].end()) {
v[i].insert(j);
++edges;
break;
}
if(edges == m)
break;
}
if(edges == m)
break;
}
++count;
}
while(edges < m) {
for(int i = 0; i < n; i++) {
if(v[i].size() == D)
continue;
for(int j = 0; j < n; j++) {
if(v[i].find(j) == v[i].end()) {
v[i].insert(j);
++edges;
break;
}
if(edges == m)
break;
}
if(edges == m)
break;
}
}
for(int i = 0; i < n; i++) {
set <int>::iterator it = v[i].begin();
for(; it != v[i].end(); ++it) {
printf("%d %d\n", i+1, (*it)+1);
}
}
}
}
return 0;
}
我不知道这个代码是否正确与否。
不错的问题。请说明你到目前为止所做的一切。 –
@AbhishekBansal所以,重点是假设我们想要在这两个约束之间有一个度,所以我们可以顺序地将一个顶点从左边映射到右边的X个顶点。然后尝试分配到剩余的所有顶点。再次增加一个边以将它们总结为M.但它变得非常复杂。所以想着是否缺少一些微不足道的方法 – HackAround
想一想(可能)的方向是什么:从运输问题来看,你有n个来源,n个目的地(以及一些额外的容量/需求限制)。 –