UVa 11167: Monkeys in the Emei Mountain

Problem Statement:
UVa 11167 - Monkeys in the Emei Mountain

Solution:
A pretty tough maxflow problem. Oh yes, this is a bipartite matching problem between N monkeys and 50000 time intervals. The simplest way to think about this problem is to have N nodes representing monkeys, 50000 nodes representing time intervals, and two nodes S and T which are source and sink respectively. A monkey has to drink v times, hence we add an edge between S and that monkey with capacity v. This monkey can drink from time interval s to t, so we add an edge to each time interval from s to t by capacity 1 each. Finally, each time interval can only be shared between M monkeys, so for each time interval we add an edge to T with capacity M. The maximum flow from S to T will give us the maximum bipartite matching between the monkeys and the time intervals. If this maximum flow exactly equals to the total times all monkeys have to drink, we have found a valid matching.



However, that is only half of the story. If we implement it directly using 50000 time intervals, we are faced with a huge running time (since it is \(O(VE^2)\), with V at least 50000 and E is \(O(V^2)\), with best case running time of \(O(V^2)\), still too big). Hence we need to consider the time intervals in a more compressed manner. The easiest way to do this is by breaking the intervals (s,t) into smaller intervals only if there are intersections with other intervals. (E.g., if we have monkey 1 drinking from interval (3, 7), and monkey 2 drinking from interval (4, 12), we can break the intervals into (3, 4), (4, 7), and (7, 12) ). What is the bound of the number of intervals in the end? We can think of this incrementally, in each addition of monkey, we will have to break at most two existing interval, introducing 2 new interval segments. Hence in total we will have \(O(N)\) intervals. Thus we have pushed V to \(O(N)\). :D

The last thing needed is a careful implementation and a strong heart to face several WAs..

Implementation:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;

#define NMAX 50155
int INF = (int) 1e9;

int N, M;
int S, T;
vector<vector<pair<int,pair<int,int> > > >adj;
vector<pair<int,int> > edges;
vector<pair<int,int> > node;
vector<pair<int,int> > st;
int mark[NMAX];
int idx[NMAX];
int par[NMAX];
int rel[NMAX];
int required;
int cnt;

int augment_path(int v, int mf){
 if(v == S){
  //printf("%d ", v);
  return mf;
 }
 int u = par[v];
 int k = rel[v];
 int m = adj[u][k].second.first;
 int n = adj[u][k].second.second;
 bool back_edge = false;
 if(edges[m].first == 0) back_edge = true;
 if(back_edge){
  mf = min(mf, edges[n].second);
 } else {
  mf = min(mf, edges[m].first - edges[m].second);
 }
 mf = augment_path(u, mf);
 //printf("%d ", v);
 if(back_edge){
  edges[n].second -= mf;
 } else {
  edges[m].second += mf;
 }
 return mf;
}

bool edmond_karps(){
 int maxflow = 0;
 while(1){
  bool can_augment = false;
  for(int i=0;i<cnt;++i) par[i] = -1;
  par[T] = -1;
  queue<int> q;
  q.push(S);
  par[S] = S;
  while(!q.empty()){
   int u = q.front();
   q.pop();
   for(int i=0;i<adj[u].size();++i){
    int v = adj[u][i].first;
    int m = adj[u][i].second.first;
    int n = adj[u][i].second.second;
    if(par[v] != -1) continue;
    if(edges[m].first - edges[m].second > 0 ||
       edges[n].second > 0) {
     par[v] = u;
     rel[v] = i;
     if(v == T) {
      can_augment = true;
      break;
     } else {
      q.push(v);
     }
    }
   }
   if(can_augment) break;
  }
  if(can_augment){
   maxflow += augment_path(T, INF);
   //printf("\n");
   if(maxflow == required) break;
  } else {
   break;
  }
 }
 return (maxflow == required);
}

void add_edge(int u, int v, int cap){
 adj[u].push_back(make_pair(v, make_pair(edges.size(), edges.size()+1)));
 adj[v].push_back(make_pair(u, make_pair(edges.size()+1, edges.size())));
 edges.push_back(make_pair(cap, 0));
 edges.push_back(make_pair(0, 0));
}


int main(){
 int tc = 1;
 while(scanf("%d", &N), N!=0){
  scanf("%d", &M);
  int v, s, t;
  node = vector<pair<int,int> > (NMAX);
  adj = vector<vector<pair<int, pair<int,int> > > > (NMAX);
  edges.clear();
  st.clear();
  S = NMAX-2;
  T = NMAX-1;
  required = 0;
  for(int i=0;i<=50000;++i) mark[i] = 0;
  for(int i=0;i<N;++i){
   scanf("%d %d %d", &v, &s, &t);
   add_edge(S, i, v);
   st.push_back(make_pair(s,t));
   required += v;
   mark[s] = 1;
   mark[t] = 1;
  }
  cnt = N;
  int prev = -1;
  for(int j=0;j<=50000;++j){
   if(mark[j]){
    if(prev == -1) {
     prev = j;
    } else {
     node[cnt] = make_pair(prev,j);
     idx[prev] = cnt;
     add_edge(cnt, T, (j - prev)*M);
     prev = j;
     ++cnt;
    }
   }
  }
  for(int i=0;i<N;++i){
   for(int j=st[i].first;j<st[i].second;++j){
    if(mark[j]){
     add_edge(i, idx[j], node[idx[j]].second - node[idx[j]].first);
     //printf("%d, [%d,%d], %d\n", j, node[idx[j]].first, node[idx[j]].second, node[idx[j]].second - node[idx[j]].first);
    }
   }
  }
  /*
  for(int i=0;i<=adj.size();++i){
   if(adj[i].empty()) continue;
   printf("%d:", i);
   for(int j=0;j<adj[i].size();++j){
    printf(" %d", adj[i][j].first);
   }
   printf("\n");
  }
  */
  if(edmond_karps()){
   printf("Case %d: Yes\n", tc++);
   int tracker[50050];
   memset(tracker, 0, sizeof tracker);
   for(int i=0;i<N;++i){
    vector<pair<int,int> > itv;
    for(int j=0;j<adj[i].size();++j){
     if(adj[i][j].first == T || adj[i][j].first == S) continue;
     int v = adj[i][j].first;
     int m = adj[i][j].second.first;
     //printf("%d --> %d [%d,%d]\n",i, edges[m].second, node[v].first, node[v].second);
     if(edges[m].first > 0 && edges[m].second > 0) {
      int start = node[v].first + tracker[v];
      int end = node[v].first + tracker[v] + edges[m].second;
      if(end > node[v].second){
       int _end = end - (node[v].second - node[v].first);
       tracker[v] = _end - node[v].first;
       if(!itv.empty() && itv.back().second == node[v].first){
        itv.back().second = _end;
       } else {
        itv.push_back(make_pair(node[v].first, _end));
       }
       if(_end == start){
        itv.back().second = node[v].second;
       } else {
        itv.push_back(make_pair(start, node[v].second));
       }
      } else {
       tracker[v] = end - node[v].first;
       if(tracker[v] == (node[v].second - node[v].first)) tracker[v] = 0;
       if(!itv.empty() && itv.back().second == start){
        itv.back().second = end;
       } else {
        itv.push_back(make_pair(start, end));
       }
      }
     }
    }
    printf("%d", (int) itv.size());
    for(int j=0;j<itv.size();++j){
     printf(" (%d,%d)", itv[j].first, itv[j].second);
    }
    printf("\n");
   }
  } else {
   printf("Case %d: No\n", tc++);
  }
 }
 return 0;
}