Submission #13286

#	Time	Username	Problem	Language	Result	Execution time	Memory
13286		heesub	비용 (KOI11_cost)	C++98	7.20 / 24	1500 ms	4304 KiB

cost

#include <stdio.h>
#include <vector>
#include <algorithm>
 
#define MAX_V   100000
#define MAX_E   100000
 
class edge {
public:
    edge(int from, int to, int weight)
    {
        _from = from;
        _to = to;
        _weight = weight;
    }
 
    int _from;
    int _to;
    int _weight;
};
 
bool operator<(const edge& x, const edge& y)
{
    return x._weight > y._weight;
}
 
int v, e;
std::vector<edge> edges;
 
int uf[MAX_V + 1];
int rank[MAX_V + 1];
 
static int _find(int v1)
{
    int tmp = v1;
 
    while (v1 != uf[v1])
        v1 = uf[v1];
 
    uf[tmp] = v1;
 
    return v1;
}
 
static void _union(int v1, int v2)
{
    int pv1 = _find(v1);
    int pv2 = _find(v2);
 
    if (pv1 == pv2) return;
 
    if (rank[pv1] > rank[pv2])
        uf[pv2] = pv1;
    else {
        uf[pv1] = pv2;
        if (rank[pv1] == rank[pv2])
            rank[pv2]++;
    }
}
 
static int cost(int v1, int v2)
{
    int i;
    int sum = 0;
 
    if (v1 >= v2)
        return 0;
 
    for (i = 1; i <= v; i++) {
        uf[i] = i;
        rank[i] = 1;
    }
 
    std::vector<edge>::iterator iter;
    for (iter = edges.begin(); iter != edges.end(); iter++) {
        _union(iter->_from, iter->_to);
        if (_find(v1) == _find(v2))
            break;
    }   
 
    for (;iter != edges.end(); iter++)
        sum += iter->_weight;
 
    return sum;
}
 
int main(void)
{
    unsigned long long sum = 0;
 
    scanf("%d", &v);
    scanf("%d", &e);
     
    for (int i = 0; i < e; i++) {
        int from, to, weight;
        scanf("%d %d %d", &from, &to, &weight);
        edges.push_back(edge(from, to, weight));
    }
 
    std::sort(edges.begin(), edges.end());
 
    for (int i = 1; i <= v; i++)
        for (int j = 1; j <= v; j++)
            sum += cost(i, j);
 
    if (sum > 1000000000)
        printf("%llu\n", sum % 1000000000);
    else
        printf("%llu\n", sum);
 
    return 0;
}

• Subtask 1: 4.8 / 4.8
• Subtask 2: 2.4 / 7.2
• Subtask 3: 0 / 12