SRM531 Div2 Hard(950) KingdomReorganization

KingdomReorganization

最小全域木。すでに存在する辺eを削除するのにコストCが掛かるというのは、辺の重みを-Cと考えて、あらかじめ重みの総和にCを加えておく。Prim法は重みが負でも動く。

#include <string>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int cost( char c ) { return c<='Z' ? c-'A' : c-'a'+26; }

struct Edge
{
    int f,t,w;  //  始点、終点、重み
    Edge(int f_,int t_,int w_):f(f_),t(t_),w(w_){}
    bool operator<(const Edge&e)const{return w<e.w;}
};

//  最小全域木（Prim法）
int minSpanning( vector<vector<int> > E )
{
    int n = (int)E.size();
    int w = 0;

    vector<bool> V(n);
    priority_queue<Edge> Q;
    Q.push( Edge(0,0,0) );

    while ( !Q.empty() )
    {
        Edge e = Q.top(); Q.pop();
        if ( V[e.t] )
            continue;
        V[e.t] = true;
        w -= e.w;
        for ( int i=0; i<n; i++ )
        if ( !V[i] )
            Q.push( Edge(e.t,i,-E[e.t][i]) );
    }

    return w;
}

class KingdomReorganization{public:
int getCost( vector <string> kingdom, vector <string> build, vector <string> destroy )
{
    int N = (int)kingdom.size();
    vector<vector<int> > E( N, vector<int>(N) );
    
    for ( int i=0; i<N; i++ )
    for ( int j=0; j<N; j++ )
        if ( kingdom[i][j]=='0' )
            E[i][j] = cost(build[i][j]);
        else
            E[i][j] = -cost(destroy[i][j]);

    int t = 0;
    for ( int i=0; i<N; i++ )
    for ( int j=i+1; j<N; j++ )
        if ( kingdom[i][j]=='1' )
            t += cost(destroy[i][j]);

    return t + minSpanning(E);

}};