题目描述

懒得弄

样例

懒得弄

这题好离谱，实现好难，写了一晚上调了半个晚上才调好，建议直接跳过吧 –.–

算法1

C++ 代码

#include<bits/stdc++.h>
#include<unordered_map>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
struct pr{
    ll a, b;
    ll w;
};
struct node{
    ll x, w;
};
vector<pr> st1,st2,ss;
ll mp[105][105];
unordered_map<string, int> p;
vector<ll> ku[105];
ll tot = 1;
ll cnt[105];
int n;
ll o[105][105];
void dfs(ll x,ll k){
    cnt[x] = k;
    ku[k].push_back(x);
    o[k][x] = 1;
    for (int i = 1; i <=tot; i++){
        if (mp[x][i]!=inf&&!cnt[i]){
            dfs(i, k);
        }
    }
}
ll k = 0;
bool cmp(pr a, pr b){
    return a.w < b.w;
}
ll pre[105];
ll find(ll x){
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
ll sum[105];
ll mp1[105][105];
void kr(ll x){
    for (int i = 1; i <= 104; i++)pre[i] = i;
    ss.clear();
    for (auto to : st1){
        if (cnt[to.a] == cnt[to.b] == x){
            ss.push_back(to);
        }
    }
    sort(ss.begin(),ss.end(),cmp);
    ll dx, dy;
    for (auto to : ss){
        dx = find(to.a);
        dy = find(to.b);
        if (dx != dy){

            sum[x] += to.w;
            pre[dx] = dy;
            mp1[to.a][to.b] = 1;
            mp1[to.b][to.a] = 1;    
        }
    }
}
ll link[105];
bool vis[105];ll t = 0,tt,ttt;bool f1 = 1;
struct nn{
    ll w, u,v;
};
vector<nn >sss;
ll g[105],gg[105],ggg[105];
void dfs1(ll x,ll a){

    if (x == 1){
        for (auto to : sss){
            if (t < to.w){
                t = to.w;
                g[a] = t;
                gg[a] = to.u;
                ggg[a] = to.v;
            }
        }
        return;
    }
    vis[x] = 1;
    for (int i = 1; i <= tot; i++){
        if (!vis[i] && mp1[x][i]){
            if (i != 1)sss.push_back({ mp[x][i], x, i });
            dfs1(i,a);
            if(sss.size())sss.pop_back();
        }
    }
}
vector<ll > kk;
ll zz[105];

int main(){

    cin >> n;
    string s1, s2;
    ll w; ll s;
    p["Park"] = 1;
    for (int i = 1; i <= 104; i++){
        for (int j = 1; j <= 104; j++){
            mp[i][j] = inf;
        }
    }
    for (int i = 1; i <= n; i++){
        cin >> s1 >> s2 >> w;
        if (!p[s1]){
            p[s1] = ++tot;
        }
        if (!p[s2]){
            p[s2] = ++tot;
        }
        st1.push_back({ p[s1], p[s2], w });
        if (p[s1] == 1||p[s2]==1){
            st2.push_back({ p[s1], p[s2], w });
        }
        else{
            mp[p[s1]][p[s2]] = w;
            mp[p[s2]][p[s1]] = w;
        }
    }
    cin >> s;
    for (int i = 2; i <=tot ; i++){
        if (!cnt[i]){
            ++k;
            dfs(i,k);
        }
    }
    for (int i = 1; i <= k; i++){
        kr(i);
    }
    for (int i = 1; i <= 104; i++){
            link[i] = inf;
    }
    for (auto to : st2){
        mp[to.a][to.b] = to.w;
        mp[to.b][to.a] = to.w;
    }
    for (int i = 1; i <= k; i++){
        for (auto to:ku[i]){
            if (link[i] > mp[1][to]){
                link[i] = mp[1][to];
                zz[i] = to;
            }

        }
    }
    for (int i = 1; i <= k; i++){
        if (zz[i])mp1[1][zz[i]] = 1,mp1[zz[i]][1]=1;
    }
    ll ans = 0;
    for (int i = 1; i <= k; i++){
        ans += link[i] + sum[i];
    }
    if (k == s){
        cout << "Total miles driven: "<<ans << endl;
    }
    else{
        while (s>k){
            s--;
            ll now = 0;
            memset(g, 0, sizeof g); ll d;
            for (int i = 2; i <= tot; i++){
                if (!mp1[1][i]){
                    memset(vis, 0, sizeof vis);
                    f1 = 0; sss.clear(); t = 0;
                    dfs1(i, i);
                    if (g[i] && now < g[i] - mp[1][i]){
                        now = g[i] - mp[1][i];
                        d = i;
                    }
                }           
            }
            if (now <= 0)break;
            ans -= now;
            mp1[1][d] = mp1[d][1] = 1;
            mp1[gg[d]][ggg[d]] =mp1[ggg[d]][gg[d]]= 0;
        }
        cout << "Total miles driven: "<<ans << endl;
    }
}