fork download 
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string.h>
  5. #include <queue>
  6. using namespace std;
  7.  
  8. typedef pair<int,int> pii;
  9.  
  10.  
  11. const int inf = 0x3F3F3F3F;
  12.  
  13. struct Edge
  14. {
  15.     int next;
  16.         int inv;        
  17.         int flow;       
  18.         int cap;        
  19.         int cost;                       
  20.         Edge(int next, int inv, int cap, int cost) : next(next), inv(inv), flow(0), cap(cap), cost(cost) {}
  21. };
  22.  
  23.         int n;                          
  24.         vector<Edge> e[400];
  25.         int phi[400];   
  26.         int d[400];
  27.         int f[400];
  28.         int from[400];
  29.  
  30.         inline void AddEdge(int a, int b, int cap, int cost)
  31.         {
  32.                 e[a].push_back(Edge(b, e[b].size(), cap, cost));
  33.                 e[b].push_back(Edge(a, e[a].size() - 1, 0, -cost));
  34.         }
  35.  
  36.         int A[100][100];
  37.  
  38.         int main()
  39.         {
  40.  
  41.                 int resultFlow = 0, resultCost = 0;
  42.                 int N,S;
  43.                 cin >> N >> S;
  44.                 for (int i=0;i<N;i++)
  45.                         for (int j=i;j<N;j++)
  46.                                 cin >> A[i][j];
  47.  
  48.                 int source = 0;
  49.                 int sink = 2*N + S + 1;
  50.  
  51.                 for (int i=1;i<=S+N;i++)
  52.                         AddEdge(0,i,1,0);
  53.                 for (int i=S+N+1;i<=S+2*N;i++)
  54.                         AddEdge(i,sink,1,0);
  55.                 for (int i=1;i<=S;i++)
  56.                         for (int j=0;j<N;j++)
  57.                                 AddEdge( i, S+N+1+j ,1,A[0][j]);
  58.                 for (int i=1;i<N;i++)
  59.                         for (int j=i;j<N;j++)
  60.                                 AddEdge( S+i, S+N+j+1 ,1,A[i][j]);
  61.                 n = sink+1;
  62.  
  63.                 while (resultFlow != N)
  64.                 {
  65.                         memset(f,0,sizeof(f));
  66.                         memset(d,0x3F,sizeof(d));
  67.                         d[source] = 0;
  68.                         priority_queue< pii, vector<pii>, greater<pii> > Q;
  69.                         Q.push( pii(0,source) );
  70.                         while (!Q.empty()){
  71.                                 pii U = Q.top();
  72.                                 int t = U.first;
  73.                                 int i = U.second;
  74.                                 Q.pop();
  75.                                 if (f[i]) continue;
  76.                                 f[i] = 1;
  77.  
  78.                                 for(int j = 0; j < e[i].size(); ++j)
  79.                                         if(e[i][j].cap > e[i][j].flow)
  80.                                         {
  81.                                                 int a = e[i][j].next;
  82.                                                 if(!f[a] && d[a] > d[i] + e[i][j].cost + phi[i] - phi[a])
  83.                                                 {
  84.                                                         d[a] = d[i] + e[i][j].cost + phi[i] - phi[a];
  85.                                                         from[a] = e[i][j].inv;
  86.                                                         Q.push( pii( d[a] ,a) );
  87.                                                 }
  88.                                         }
  89.                         }
  90.  
  91.  
  92.                         if(!f[sink]) break;
  93.  
  94.                         for(int i = 0; i < n; ++i)
  95.                                 phi[i] += f[i] ? d[i] : d[sink];
  96.  
  97.                         int augFlow = inf, augCost = 0;
  98.  
  99.                         for(int i = sink; i != source; )
  100.                         {
  101.                                 int a = e[i][from[i]].next;
  102.                                 int b = e[i][from[i]].inv;
  103.                                 augFlow = min(augFlow, e[a][b].cap - e[a][b].flow);
  104.                                 augCost += e[a][b].cost;
  105.                                 i = a;
  106.                         }
  107.  
  108.                         for(int i = sink; i != source; )
  109.                         {
  110.                                 int a = e[i][from[i]].next;
  111.                                 int b = e[i][from[i]].inv;
  112.                                 e[a][b].flow += augFlow;
  113.                                 e[i][from[i]].flow -= augFlow;
  114.                                 i = a;
  115.                         }
  116.  
  117.                         resultFlow += augFlow;
  118.                         resultCost += augFlow * augCost;
  119.                 }
  120.                 cout << resultCost << endl;
  121.         }
Time limit exceeded #stdin #stdout 5s 3148KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/vftHD5
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!