题目描述

略= =

算法1

(暴力枚举)

随便你怎么暴力

算法2

最小生成树 $O(m)$

首先这题是困难就离谱。

没搞懂 $A_i$ 的意义是什么，题目都约定了 $\sum A[i] =0$ ，那么最小生成树的 $n$ 个节点一定满足这个条件。

那么就是裸板子了。

注意 $\forall A[i]=0$ 时，$ans=0$。

我当时 8min 就切掉了。/cy

时间复杂度

$O(m)$

C++ 代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MAXN = 100010;
const int MAXM = 100010;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int n, m, k;
int eu, ev, ans, tot, cnt;

int a[MAXN];
int fa[MAXN];

string s;

inline int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
    return s * f;
}

struct edge {
    int u, v, w;
}e[MAXN * 2];

int find(int x) {
    while (x != fa[x]) x = fa[x] = fa[fa[x]];
    return x;
}

bool cmp(edge x, edge y) {
    return x.w < y.w;
}

void Kruskal() {
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        eu = find(e[i].u);
        ev = find(e[i].v);
        if (eu == ev) continue;
        fa[eu] = ev;
        ans += e[i].w;
        if (++cnt == n - 1) break;
    }
}

int main(){
    int T, ok = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        ok = max(ok, a[i]);
        fa[i] = i;
    }
    if (!ok) {
        printf("0\n");
        return 0;
    }
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        e[i].u = u; e[i].v = v; e[i].w = w;
    }

    Kruskal();

    if (cnt != n - 1) printf("Impossible\n");
    else printf("%d\n", ans);
    return 0;
}