fork download 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 105;
  4. const long long inf = -1e15;
  5. int n , m;
  6. int a[N] , b[N] , c[N];
  7. long long dist[N];
  8. int pre[N];
  9. int cap[N][N];
  10. int cst[N][N];
  11. bool solve(vector < pair < int , int > > &v){
  12.     for(int i = 0 ; i <= n + 2 ; ++i){
  13.         dist[i] = inf;
  14.         pre[i] = -1;
  15.     }
  16.     dist[0] = 0;
  17.     pre[0] = 0;
  18.     for(int i = 0 ; i <= n + 2 ; ++i){
  19.         for(auto it : v){
  20.             int a = it.first;
  21.             int b = it.second;
  22.             if(cap[a][b] > 0){
  23.                 if(dist[a] != inf){
  24.                     if(dist[b] < dist[a] + cst[a][b]){
  25.                         dist[b] = dist[a] + cst[a][b];
  26.                         pre[b] = a;
  27.                     }
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     return (dist[n + 2] != inf);
  33. }
  34. bool check(int val){
  35.     memset(cap , 0 , sizeof(cap));
  36.     memset(cst , 0 , sizeof(cst));
  37.     vector < pair < int , int > > v;
  38.     v.clear();
  39.     cap[0][1] = val;
  40.     v.emplace_back(make_pair(0 , 1));
  41.     v.emplace_back(make_pair(1 , 0));
  42.     for(int i = 1 ; i <= n ; ++i){
  43.         cap[1][i + 1] = (b[i] - a[i]) / c[i];
  44.         v.emplace_back(make_pair(1 , i + 1));
  45.         cst[1][i + 1] = c[i];
  46.         cst[i + 1][1] = -c[i];
  47.         v.emplace_back(make_pair(i + 1 , 1));
  48.         cap[i + 1][n + 2] = (b[i] - a[i]) / c[i];
  49.         v.emplace_back(make_pair(i + 1 , n + 2));
  50.         v.emplace_back(make_pair(n + 2 , i + 1));
  51.     }
  52.     long long ans = 0;
  53.     for(int i = 1 ; i <= n ; ++i){
  54.         ans += a[i];
  55.     }
  56.     while(solve(v)){
  57.         int node = n + 2;
  58.         int flow = val;
  59.         while(node){
  60.             flow = min(flow , cap[pre[node]][node]);
  61.             node = pre[node];
  62.         }
  63.         node = n + 2;
  64.         while(node){
  65.             ans += cst[pre[node]][node] * flow;
  66.             cap[pre[node]][node] -= flow;
  67.             cap[node][pre[node]] += flow;
  68.             node = pre[node];
  69.         }
  70.     }
  71.     return ans >= m * n;
  72. }
  73. int main(){
  74.     scanf("%d %d" , &n , &m);
  75.     for(int i = 1 ; i <= n ; ++i){
  76.         scanf("%d %d %d" , a + i , b + i , c + i);
  77.     }
  78.     int l = 1;
  79.     int r = 1e4 + 4;
  80.     if(!check(r)){
  81.         printf("-1\n");
  82.     }
  83.     else{
  84.         while(l < r){
  85.             int mid = l + r >> 1;
  86.             if(check(mid)){
  87.                 r = mid;
  88.             }
  89.             else{
  90.                 l = mid + 1;
  91.             }
  92.         }
  93.         printf("%d\n" , l);
  94.     }
  95. }
  96.  
Success #stdin #stdout 0s 3564KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/wcFWT2
language:
C++14 (gcc 8.3)
created:
8 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!