SRM-429 500pt: IngredientProportions

keyword

有理数　グラフ　C++

問題概要

A:B = n:mという情報がN(<9)個与えられる。既約な連比を求める問題。

解法

A:B = n:mならばA->Bの重みがm/nであるようなグラフを作る。グラフは木になるので適当な点からスタートして掛け合わせながら進んでいけば良い。わざわざ有理数クラスをつくらなくても、m/nをかけるとき、nで割りきれなければ全体の要素をn倍するようにすれば良い。

感想

この位の問題ならもっと速くとけるようにならねば。

int graph[10][10];
int visited[10];
int64 ans[10];
int N;

vector <int> getMasses(vector <string> proportions) {
    int i, j;
    N=SZ(proportions)+1;
    int64 multi = 1;
    REP(i,N)REP(j,N) graph[i][j] = 0;
    REP(i,N) visited[i] = false;
    REP(i,N-1){
        int x, y, xx, yy;
        sscanf(proportions[i].c_str(), "#%d and #%d as %d:%d", &x, &y, &xx, &yy);
        graph[x][y] = xx;
        graph[y][x] = yy;
    }
    ans[0] = multi;
    dfs(0);
    int64 d = ans[0];
    FOR(i,1,N) d = __gcd(d,ans[i]);
    REP(i,N) ans[i] /= d;
    vector<int> ret;
    REP(i,N) ret.push_back(ans[i]);
    return ret;
}

void dfs(int v){
    if(visited[v]) return ;
    visited[v] = true;
    int i,j;
    REP(i,N)if(graph[v][i]){
        if(ans[v] % graph[v][i]){
            REP(j,N) ans[j] *= graph[v][i];
        }
        ans[i] = ans[v] / graph[v][i] * graph[i][v];
        dfs(i);
    }
    return ;
}