Oct. Training 4

L - Airports

https://codeforces.com/gym/100959

题意

给定n个点，第i个点为（\(x_i, y_i\)）,对于曼哈顿距离小于D的两个点可以建一条边，问最大的D使得整个图联通。

思路

这就相当于求曼哈顿最大生成树。
我们可以开八个set来维护 两组\(x_i + y_i\) \(-x_i - y_i\) \(x_i - y_i\) \(y_i - x_i\) 分别代表选和未选的点集
因为两点之间的曼哈顿距离是\(max(x_1 + y_1 - x_2 - y_2, x_1 + x_2 + y_1 - y_2, x_1 + x_2 + y_1 + y_2, x_1 - x_2 + y_1 + y_2)\)
所以'++'的set一定和'--'的set匹配，'+-'的set 一定和'-+'的set匹配。
后面每次比较四种组合方式求最大。

#include<bits/stdc++.h>
#include<array>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;

const int N = 2e5 + 5;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
#define int ll

int n;
int vis[N], date[N][5];
multiset<pair<int, int>>st1[5], st2[5];

void solve() {
    cin >> n;
    for (int i = 1, u, v; i <= n; i++) {
        cin >> u >> v;
        st1[1].insert({ u + v, i }), date[i][1] = u + v;
        st1[2].insert({ -u + v, i }), date[i][2] = -u + v;
        st1[3].insert({ u - v, i }), date[i][3] = u - v;
        st1[4].insert({ -u - v, i}), date[i][4] = -u - v;
    }

    int mx = -INF, p = 0;
    for (int i = 1; i <= 4; i++) {
        auto t = st1[i].end(); t--;
        if (mx < (*t).first) {
            mx = (*t).first;
            p = (*t).second;
        }
    }

    for (int i = 1; i <= 4; i++) {
        auto it = st1[i].find({ date[p][i], p });
        st2[i].insert(*it);
        st1[i].erase(it);  
    }

    int num = 1;
    ll anss = INF;
    while (1) {
        if (st1[1].empty()) break;
        int ans = -INF, s1 = 0, s2 = 0, id = 0;
        for (int i = 1; i <= 4; i++) {

            if (st1[i].empty() || st2[4 - i + 1].empty()) continue;

            auto t1 = st1[i].end();
            t1--;
            while (vis[(*t1).second]) st1[i].erase(t1), t1--;
            auto t2 = st2[4 - i + 1].end();

            int dis = (*t1).first + (*(--t2)).first;
            if (dis > ans) {
                ans = dis;
                id = (*t1).second;
            }
        }

        anss = min(ans, anss);
        vis[id] = 1;
        for (int i = 1; i <= 4; i++) {
            auto it = st1[i].find({ date[id][i], id });
            st2[i].insert(*it); 
            st1[i].erase(it);
        }
    }
    
    cout << anss << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    //cin >> _t;
    while (_t--) {
        solve();
    }

    return 0;
}

D - Minimum Path

https://codeforces.com/problemset/problem/1473/E

题意

n个点m条边 每条边有一个边权 \(w_i\) 一条从u到v的路径的价值是这条路径上每条边权和减去最大边权加上最小边权。
求1到剩余n-1个点的路径最小价值

思路

对于一条路径的价值最小边权会被加两次 最大边权会被置零。
那么我们可以建四个图 第一张图为原图，1图和2图建 2 * w 边， 1图和3图建0的边， 而后2图和4图建 0 边， 3图和4图建2 * w的边， 1图和4图案原边建立。
然后对原图上的点跑最短路即可。
这样保证了一定会将一个最小值边加两次最大值边不加，且最优。

#include<bits/stdc++.h>
#include<array>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;

const int N = 2e5 + 5;
const int M = 1e6 + 1;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
#define int ll
int n, m;

vector<pair<int, int>>g[N*4];
int dis[N * 4], vis[N * 4];

void dij(int s) {
    for (int i = 1; i <= n * 4; i++) dis[i] = INF, vis[i] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    dis[s] = 0;
    q.push({ dis[s], s });

    while (q.size()) {
        auto [w, x] = q.top();
        q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (auto [to, w] : g[x]) {
            if (dis[to] > dis[x] + w) {
                dis[to] = dis[x] + w;
                q.push({ dis[to], to });
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });

        g[u + n].push_back({ v + n, w });
        g[v + n].push_back({ u + n, w });

        g[u + 2 * n].push_back({ v + 2 * n, w });
        g[v + 2 * n].push_back({ u + 2 * n, w });

        g[u + 3 * n].push_back({ v + 3 * n, w });
        g[v + 3 * n].push_back({ u + 3 * n, w });

        g[u].push_back({ v + n, w * 2 });
        g[v].push_back({ u + n, w * 2 });

        g[u].push_back({ v + 2 * n, 0 });
        g[v].push_back({ u + 2 * n, 0 });

        g[u + n].push_back({ v + 3 * n, 0 });
        g[v + n].push_back({ u + n * 3, 0 });

        g[u + n * 2].push_back({ v + 3 * n, w * 2 });
        g[v + 2 * n].push_back({ u + n * 3, w * 2 });

        g[u].push_back({ v + 3 * n, w});
        g[v].push_back({ u + n * 3, w});
    }

    dij(1);

    for (int i = 2; i <= n; i++)
        cout << dis[i + 3 * n] << " \n"[i == n];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    //cin >> _t;
    while (_t--) {
        solve();
    }

    return 0;
}