構造具有度約束

我們需要構造與每個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

構造具有度約束

回答

相關問題