fork download
copy 
  1. // for input: 
  2. // 3
  3. // 10.7 8 18.9 
  4. // 6.6 11.2 13.7 
  5. // 14.1 13.8 9.4
  6. // 
  7. // the output is:
  8. // minimal difference between longest and shortest edge: 1.8
  9. // edges in the best solution: 
  10. // edge: 0 <- 0
  11. // edge: 1 <- 1
  12. // edge: 2 <- 2
  13. #include<iostream>
  14. #include<algorithm>
  15. #include<vector>
  16. #include<set>
  17. using namespace std;
  18.  
  19. int i,j,n,m;
  20.  
  21. float edges[100][100];
  22.  
  23. vector<float> arr;
  24.  
  25. bool find_path(const set<pair<int, int> >& E, int a, int n, vector<int>& last, vector<bool>& checked) {
  26.   for(int i = 0; i < n; ++i) {
  27.     if(!checked[i] && E.count(make_pair(a, i))) {
  28.       checked[i]=true;
  29.       int temp = last[i];
  30.       last[i]=a;
  31.       if (temp < 0 || find_path(E, temp, n, last, checked)) {
  32.         return true;
  33.       }
  34.       last[i]=temp;
  35.     }
  36.   }
  37.   return false;
  38. }
  39.  
  40. set<pair<int, int> >& Simple_Hungarian(const set<pair<int, int> >& E, int n) {
  41.   static set<pair<int, int> > ans;
  42.   static vector<int> last;
  43.   static vector<bool> checked;
  44.   ans.clear();
  45.   last.resize(n);
  46.   fill(last.begin(), last.end(), -1);
  47.   checked.resize(n);
  48.   for(int i = 0; i < n; ++i) {
  49.     fill(checked.begin(), checked.end(), false);
  50.     find_path(E, i, n, last, checked);
  51.   }
  52.  
  53.   for(int i = 0; i < n; ++i) {
  54.     if (last[i] >=0) 
  55.       ans.insert(make_pair(last[i], i));
  56.   }
  57.   return ans;
  58. }
  59.  
  60. int main() {
  61.   cin >> n;
  62.   for(i=0;i<n;i++) {
  63.     for(j=0;j<n;j++) {
  64.       cin >> edges[i][j];
  65.       arr.push_back(edges[i][j]);
  66.     }
  67.   }
  68.   sort(arr.begin(), arr.end());
  69.   arr.resize(distance(arr.begin(), unique(arr.begin(), arr.end())));
  70.   set<pair<int, int> > ans;
  71.   float ans_diff=-1;
  72.   for(int low_i = 0; low_i < (int)arr.size(); ++low_i) {
  73.     float low = arr[low_i];
  74.     int high_l = i, high_r = arr.size()-1, mid;
  75.     while(high_l <= high_r) {
  76.       mid = (high_l+high_r)/2;
  77.       float high = arr[mid];
  78.       set<pair<int, int> > filtered_edges;
  79.       for (int i = 0; i < n; i++) {
  80.         for (int j = 0; j < n; j++) {
  81.           if(edges[i][j] >= low && edges[i][j] <= high) {
  82.             filtered_edges.insert(make_pair(i,j));
  83.           }
  84.         }
  85.       }
  86.       const set<pair<int, int> >& max_match = Simple_Hungarian(filtered_edges, n);
  87.  
  88.       if ((int)max_match.size() == n) {
  89.         high_r = mid-1;
  90.       } else {
  91.         high_l = mid+1;
  92.       }
  93.     }
  94.     float high = arr[high_l];
  95.     if (high_l < (int) arr.size() && high_l >= low_i && (ans_diff < 0 || high-low < ans_diff)) {
  96.       ans_diff = high - low;
  97.       set<pair<int, int> > filtered_edges;
  98.       for (int i = 0; i < n; i++) {
  99.         for (int j = 0; j < n; j++) {
  100.           if(edges[i][j] >= low && edges[i][j] <= high) {
  101.             filtered_edges.insert(make_pair(i,j));
  102.           }
  103.         }
  104.       }
  105.       ans = Simple_Hungarian(filtered_edges, n);
  106.     }
  107.   }
  108.   cout << "minimal difference between longest and shortest edge: " << ans_diff << endl;
  109.  
  110.   cout << "edges in the best solution: " << endl;
  111.   for(i=0;i<n;i++) {
  112.     for(j=0;j<n;j++) {
  113.       if (ans.count(make_pair(i, j))) {
  114.         cout << "edge: " << i << " <- " << j << endl;
  115.       }
  116.     }
  117.   }
  118.  
  119.   return 0;
  120. }
  121.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
3
10.7 8 18.9 
6.6 11.2 13.7 
14.1 13.8 9.4
stdout
copy 
minimal difference between longest and shortest edge: 1.8
edges in the best solution: 
edge: 0 <- 0
edge: 1 <- 1
edge: 2 <- 2
https://ideone.com/33n2Tg
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!