fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. double valor[60+60][60+60];
  10. int cap[60+60][60+60], orCap[60+60][60+60];
  11. bool vis[60+60];
  12. int P[60+60];
  13.  
  14. vector<vector<int > > g1, g2;
  15.  
  16. int n, m;
  17.  
  18. bool bfs(vector<vector<int> > g)
  19. {
  20.     queue<int> q;
  21.     q.push(0);
  22.     memset(vis, false, sizeof(vis));
  23.     memset(P, -1, sizeof(P));
  24.     vis[0] = true;
  25.     while (q.empty() == false)
  26.     {
  27.         int v = q.front();
  28.         q.pop();
  29.         for (int i = 0; i < g[v].size(); i++)
  30.         {
  31.             int u = g[v][i];
  32.             if (cap[v][u] > 0 && !vis[u])
  33.             {
  34.                 vis[u] = true;
  35.                 q.push(u);
  36.                 P[u] = v;
  37.             }
  38.         }
  39.     }
  40.     if (vis[n+m+1]) return true;
  41.     return false;
  42. }
  43.  
  44. double addFlow()
  45. {
  46.     int v = n + m + 1;
  47.     int minCap = (1<<30);
  48.     while (P[v] != -1)
  49.     {
  50.         minCap = min(minCap, cap[ P[v] ][v]);
  51.         v = P[v];
  52.     }
  53.     v = n + m + 1;
  54.     double res = 0;
  55.     while (P[v] != -1)
  56.     {
  57.         int u = P[v];
  58.         cap[u][v] -= minCap;
  59.         cap[v][u] += minCap;
  60.         res += valor[u][v] * (double)minCap;
  61.         v = u;
  62.     }
  63.     return res;
  64. }
  65.  
  66. int main()
  67. {
  68.     int T = 0;
  69.     while (cin>>n>>m)
  70.     {
  71.         T++;
  72.         if (n + m == 0) break;
  73.         g1.clear();
  74.         g2.clear();
  75.         g1.resize(60+60);
  76.         g2.resize(60+60);
  77.         memset(cap, 0, sizeof(cap));
  78.         memset(orCap, 0, sizeof(orCap));
  79.         for (int i = 0; i < 60+60; i++)
  80.         {
  81.             for (int j = 0; j < 60+60; j++)
  82.             {
  83.                 valor[i][j] = 0;
  84.             }
  85.         }
  86.         for (int i = 1; i <= n; i++)
  87.         {
  88.             cin>>cap[0][i];
  89.         }
  90.         for (int i = 1; i <= m; i++)
  91.         {
  92.             cin>>cap[n+i][n+m+1];
  93.         }
  94.  
  95.         for (int i = 0; i < 60+60; i++)
  96.         {
  97.             for (int j = 0; j < 60+60; j++)
  98.             {
  99.                 orCap[i][j] = cap[i][j];;
  100.             }
  101.         }
  102.  
  103.         for (int i = 1; i <= m; i++)
  104.         {
  105.             g1[n+i].push_back(n+m+1);
  106.             g2[n+i].push_back(n+m+1);
  107.         }
  108.  
  109.         for (int i = 1; i <= n; i++)
  110.         {
  111.             g1[0].push_back(i);
  112.             g2[0].push_back(i);
  113.             vector<pair<double, int> > v;
  114.             for (int j = 1; j <= m; j++)
  115.             {
  116.                 cin>>valor[i][n+j];
  117.                 v.push_back( make_pair( valor[i][n+j], n + j ) );
  118.             }
  119.             sort(v.begin(),v.end());
  120.             for (int j = 0; j < v.size(); j++)
  121.             {
  122.                 if (v[j].first == -1) continue;
  123.                 g1[i].push_back(v[j].second);
  124.                 cap[i][v[j].second] = (1<<30);
  125.             }
  126.             //reverse(v.begin(), v.end());
  127.             for (int j = v.size()-1; j >= 0; j--)
  128.             {
  129.                 if (v[j].first == -1) continue;
  130.                 g2[i].push_back(v[j].second);
  131.             }
  132.         }
  133.  
  134.         double f1 = 0, f2 = 0;
  135.         while (bfs(g1))
  136.         {
  137.             f1 += addFlow();
  138.             //cout<<f1<<endl;
  139.         }
  140.  
  141.         for (int i = 0; i < 60+60; i++)
  142.         {
  143.             for (int j = 0; j < 60+60; j++)
  144.             {
  145.                 cap[i][j] = orCap[i][j];
  146.             }
  147.         }
  148.  
  149.         while (bfs(g2))
  150.         {
  151.             f2 += addFlow();
  152.             cout<<"adsfsdfsa"<<endl;
  153.         }
  154.  
  155.         cout<<"Problem "<<T<<": "<<f1<<" to "<<f2<<endl;;
  156.  
  157.     }
  158.     return 0;
  159. }
  160.  
Success #stdin #stdout 0s 15472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yvi9cQ
language:
C++ (gcc 8.3)
created:
7 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!