Submission #27806041

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;


int main(){
  int h,w,n;
  cin >> h >> w >> n;
  vector<int>hmin(h,1e9),wmin(w,1e9);
  vector<tuple<int,int,int>>p;
  for(int i=0;i<n;i++){
    int a,b,c;
    cin >> a >> b >> c;
    a--,b--;
    hmin[a]=min(hmin[a],c);
    wmin[b]=min(wmin[b],c);
    p.push_back(make_tuple(a,b,c));
  }
  
  mcf_graph<int,long long>g(h+w+2);
  //0:source, 1-h:row, h+1-h+w:col, h+w+1:sink
  for(int i=1;i<=h;i++)g.add_edge(0,i,1,0);
  for(int i=1;i<=w;i++)g.add_edge(h+i,h+w+1,1,0);
  const long long INF=2e9;
  for(int i=0;i<n;i++){
    auto[a,b,c]=p[i];
    if(c<hmin[a]+wmin[b]){
      g.add_edge(a+1,b+h+1,1,c-hmin[a]-wmin[b]+INF);
    }
  }
  
  long long ans_base=0;
  for(int i=0;i<h;i++)ans_base+=hmin[i];
  for(int i=0;i<w;i++)ans_base+=wmin[i];
  long long ans=ans_base;
  for(auto[cap,cost]:g.slope(0,h+w+1))ans=min(ans,ans_base+cost-INF*cap);
  cout << ans << endl;
}

Submission Info

Judge Result