构造具有度约束

我们需要构造与每个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

来源

2016-10-22 HackAround

不错的问题。请说明你到目前为止所做的一切。 –

@AbhishekBansal所以，重点是假设我们想要在这两个约束之间有一个度，所以我们可以顺序地将一个顶点从左边映射到右边的X个顶点。然后尝试分配到剩余的所有顶点。再次增加一个边以将它们总结为M.但它变得非常复杂。所以想着是否缺少一些微不足道的方法 – HackAround

想一想（可能）的方向是什么：从运输问题来看，你有n个来源，n个目的地（以及一些额外的容量/需求限制）。 –

显然，变量需要满足这个问题得到解决。

寻找边缘可以用波浪来完成。首先将第一组中的每个节点i连接到第二组中的相应节点i。在下一波中，将i与(i + 1) mod N连接起来。然后i与(i + 2) mod N等等。这将增加每个波的每个顶点的度数。每当你构建了M边缘时停止。这也可能发生在一波。

来源

2016-10-22 16:48:11

ACM ICPC 2016印度预赛回合问题。

Link

的比赛现在结束。我无法提交答案（即将在结束前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; 
}

我不知道这个代码是否正确与否。

来源

2016-10-22 16:58:27 Shubham

构造具有度约束

回答

相关问题