SPOJ AMR 12 A The Black Riders(二分+二分整合)

n人、m個の穴があります.穴ごとに一人を収容することができ、一人一人が穴ごとに時間がかかります.一人一人が穴に着いた後、Cの時間をかけて穴を掘ることができ、この穴の容量は2になります.少なくともK個人が穴に入る最短時間を求めます.
やはり極値を求める問題を判定問題に変換する.二分列挙時間、timeの時間内に少なくともK人を穴に入れることができますか?穴に入る人数を求めるのはもちろん2点マッチングでします.g[i][j]は、i番目の人からj番目の穴までの時間である.g[i][j]<=timeの場合、iからjにエッジが接続される.穴を掘る場合は?g[i][j]+C<=timeであれば、iからjとj+mにそれぞれエッジを接続することで、時間が十分な場合に穴の容量を変えることが保証される.

#include<algorithm>
#include<iostream>
#include<cstring>
#include<fstream>
#include<sstream>
#include<cstdlib>
#include<vector>
#include<string>
#include<cstdio>
#include<bitset>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define FF(i, a, b) for(int i=a; i<b; i++)
#define FD(i, a, b) for(int i=a; i>=b; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define CLR(a, b) memset(a, b, sizeof(a))
#define debug puts("**debug**")
#define LL long long
#define PB push_back
#define MP make_pair
using namespace std;

const int maxn = 222;
int n, m, K, C, g[maxn][maxn];

struct BPM
{
  int n, m;               //       
  int G[maxn][maxn];      //    
  int left[maxn];         // left[i]    i        ，-1     
  bool T[maxn];           // T[i]    i       

  void init(int n, int m) {
    this->n = n;
    this->m = m;
    memset(G, 0, sizeof(G));
  }

  inline void add(int u, int v)
  {
      G[u][v] = 1;
  }

  bool match(int u){
    for(int v = 0; v < m; v++) if(G[u][v] && !T[v]) {
      T[v] = true;
      if (left[v] == -1 || match(left[v])){
        left[v] = u;
        return true;
      }
    }
    return false;
  }
  //      
  int solve() {
    memset(left, -1, sizeof(left));
    int ans = 0;
    for(int u = 0; u < n; u++) { //      u    
      memset(T, 0, sizeof(T));
      if(match(u)) ans++;
    }
    return ans;
  }
}solver;

bool ok(int time)
{
    solver.init(n, m*2);
    REP(i, n) REP(j, m)
    {
        if(g[i][j] <= time) solver.add(i, j);
        if(g[i][j] + C <= time) solver.add(i, j+m);
    }
    return solver.solve() >= K;
}

int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        int L = 0, R = -1, M, ans;
        scanf("%d%d%d%d", &n, &m, &K, &C);
        REP(i, n) REP(j, m)
        {
            scanf("%d", &g[i][j]);
            R = max(R, g[i][j]);
        }
        while(L <= R)
        {
            M = (L + R) >> 1;
            if(ok(M)) ans = M, R = M - 1;
            else L = M + 1;
        }
        printf("%d
", ans);
    }
    return 0;
}