14142: 【原4142】抗震救灾

题目

题目描述

author: 侯不会 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4142

Description

近日，由于一场世纪大地震，某国通讯设施全面瘫痪。在灾后重建中，抢修通讯设备成为首要任务。现在，你已经了解该国的基本状况，该国首脑希望你设计一种方案，使得所用的救灾资金尽可能少。 已知该国地形可以简化成包含\(n\)个点的一张无向图，每个点代表一座城市。由于地震的破坏，该国的城市之间已经只剩下\(m\)条仍具备通行条件的双向道路。当然，目前该国的所有城市是联通的。现在，该国希望在一些仍能通行的道路下铺设通信电缆，使得任意两个城市之间能够通过通信电缆直接或间接地传递灾情。不过，若某条道路被破坏后，该国的所有城市不再全部联通，则这条道路被认为是危险道路，因为一旦这条道路被次生灾害破坏，那么相应的通信电缆也会被破坏，而且没有其他可供选择的途径来恢复通信。在这样的危险道路上，你只能选择用无线通信设备代替。（注意：在非危险道路上，即使无线设施的费用低于通信电缆的费用，你也只能铺设通信电缆，因为这种方式可靠性更高。）

Input Format

第一行包含两个正整数\(n\)和\(m\)。 接下来共\(m\)行，第\(i\)行包含四个整数\(s[i]\)，\(t[i]\)，\(a[i]\)和\(b[i]\)，分别表示第\(i\)条道路连接的两座城市，以及在该条道路上铺设电缆和架设无线设备的费用。

Output Format

第一行包含一个整数，表示最小代价。

Sample Input

8 11
2 6 0 9
2 7 8 6
7 3 4 0
4 8 3 0
4 5 0 0
4 1 1 10
2 4 0 10
7 6 0 10
2 3 2 1
1 4 1 0
1 5 2 4

Sample Output

13

数据范围

对于\(30\%\)的数据，\(n \le 500\)，\(m \le 3000\)。 对于额外\(40\%\)的数据，数据保证不存在危险道路。 对于\(100\%\)的数据，\(n \le 10^{5}\)，\(m \le 5 \times 10^{5}\)。 在每一部分数据中，均包含若干较小的测试点。

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4142.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int at[100005] = {0}, nxt[1000005], w[1000005], to[1000005], cnt = 0;
int id[1000005], tot = 0;
bool is_mul[500005] = {0};
int dfn[100005] = {0}, low[100005], D = 0;
int ffa[100005], siz[100005];
unordered_map<int, int> mp[100005];
int Find(int x){
    return (ffa[x] == x ? x: (ffa[x] = Find(ffa[x])));
}
int Union(int x, int y){
    int u = Find(x), v = Find(y);
    if (u == v) return 0;
    if (siz[u] > siz[v])
        ffa[v] = u, siz[u] += siz[v];
    else    
        ffa[u] = v, siz[v] += siz[u];
    return 1;
}
inline int get(int x){
    return ((x & 1) ? x + 1: x - 1);
}
bool cmp(int i, int j){
    return w[i] < w[j];
}
void tarjan(int cur, int fa){
    dfn[cur] = low[cur] = ++D;
    for (int i = at[cur]; i; i = nxt[i]){
        int v = to[i];
        if (v == fa) continue;
        if (!dfn[v]){
            tarjan(v, cur);
            if (low[v] > dfn[cur] && !is_mul[(i + 1) >> 1]){
                id[++tot] = ((i & 1) ? (i + 1): i);
            }else {
                low[cur] = min(low[cur], low[v]);
                id[++tot] = ((i & 1) ? i: (i - 1));
            }
        }else 
            low[cur] = min(low[cur], dfn[v]), 
            id[++tot] = ((i & 1) ? i: (i - 1));
    }
}
void init(){
    n = read(), m = read();
    for (int i = 1; i <= m; ++i){
        int u = read(), v = read(), ww1 = read(), ww2 = read();
        if (u == v) continue;
        if (u > v) swap(u, v);
        if (mp[u].count(v)){
            int pos = mp[u][v];
            w[pos] = min(w[pos], ww1), w[pos + 1] = min(w[pos + 1], ww2);
            is_mul[(pos + 1) >> 1] = true;
        }else {
            mp[u][v] = cnt + 1;
            to[++cnt] = v, nxt[cnt] = at[u], w[cnt] = ww1, at[u] = cnt;
            to[++cnt] = u, nxt[cnt] = at[v], w[cnt] = ww2, at[v] = cnt;
        }
    }
    for (int i = 1; i <= n; ++i)
        ffa[i] = i, siz[i] = 1;
}
void solve(){
    int lft = n; 
    long long ans = 0;
    tarjan(1, 0);
    sort(id + 1, id + tot + 1, cmp);
    for (int i = 1; lft > 1; ++i){
        int u = to[id[i]], v = to[get(id[i])], ww = w[id[i]];
        if (Union(u, v))
            --lft, ans += ww;
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}