oj.uz

답안 #43268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43268 2018-03-12T08:40:12 Z ngkan146 시간이 돈 (balkan11_timeismoney) C++11
100 / 100
 656 ms 1004 KB 
#include <bits/stdc++.h>
using namespace std;
struct edge{
    int u,v,w1,w2;
    edge(int u=0,int v=0,int w1=0,int w2=0): u(u), v(v), w1(w1), w2(w2) {}
};
int dsup[205], dsusize[205];
int dsu_p(int x){
    return dsup[x] == x ? x : dsup[x] = dsu_p(dsup[x]);
}
void dsu_union(int x,int y){
    x = dsu_p(x);
    y = dsu_p(y);
    if (dsusize[x] > dsusize[y])    swap(x, y);
    dsusize[y] += dsusize[x];
    dsup[x] = y;
}
int n, m;
vector <edge> lst;
typedef pair<int,int> mst;
mst ans;
int answer;
vector <mst> lstt;
mst find_mst(int v1,int v2){
    sort(lst.begin(), lst.end(), [&](edge x,edge y){
         return x.w1 * v1 + x.w2 * v2 != y.w1 * v1 + y.w2 * v2 ? x.w1 * v1 + x.w2 * v2 < y.w1 * v1 + y.w2 * v2 : x.w1 < y.w1;
    });
    for(int i=1;i<=n;i++)
        dsup[i] = i,
        dsusize[i] = 1;
    mst res;
    vector <mst> mjk;
    for(auto e: lst){
        if (dsu_p(e.u) != dsu_p(e.v))
            dsu_union(e.u, e.v),
            mjk.push_back({e.u, e.v}),
            res.first += e.w1,
            res.second += e.w2;
    }
    if (answer > res.first * res.second){
        answer = res.first * res.second;
        ans = move(res);
        lstt = move(mjk);
    }
    return res;
}
void solve(mst a,mst b){
    mst tmp = find_mst(a.second - b.second, - a.first + b.first);
    if (a.first != tmp.first && a.second != tmp.second &&
        b.first != tmp.first && b.second != tmp.second)
            solve(a, tmp), solve(tmp, b);
}
int main(){
    answer = (int) 2e9;
    iostream::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,w1,w2;
        cin >> u >> v >> w1 >> w2;
        u ++; v ++;
        lst.push_back(edge(u, v, w1, w2));
    }
    solve(find_mst(1,0), find_mst(0, 1));
    cout << ans.first << ' ' << ans.second << endl;
    for(auto v: lstt)
        cout << v.first-1 << ' ' << v.second-1 << endl;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 660 KB Output is correct
7 Correct 3 ms 660 KB Output is correct
8 Correct 8 ms 956 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 2 ms 956 KB Output is correct
11 Correct 2 ms 956 KB Output is correct
12 Correct 2 ms 956 KB Output is correct
13 Correct 2 ms 956 KB Output is correct
14 Correct 9 ms 956 KB Output is correct
15 Correct 5 ms 956 KB Output is correct
16 Correct 72 ms 956 KB Output is correct
17 Correct 75 ms 956 KB Output is correct
18 Correct 79 ms 956 KB Output is correct
19 Correct 656 ms 1004 KB Output is correct
20 Correct 627 ms 1004 KB Output is correct