(X座標Y座標を独立に考える)ARC-044-C-ビーム

問題URL→http://arc044.contest.atcoder.jp/tasks/arc044_c

全然分からなかったので解説とkmjpさんのブログを見た。

求めるものがマンハッタン距離であり、ビームもX軸方向、Y軸方向に飛んでくるので、
X座標Y座標を独立に考えることができる。
↑これ重要

あとはDPをするのだが、このDPが良く分からなかった。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int S[2];   //S[0]:W, S[1]:H
int Q;      //ビームが飛んでくる回数
vector<int> E[2][101010];   //E[方向][時刻]
int dp[101010];

signed main()
{
    cin >> S[0] >> S[1] >> Q;
    REP(i,Q) {
        int j;  //ビームが飛んでくる時刻
        int x;  //方向(0:縦、 1:横)
        int y;  //座標
        cin >> j >> x >> y;
        E[x][j].push_back(y-1);
    }

    ll tot = 0;
    REP(j,2) {
        memset(dp, 0, sizeof(dp));

        REP(i,100100) if (E[j][i].size()) {
            sort(E[j][i].begin(), E[j][i].end());
            if (E[j][i].size() == S[j]) {
                cout << -1 << endl;
                return 0;
            }

            for (int x : E[j][i]) {
                if (x) dp[x-1] = min(dp[x-1], dp[x]+1);
                if (x<S[j]-1) dp[x+1] = min(dp[x+1], dp[x]+1);
            }
            reverse(E[j][i].begin(), E[j][i].end());
            for (int x : E[j][i]) {
                if (x) dp[x-1] = min(dp[x-1], dp[x]+1);
                if (x<S[j]-1) dp[x+1] = min(dp[x+1], dp[x]+1);
            }
            for (int r : E[j][i]) dp[r] = 1 << 30;
        }

        tot += *min_element(dp, dp + S[j]);
    }

    cout << tot << endl;
}

(木の直径の性質)AGC-005-C-Tree Restoring

問題URL→http://agc005.contest.atcoder.jp/tasks/agc005_c

木の直径の性質を使う問題。
木の直径は与えられた数列の最大値。
解説にある通り、dist(a,b)をa-b間の距離とすると、
dist(a,b)が木の直径となるとき、任意の頂点pとqについて
max(dist(p,q)) = max(dist(p,a), dist(p,b))となる。

つまり直径上にない点からの最も遠い距離はaまたはbまでの距離のマックスとなる。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N;
int a[110];
multiset<int> ms;

signed main()
{
    cin >> N;
    REP(i,N) {
        cin >> a[i];
        ms.insert(a[i]);
    }

    int K = *max_element(a, a + N);
    if (K % 2 == 0) {
        for (int i=K/2+1; i<=K; i++) if (ms.count(i) < 2) {
            cout << "Impossible" << endl;
            return 0;
        }
        for (int i=K/2+1; i<=K; i++) ms.erase(i);
        if (ms.count(K/2) == 1 && ms.size() == 1) {
            cout << "Possible" << endl;
            return 0;
        } else {
            cout << "Impossible" << endl;
            return 0;
        }
    } else {
        for (int i=(K+1)/2; i<=K; i++) if (ms.count(i) < 2) {
            cout << "Impossible" << endl;
            return 0;
        }
        for (int i=(K+1)/2+1; i<=K; i++) ms.erase(i);
        if (ms.count((K+1)/2) == 2 && ms.size() == 2) {
            cout << "Possible" << endl;
            return 0;
        } else {
            cout << "Impossible" << endl;
            return 0;
        }
    }
}

(トポロジカルソートの数え上げ・DP)ABC-041-D-徒競走

問題URL→http://abc041.contest.atcoder.jp/tasks/abc041_d

トポロジカルソートの数え上げはO(2^N)で出来るようだ。
詳しい解説は公式解説を参照。

漸化式は最も右に置かれる要素によって場合わけをする。(詳しくは公式解説参照)

#include <iostream>
#include <vector>
#include <string.h>
#include <climits>
#include <algorithm>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N, M;
int x, y;
vi G[20];

int dp[1<<16];

int rec(int S)
{
    if (dp[S] > 0) return dp[S];
    if (S == 0) return 1;

    int res = 0;
    REP(i,N) {
        if (S >> i & 1) {
            bool ok = true;
            for (int v : G[i]) {
                if (S >> v & 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                res += rec(S & ~(1 << i));
            }
        }
    }

    return dp[S] = res;
}

signed main()
{
    cin >> N >> M;
    REP(i,M) {
        cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
    }

    cout << rec((1 << N) - 1) << endl;
}

(拡張UnionFind・ラムダ式)ABC-040-D-道路の老朽化対策について

問題URL→http://abc040.contest.atcoder.jp/tasks/abc040_d

クエリを年代順にソートしてUnionFindする問題。
ただし普通のUnionFindではだめで、各集合のサイズも取得できるようにしないといけない。
今回はそれを実装した。
またUnionFindを汎用的に使えるようにclass化もしたので良いライブラリが出来たと思う。

ラムダ式便利。

#include <iostream>
#include <vector>
#include <string.h>
#include <climits>
#include <algorithm>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//UnionFind!!!
class UnionFind
{
private:
    vector<int> par;
    vector<int> myRank;
    vector<int> cnt;

public:
    //n要素で初期化
    UnionFind(int n)
    {
        par.resize(n);
        myRank.resize(n);
        cnt.resize(n);
        REP(i,n) {
            par[i] = i;
            myRank[i] = 0;
            cnt[i] = 1;
        }
    }

    //木の根を求める
    int find(int x)
    {
        if (par[x] == x) return x;
        else return par[x] = find(par[x]);
    }

    //xとyの属する集合を併合
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y) return;

        if (myRank[x] < myRank[y]) {
            par[x] = y;
            cnt[y] += cnt[x];
        } else {
            par[y] = x;
            cnt[x] += cnt[y];
            if (myRank[x] == myRank[y]) myRank[x]++;
        }
    }

    //xとyが同じ集合に属するか否か
    bool same(int x, int y)
    {
        return find(x) == find(y);
    }

    //xが含まれる集合の要素数
    int count(int x)
    {
        return cnt[find(x)];
    }
};

int N, M;
int a[202020], b[202020], y[202020];
int Q;
int v[101010], w[101010];

struct Query
{
    int year;
    int qType;
    int idx;
    int a, b;
    int v;
};

Query qs[303030];

signed main()
{
    cin >> N >> M;
    REP(i,M) {
        cin >> qs[i].a >> qs[i].b >> qs[i].year;
        qs[i].a--; qs[i].b--;
        qs[i].qType = 1;
    }
    cin >> Q;
    REP(i,Q) {
        cin >> qs[M+i].v >> qs[M+i].year;
        qs[M+i].v--;
        qs[M+i].qType = 2;
        qs[M+i].idx = i;
    }

    sort(qs, qs + M + Q, [](Query a, Query b){
        if (a.year == b.year) {
            return a.qType > b.qType;
        } else {
            return a.year > b.year;
        }
    });

    /*
    REP(i,M+Q) {
        cout << qs[i].year << " : " << qs[i].qType << endl;
    }
    */

    UnionFind uf(101010);

    vector<int> ans(Q);

    REP(i,M+Q) {
        if (qs[i].qType == 1) {
            uf.unite(qs[i].a, qs[i].b);
        } else {
            ans[qs[i].idx] = uf.count(qs[i].v);
        }
    }

    REP(i,Q) {
        cout << ans[i] << endl;
    }
}

(セグメント木・ラムダ式)ABC-038-D-プレゼント

問題URL→http://abc038.contest.atcoder.jp/tasks/abc038_d

まず二次元平面に点を打つ。
あとは左から見ていって点が見つかったときに、その高さ未満の範囲から最も入れ子の数が大きい値をセグメント木を使って高速に求める。

初めてラムダ式を使った。これ超便利。

//*
#include <bits/stdc++.h>
//*/
/*
#include <iostream>
#include <vector>
#include <string.h>
//*/
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

struct SegmentTree
{
private:
    int n;
    vector<int> node;

public:
    //元配列v(vector)をセグメント木で表現する
    SegmentTree(vector<int> v)
    {
        //最下段のノード数は元配列のサイズ以上になる最小の2冪→これをnとおく
        //セグメント木全体で必要なノード数は2n-1である
        int sz = v.size();
        n = 1;
        while (n < sz) n *= 2;
        node.resize(2 * n - 1, INF);

        //最下段に値を入れたあとに、下の段から埋めていく
        //値を埋めるときは自分の2つの子を見ればいい
        REP(i,sz) node[i+(n-1)] = v[i];
        for (int i=n-2; i>=0; i--) {
            //★セグ木の処理を書き換えるときはここを書き換える
            node[i] = min(node[2*i+1], node[2*i+2]);
        }
    }

    void update(int x, int val)
    {
        //最下段のノードにアクセスする
        x += n - 1;

        //最下段のノードを更新したら、あとは親に登って更新していく
        node[x] = val;
        while (x > 0) {
            //x=0でないなら親がある
            x = (x - 1) / 2;
            node[x] = min(node[2*x+1], node[2*x+2]);
        }
    }

    //要求区間[a,b)の要素の最小値を答える
    //k:=自分がいるノードのインデックス
    //対象区間は[l,r)にあたる
    int getmin(int a, int b, int k = 0, int l = 0, int r = -1)
    {
        //最初に呼び出されたときの対象区間は[0,n)
        if (r < 0) r = n;

        //要求区間と対象区間が交わらない→答えに影響を与えない値を返す
        //★セグ木の機能によって変える
        if (r <= a || b <= l) return INF;

        //要求区間が対象区間を完全に被覆→対象区間を答えの計算に使う
        if (a <= l && r <= b) return node[k];

        //要求区間が対象区間の一部を被覆→子について探索を行う
        //左の子をvl、右の子をvrとしている
        //新しい対象区間は現在の対象区間を半分にしたもの
        int vl = getmin(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = getmin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
};

int N;
P wh[101010];

signed main()
{
    cin >> N;
    REP(i,N) {
        cin >> wh[i].first >> wh[i].second;
    }

    sort(wh, wh + N, [](P x, P y){
        if (x.first == y.first) return x.second > y.second;
        else return x.first < y.first;
    });

    vector<int> a(101010, 0);
    SegmentTree st(a);

    int ans = 0;
    REP(i,N) {
        int h = wh[i].second;
        int now = -st.getmin(0, h) + 1;
        ans = max(ans, now);
        st.update(h, -now);
    }

    cout << ans << endl;
}

(木DP・数え上げ)ABC-036-D-塗り絵

問題URL→http://abc036.contest.atcoder.jp/tasks/abc036_d

木DPの典型問題。
int rec(int v, int p, int color)
とすると計算量がオーバーするのでpを消去するためにdfsを一回走らせて前の頂点に戻る辺を除く。

数え上げでコード上で*になっていたところが+でやったら答えが合わなかった。
数え上げなので掛けなければならない。ところどころ+のところもあるのでよく考えよう。

木DP何気に初めて実装したけどうまくかけたと思う。他の人のコードも見てみよう。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N;
int a, b;

vector<int> G[101010];
vector<int> GG[101010];

void dfs(int v, int p)
{
    for (int ne : G[v]) {
        if (ne == p) continue;
        GG[v].push_back(ne);
        dfs(ne, v);
    }
}

int dp[101010][2];

int rec(int v, int color)
{
    if (dp[v][color] != -1) return dp[v][color];

    int res = 1;
    for (int ne : GG[v]) {
        if (color == 0) {
            res *= rec(ne, 1);
        } else {
            res *= rec(ne, 0) + rec(ne, 1);
        }
        res %= MOD;
    }
    return dp[v][color] = res;
}

signed main()
{
    cin >> N;
    REP(i,N-1) {
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    dfs(0, -1);

    memset(dp, -1, sizeof dp);
    cout << (rec(0, 0) + rec(0, 1)) % MOD << endl;
}

(ダイクストラ・各頂点からスタート地点までの距離)ABC-035-D-トレジャーハント

問題URL→http://abc035.contest.atcoder.jp/tasks/abc035_d

ある経路で戻ってくるとき、その経路上で最も稼げる町だけに可能な限り滞在すればよいので、滞在する町は1つ。
よってこの滞在する町を全探索する。
この町に滞在できる時間はその町への最短距離を通った時にかかる時間と、帰るのにかかる時間を引いた残りの分。
したがって、ある頂点への最短距離と各頂点からスタート地点への最短距離を求めればいい。
前者は普通のダイクストラでできる。後者はグラフの各辺を逆向きにしてスタート地点からダイクストラをすればよい。

またその町を使うときの行きと帰りの最短経路のうち最も稼げる町の稼げる金額を求めるのにダイクストラに付加情報を作らせる(下コードのMaxValue)
↑実はこれはいらなかった。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N, M, T;
int A[101010];
int a, b, c;

struct edge
{
    int to, cost;
};

vector<edge> G[101010];
vector<edge> rG[101010];
int d[101010];
int rd[101010];
int maxValue[101010];
int maxValue2[101010];

void dijkstra(int s, vector<edge> GG[], int dd[], int aMaxValue[])
{
    //greater<P>を指定することでfirstが小さい順に取り出せるようにする
    priority_queue<P, vector<P>, greater<P>> que;
    fill(dd, dd + N, INF);
    dd[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (dd[v] < p.first) continue;
        for (edge e : GG[v]) {
            if (dd[e.to] > dd[v] + e.cost) {
                dd[e.to] = dd[v] + e.cost;
                que.push(P(dd[e.to], e.to));
                aMaxValue[e.to] = max(A[e.to], aMaxValue[v]);
            }
        }
    }
}

signed main()
{
    cin >> N >> M >> T;
    REP(i,N) cin >> A[i];
    REP(i,M) {
        cin >> a >> b >> c;
        a--; b--;
        G[a].push_back(edge{b, c});
        rG[b].push_back(edge{a, c});
    }

    REP(i,N) maxValue[i] = A[i];
    REP(i,N) maxValue2[i] = A[i];

    dijkstra(0, G, d, maxValue);
    dijkstra(0, rG, rd, maxValue2);

    int ans = 0;
    REP(i,N) {
        if (T - d[i] - rd[i] < 0) continue;
        //下の行はいらなかったのでmaxValueを計算する必要はなかった
        //ans = max(ans, (T - d[i] - rd[i]) * max(maxValue[i], maxValue2[i]));
        ans = max(ans, (T - d[i] - rd[i]) * A[i]);
    }
    cout << ans << endl;
}

(bitDP・配るDP)ABC-025-D-25個の整数

問題URL→http://abc025.contest.atcoder.jp/tasks/abc025_d

コンテスト本番で満点で通している人が2人だけの難問。
ポイントがいくつかある。

一つ目は1から順番に埋めていくということ。
この条件を加えることで次回以降に埋める数字は今の数字より大きいという制約が掛かる。

二つ目はその数字を置こうとしている場所の左右または上下に片方だけ既に数字が埋まっている場合はあとで矛盾が生まれる。
よってこれを避けていくと矛盾のない埋め方が得られる。

三つめはbitDPを使うということ。これまでに埋めた値は今見ている値より小さいことがすでに分かっているので、
埋めた場所だけ分かればよい。これはbitDPでできる。
2^25が約3*10^7というところからbitDPを検討すべき。

今回の問題のような小さい値から順番に埋めていくテクニックはとても汎用的。
二つ目のポイントは部分に注目して場合分けして考察するようにしよう。

配るDP

また^でどちらか片方のみtrueの場合を検出できる。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
//*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int A[25];
int fix[26];    //既に指定されている数字の場所fix[5]:5が入っている場所インデックス
int dp[1<<25];
vector<int> V;

signed main()
{
    REP(i,26) fix[i] = -1;
    REP(i,25) {
        cin >> A[i];
        if (A[i] == 0) V.push_back(i);
        else fix[A[i]] = i;
    }

    dp[0] = 1;
    //配るDP
    for (int mask=0; mask<(1<<25)-1; mask++) if (dp[mask]) {
        int b = __builtin_popcount(mask) + 1;   //次に置く数字
        if (fix[b] >= 0) {
            //次に置く数字bの場所が指定されていた場合
            int r = fix[b];
            int y = r / 5;
            int x = r % 5;
            if ((mask & (1 << r)) == 0) {
                //これから置く場合
                if (y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
                if (x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
                dp[mask ^ (1 << r)] += dp[mask];
                if (dp[mask ^ (1 << r)] >= MOD) dp[mask ^ (1 << r)] -= MOD;
            }
        } else {
            for (int r : V) {
                int y = r / 5;
                int x = r % 5;
                if ((mask & (1 << r)) == 0) {
                    if (y > 0 && y < 4 && ((mask >> (r - 5)) ^ (mask >> (r + 5))) & 1) continue;
                    if (x > 0 && x < 4 && ((mask >> (r - 1)) ^ (mask >> (r + 1))) & 1) continue;
                    dp[mask ^ (1 << r)] += dp[mask];
                    if (dp[mask ^ (1 << r)] >= MOD) dp[mask ^ (1 << r)] -= MOD;
                }
            }
        }
    }

    cout << dp[(1<<25)-1] << endl;
}

(フェルマーの小定理・逆元)ABC-024-D-動的計画法

問題URL→http://abc024.contest.atcoder.jp/tasks/abc024_d

なんか良く分からんがA,B,Cの値が余りであることを無視してA,B,Cの値からr,cを計算したら通った。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
//*/
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007

#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//(x^n)%modを求める
ll mod_pow(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

//aのmodにおける逆元を求める(フェルマーの小定理)
ll inverse(ll a, ll mod)
{
    return mod_pow(a, mod - 2, mod);
}

signed main()
{
    int A, B, C;

    cin >> A >> B >> C;
    int X = A * inverse(B, MOD) % MOD;
    int Y = A * inverse(C, MOD) % MOD;
    //cout << "X = " << X << " : Y = " << Y << endl;

    int c = (1 - X + MOD) * inverse(X + Y - 1, MOD) % MOD;
    int r = X * inverse(X + Y - 1, MOD) - 1;
    r %= MOD;
    //cout << "c = " << c << " : r = " << r << endl;

    cout << c << " " << r << endl;
}

(UnionFind・クラスカル法)POJ-3723-Conscription

問題URL→http://poj.org/problem?id=3723

蟻本の問題。
UnionFindのライブラリを整備してなかったのでちょうど良かった。
最小全域木アルゴリズムのクラスカル法もライブラリになかったので、これですぐ使えるようになった。

/*
#include <bits/stdc++.h>
//*/
//*
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
//*/
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

//#define int long long
#ifdef int
    const long long INF = LLONG_MAX / 10;
#else
    const int INF = 1010101010;
#endif

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//UnionFind!!!
const int MAX_N = 30303;
int par[MAX_N];     //親
int myRank[MAX_N];  //木の深さ

//n要素で初期化
void init(int n)
{
    REP(i,n) {
        par[i] = i;
        myRank[i] = 0;
    }
}

//木の根を求める
int find(int x)
{
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
}

//xとyの属する集合を併合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (myRank[x] < myRank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (myRank[x] == myRank[y]) myRank[x]++;
    }
}

//xとyが同じ集合に属するか否か
bool same(int x, int y)
{
    return find(x) == find(y);
}

//クラスカル法!!!
struct edge
{
    int u, v, cost;
    edge() {}
    edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}
};

bool comp(const edge& e1, const edge& e2)
{
    return e1.cost < e2.cost;
}

const int MAX_E = 50505;
edge es[MAX_E];
int V, E;

int kruskal()
{
    sort(es, es + E, comp);
    init(V);
    int res = 0;
    REP(i,E) {
        edge e = es[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int caseNum;
int N, M, R;
int x, y, d;

signed main()
{
    cin >> caseNum;
    REP(i,caseNum) {
        cin >> N >> M >> R;
        V = N + M;
        E = R;
        REP(i,R) {
            //cin >> x >> y >> d;
            scanf("%d%d%d", &x, &y, &d);
            es[i] = edge(x, N + y, -d);
        }
        cout << 10000 * (N + M) + kruskal() << endl;
    }
}