Submission #110296

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)

using namespace std;

const int MAX_H = 110;
const int MAX_W = 110;
const int MAX_N = MAX_H + MAX_W;

int h, w, n;
int u[MAX_H][MAX_W];
int f[MAX_W];
int s[MAX_H];

vector<int> g[MAX_N];
bool used[MAX_N];
int match[MAX_N];

bool check(){
  vector< vector<int> > t(h, vector<int>(w));
  REP(i, h) REP(j, w){
    if(u[i][j]){
      t[i][j] = min(s[i], f[j]);
    }else{
      t[i][j] = 0;
    }
  }
  REP(i, w){
    int tf = 0;
    REP(j, h){
      tf = max(tf, t[j][i]);
    }
    if(tf != f[i]) return false;
  }
  REP(i, h){
    int ts = 0;
    REP(j, w){
      ts = max(ts, t[i][j]);
    }
    if(ts != s[i]) return false;
  }
  return true;
}

bool dfs(int v){
  used[v] = true;
  REP(i, (int)g[v].size()){
    int u = g[v][i], w = match[u];
    if(w == -1 || (!used[w] && dfs(w))){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int bipartite_matching(){
  int r = 0;
  memset(match, -1, sizeof(match));
  REP(i, n){
    if(match[i] == -1){
      memset(used, false, sizeof(used));
      if(dfs(i)) r++;
    }
  }
  return r;
}


int solve(){
  if(!check()) return -1;
  REP(i, h) REP(j, w){
    if(u[i][j] && s[i] == f[j]){
      g[i].push_back(h + j);
      g[h + j].push_back(i);
    }
  }
  bipartite_matching();
  int r = 0, ct = 0;
  REP(i, h) if(s[i]){
    r += s[i];
    ct++;
  }
  REP(i, w) if(f[i] && match[h + i] == -1){
    r += f[i];
    ct++;
  }
  REP(i, h) REP(j, w){
    r += u[i][j];
  }
  return r - ct;
}

int main(){
  cin >> h >> w;
  n = h + w;
  REP(i, n) g[i].clear();
  REP(i, h) REP(j, w) cin >> u[i][j];
  REP(i, w) cin >> f[i];
  REP(i, h) cin >> s[i];
  cout << solve() << endl;
}

Submission Info

Judge Result