2018-Sp28-lyk/I

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include<bits/stdc++.h>
#define maxn 1200
using namespace std;
typedef unsigned int uint;
typedef pair<uint, uint> puu;
vector<puu> G[maxn];
vector<uint> A[maxn];
puu f[maxn];
uint d[maxn] = {0, 1}, A_size;

void dfs(uint u){
    for(puu p: G[u]){
        uint v = p.first, w = p.second;
        if(d[v] == 0){
            d[v] = d[u] + 1;
            f[v] = puu(u, w);
            dfs(v);
        }
        else if(d[v] > d[u]){
            A[A_size].push_back(w);
            uint p = v;
            while(p != u){
                A[A_size].push_back(f[p].second);
                p = f[p].first;
            }
            A_size += 1;
        }
    }
}
void merge(vector<uint> &A, const vector<uint> &B, uint k){
    priority_queue<puu> q;
    for(uint x : A) q.push(puu(x + B[0], 0));
    A.clear();
    for(int i = 0; i < (int)k; i += 1){
        if(q.empty()) break;
        puu p = q.top();
        q.pop();
        A.push_back(p.first);
        if(p.second + 1 < B.size())
            q.push(puu(p.first + B[p.second + 1] - B[p.second], p.second + 1));
    }
}
void merge(int l, int r, uint k){
    if(l == r) return;
    int m = (l + r) >> 1;
    merge(l, m, k);
    merge(m + 1, r, k);
    merge(A[l], A[m + 1], k);
}
int main(){
    int n, m, t = 0;
    while(scanf("%d %d", &n, &m) == 2){
        for_each(G + 1, G + n + 1, [](vector<puu> &v)->void{v.clear();});
        fill(d + 2, d + n + 1, 0);
        for_each(A, A + m - n + 2, [](vector<uint> &v)->void{v.clear();});
        A[0].push_back(0);
        uint s = 0;
        for(int i = 0; i < m; i += 1){
            uint x, y, z;
            scanf("%u %u %u", &x, &y, &z);
            G[x].push_back(puu(y, z));
            G[y].push_back(puu(x, z));
            s += z;
        }
        A_size = 1;
        dfs(1);
        uint k;
        scanf("%u", &k);
        for_each(A + 1, A + m - n + 2, [](vector<uint> &v)->
            void{sort(v.begin(), v.end(), greater<uint>());});
        merge(0, m - n + 1, k);
        uint ans = 0;
        for(uint i = 0; i < k && i < A[0].size(); i += 1)
            ans += (i + 1) * (s - A[0][i]);
        printf("Case #%d: %u\n", t += 1, ans);
    }
}
}}}

#include<bits/stdc++.h>
#define maxn 1200
using namespace std;
typedef unsigned int uint;
typedef pair<uint, uint> puu;
vector<puu> G[maxn];
vector<uint> A[maxn];
puu f[maxn];
uint d[maxn] = {0, 1}, A_size;
void dfs(uint u){
    for(puu p: G[u]){
        uint v = p.first, w = p.second;
        if(d[v] == 0){
            d[v] = d[u] + 1;
            f[v] = puu(u, w);
            dfs(v);
        }
        else if(d[v] > d[u]){
            A[A_size].push_back(w);
            uint p = v;
            while(p != u){
                A[A_size].push_back(f[p].second);
                p = f[p].first;
            }
            A_size += 1;
        }
    }
}
void merge(vector<uint> &A, const vector<uint> &B, uint k){
    priority_queue<puu> q;
    for(uint x : A) q.push(puu(x + B[0], 0));
    A.clear();
    for(int i = 0; i < (int)k; i += 1){
        if(q.empty()) break;
        puu p = q.top();
        q.pop();
        A.push_back(p.first);
        if(p.second + 1 < B.size())
            q.push(puu(p.first + B[p.second + 1] - B[p.second], p.second + 1));
    }
}
void merge(int l, int r, uint k){
    if(l == r) return;
    int m = (l + r) >> 1;
    merge(l, m, k);
    merge(m + 1, r, k);
    merge(A[l], A[m + 1], k);
}
int main(){
    int n, m, t = 0;
    while(scanf("%d %d", &n, &m) == 2){
        for_each(G + 1, G + n + 1, [](vector<puu> &v)->void{v.clear();});
        fill(d + 2, d + n + 1, 0);
        for_each(A, A + m - n + 2, [](vector<uint> &v)->void{v.clear();});
        A[0].push_back(0);
        uint s = 0;
        for(int i = 0; i < m; i += 1){
            uint x, y, z;
            scanf("%u %u %u", &x, &y, &z);
            G[x].push_back(puu(y, z));
            G[y].push_back(puu(x, z));
            s += z;
        }
        A_size = 1;
        dfs(1);
        uint k;
        scanf("%u", &k);
        for_each(A + 1, A + m - n + 2, [](vector<uint> &v)->
            void{sort(v.begin(), v.end(), greater<uint>());});
        merge(0, m - n + 1, k);
        uint ans = 0;
        for(uint i = 0; i < k && i < A[0].size(); i += 1)
            ans += (i + 1) * (s - A[0][i]);
        printf("Case #%d: %u\n", t += 1, ans);
    }
}