E問題がこれだけ解かれるの珍しいね。
https://codeforces.com/contest/1198/problem/E
問題
グリッド上で、いくつかの矩形部分が黒く塗られている(互いに重なるケースもある)。
このグリッド上にいくつかの矩形を置き、黒マスを全部覆いたい。
矩形内に白マスがあってもよいし、矩形同士が重なっても構わない。
矩形を1個置くコストが幅と高さの小さい方であるとき、総コストの最小値を求めよ。
解法
幅と高さの小さい方がコストになるなら、矩形を置くときは行または列を埋めるように置くのが最適である。
先に座標圧縮をしておくと、行か列をいくつか選択し、黒マスを覆う問題になる。
これはいわゆるProject Selection Problemに落とせるので、最大フローに持ち込める。
template<class V> class MaxFlow_dinic { public: struct edge { int to,reve;V cap;}; static const int MV = 1100; vector<edge> E[MV]; int itr[MV],lev[MV]; void add_edge(int x,int y,V cap,bool undir=false) { E[x].push_back((edge){y,(int)E[y].size(),cap}); E[y].push_back((edge){x,(int)E[x].size()-1,undir?cap:0}); } void bfs(int cur) { MINUS(lev); queue<int> q; lev[cur]=0; q.push(cur); while(q.size()) { int v=q.front(); q.pop(); ITR(e,E[v]) if(e->cap>0 && lev[e->to]<0) lev[e->to]=lev[v]+1, q.push(e->to); } } V dfs(int from,int to,V cf) { if(from==to) return cf; for(;itr[from]<E[from].size();itr[from]++) { edge* e=&E[from][itr[from]]; if(e->cap>0 && lev[from]<lev[e->to]) { V f=dfs(e->to,to,min(cf,e->cap)); if(f>0) { e->cap-=f; E[e->to][e->reve].cap += f; return f; } } } return 0; } V maxflow(int from, int to) { V fl=0,tf; while(1) { bfs(from); if(lev[to]<0) return fl; ZERO(itr); while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf; } } }; int N,M; int X1[51],X2[51],Y1[51],Y2[51]; vector<int> Xs,Ys; MaxFlow_dinic<ll> mf; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; if(M==0) return _P("0\n"); FOR(i,M) { cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i]; X2[i]++; Y2[i]++; Xs.push_back(X1[i]); Xs.push_back(X2[i]); Ys.push_back(Y1[i]); Ys.push_back(Y2[i]); } sort(ALL(Xs)); sort(ALL(Ys)); Xs.erase(unique(ALL(Xs)),Xs.end()); Ys.erase(unique(ALL(Ys)),Ys.end()); int NX=Xs.size()-1; int NY=Ys.size()-1; ll sum=0; FOR(i,NX) { x=Xs[i+1]-Xs[i]; sum+=x; mf.add_edge(NX+NY,i,x); } FOR(i,NY) { x=Ys[i+1]-Ys[i]; mf.add_edge(NX+i,NX+NY+1,x); } FOR(x,NX) FOR(y,NY) { int ins=0; FOR(i,M) if(Xs[x]>=X1[i]&&Xs[x]<X2[i]&&Ys[y]>=Y1[i]&&Ys[y]<Y2[i]) ins=1; if(ins) mf.add_edge(x,NX+y,1LL<<40); } cout<<mf.maxflow(NX+NY,NX+NY+1)<<endl; }
まとめ
CでハマるぐらいならD,Eやればよかったね。