Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * VJUDGE D - Aquarium
- * author: roy4801
- * (C++)
- */
- #include <bits/stdc++.h>
- using namespace std;
- #define PROB "D"
- #define TESTC ""
- #define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)
- typedef long long int LL;
- typedef unsigned long long ULL;
- typedef pair<int, int> P;
- typedef pair<LL, LL> PLL;
- #define F first
- #define S second
- #define INF 0x3f3f3f3f
- #define MP make_pair
- #define MT make_tuple
- #define PB push_back
- #define PPB pop_back
- #define PF push_front
- #define PPF pop_front
- #define L 100
- #define preS(x) ((x) - (c+1))
- #define preB(x) (preS(x)+1)
- char m[L+5][L+5];
- int w[L+5][L+5];
- int kase, C=1;
- int r, c; // i, j
- int ans;
- struct E
- {
- E(int a, int b, int wei)
- {
- this->a = a;
- this->b = b;
- this->wei = wei;
- }
- int a, b, wei;
- friend bool operator<(const E &lhs, const E &rhs)
- {
- return lhs.wei < rhs.wei;
- }
- };
- vector<E> e;
- struct disjoint
- {
- int p[100005];
- void init() {
- for(int i = 0; i <= 2*L+5; i++) p[i] = i;
- }
- int find(int x) {
- return p[x] == x ? x : (p[x] = find(p[x]));
- }
- void uni(int a, int b) {
- // printf(">> uni %d %d\n", a, b);
- p[find(a)] = find(b);
- }
- bool isSame(int a, int b) {
- return find(a) == find(b);
- }
- };
- disjoint d;
- int main()
- {
- #ifdef DBG
- freopen("./testdata/" PROB TESTC ".in", "r", stdin);
- freopen("./testdata/" PROB ".out", "w", stdout);
- #endif
- cin >> kase;
- while(kase-- && cin >> r >> c)
- {
- d.init();
- e.clear();
- ans = 0;
- //
- cin.get();
- for(int i = 0; i < r; i++)
- {
- for(int j = 0; j < c; j++)
- cin >> m[i][j];
- cin.get();
- }
- for(int i = 0; i < r; i++)
- for(int j = 0; j < c; j++)
- cin >> w[i][j];
- //
- int ii = 1; // current small number
- for(int i = 0; i < r; i++)
- {
- for(int j = 0; j < c; j++)
- {
- // printf("> cur %d %d %d %d\n", ii, ii+1, preS(ii), preB(ii));
- e.PB(E(ii, ii+1, w[i][j]));
- if(i > 0)
- {
- if(m[i-1][j] == '/')
- {
- if(m[i][j] == '/')
- e.PB(E(ii, preB(ii), 0));
- else
- e.PB(E(ii+1, preB(ii), 0));
- }
- else /* \ */
- {
- if(m[i][j] == '/')
- e.PB(E(ii, preS(ii), 0));
- else
- e.PB(E(ii+1, preS(ii), 0));
- }
- }
- ii++;
- }
- ii++;
- }
- sort(e.begin(), e.end());
- // for(auto &i : e)
- // printf("> %d %d %d\n", i.a, i.b, i.wei);
- for(auto &i : e)
- {
- if(!d.isSame(i.a, i.b))
- {
- ans += i.wei;
- d.uni(i.a, i.b);
- }
- }
- printf("Case %d: %d\n", C++, ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement