AOJ 2429 marukaite

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429

{n \times n} のグリッドがある。各マスは初期状態でoが書かれているか書かれていないかのどちらか一方である。各マスに対して、空白のときに書くコストと既にあるoを消すコストが与えられる。同じ行/列にoがちょうど1個になるように書いたり消したりするときの最小値をもとめよ。

解法

(2時間くらい考えて解けなかったので他人の答えを見ました。)

最小費用量で解ける。

{2n+2} 個の頂点 {S,T,s_1, \cdots , s_n, t_1, \cdots , t_n} を作り、マス {(i,j)} に書くことに正のコスト、消すことに負のコストを持たせて容量1の辺 {s_i \rightarrow t_i} を張る。さらに容量1コスト0の辺 {S \rightarrow s_i} {t_i \rightarrow T} を張り、{S} から {T} へ容量 {n} のフローを流したときの最小費用を求める。

初期状態のコストをその状態から何もない状態にするのに必要なコストとし、そこに上で求めた最小費用を足すと答えになる。

int n;
Weight W[128][128], E[128][128];
char f[128][128];
 
void solve(){
    Weight C=0;
    rep(i,n)rep(j,n){
        if(f[i][j]=='o')C+=E[i][j];
    }
 
    Graph g(n*2+2);
    int s=n*2, t=n*2+1;
    rep(i,n){
        add_edge(g,s,i,1,0);
        add_edge(g,i+n,t,1,0);
    }
    rep(i,n)rep(j,n){
        if(f[i][j]=='o'){
            add_edge(g,i,j+n,1,-E[i][j]);
        }else{
            add_edge(g,i,j+n,1,W[i][j]);
        }
    }
 
    printf("%d\n",C+primal_dual(g,s,t,n));
    static int ans[10000][3];
    int cnt=0;
 
    rep(i,g.size()){
        rep(j,g[i].size()){
            auto & e=g[i][j];
            if(e.is_rev || e.cost==0) continue;
            if(f[e.src][e.dst-n]=='o' && e.cap!=0){
                cnt++;
                ans[cnt][0]=e.src+1;
                ans[cnt][1]=e.dst-n+1;
                ans[cnt][2]=0;
            }else if(f[e.src][e.dst-n]=='.' && e.cap==0){
                cnt++;
                ans[cnt][0]=e.src+1;
                ans[cnt][1]=e.dst-n+1;
                ans[cnt][2]=1;
            }
        }
    }
    printf("%d\n",cnt);
    rep(i,cnt){
        printf("%d %d %s\n",ans[i][0],ans[i][1],ans[i][2]==0 ? "erase" : "write");
    }
}
 
int main(){
    scanf("%d",&n);
    rep(i,n)rep(j,n){
        scanf("%d",&W[i][j]);
    }
    rep(i,n)rep(j,n){
        scanf("%d",&E[i][j]);
    }
    rep(i,n){
        scanf("%s",f[i]);
    }
    solve();
}