10.7 葡萄园

题意

? 盒饭的大伯有\(n\)个葡萄园子，第\(i\)个葡萄园子里有\(a_i\) 串葡萄。
? 现在有\(m\)条路径将这些葡萄园子全部连通，并保证不存在任意一条道路属于两个简单环（但是并不保证图中没有重边）。特别的，每条道路都有一种颜色标记，禁止该颜色的车辆经过。保证每辆车子都只有一种颜色，且所有车子和道路标记的颜色共三种，编号为\(1,2,3\)
? 盒饭想向你询问这\(q\)个问题，每个问题的形式如下：
? 他现在开着一辆可以自己决定颜色的车子，他每到一个庄园就可以吃这庄园里的所有葡萄，这个庄园的葡萄被吃完就没有了。同时他能带一瓶喷涂剂，可以在某个庄园里给车子换一种颜色，喷涂剂只能用一次。如果现在从\(k\)号点出发，他最多能吃到多少串葡萄。

解法

预处理每个点在某种颜色下属于哪个连通块（给联通块标号并计算其权值）

那么答案就是两个表示不同颜色的相邻连通块的并的点权和的最大值

如果枚举两个连通块并计算并集，复杂度是\(O(N^2)\)的，换个角度考虑，我们枚举并集

并集有一个特征：它的道路颜色一定是两个原集以外的那个

原因很简单，如果\(U_a ∪ U_b =U\)，那么\(U\)这一部分是既可以让\(a\)通行又可以让\(b\)通行的，由于一共只有三种颜色，那么它内部的道路一定是对\(c\)禁止的

我们枚举每个点是作为哪两个连通块的并集，并用map存储

有了这些信息，我们就可以预处理出每个点的答案了

枚举每个点作为并集，并分连通块进行计算

\(O(n\log n)\)预处理，\(O(1)\)回答询问

代码

#include <map>
#include <queue>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAX_N = 201000;

#define int long long

int N, M, Q, cnt;

int val[MAX_N], vis[MAX_N], sum[MAX_N], ans[MAX_N], loc[MAX_N][3];

int cap;
int head[MAX_N], to[MAX_N << 1], nxt[MAX_N << 1], lim[MAX_N << 1];

queue<int> que;
map<int, int> mp[MAX_N];

inline void add(int u, int v, int w) { to[++cap] = v, nxt[cap] = head[u], head[u] = cap, lim[cap] = w; }

void find(int x, int col) {
    ++cnt;
    que.push(x);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        if (vis[u])  continue;
        vis[u] = 1, sum[cnt] += val[u], loc[u][col] = cnt;
        for (int i = head[u]; i; i = nxt[i])
            if (!vis[to[i]] && (lim[i] ^ col))  que.push(to[i]);
    }
}

void BFS(int x, int col) {
    int tmp = 0;
    que.push(x);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        if (vis[u])  continue;
        vis[u] = 1, tmp += val[u];
        for (int i = head[u]; i; i = nxt[i])
            if (!vis[to[i]] && lim[i] == col)  que.push(to[i]);
    }
    if (col == 1)
        mp[loc[x][2]][loc[x][3]] += tmp;
    if (col == 2)
        mp[loc[x][1]][loc[x][3]] += tmp;
    if (col == 3)
        mp[loc[x][1]][loc[x][2]] += tmp;
}

signed main() {
    
    scanf("%lld%lld", &N, &M);
    
    for (int i = 1; i <= N; ++i)  scanf("%lld", val + i);
    
    int u, v, w;
    for (int i = 1; i <= M; ++i) {
        scanf("%lld%lld%lld", &u, &v, &w);
        add(u, v, w), add(v, u, w); 
    }
    
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= N; ++j)  if (!vis[j])  find(j, i);
        memset(vis, 0, sizeof vis);
    }
    
    for (int i = 1; i <= 3; ++i) {
        for (int j = 1; j <= N; ++j)  if (!vis[j])  BFS(j, i);
        memset(vis, 0, sizeof vis);
    }
    
    for (int i = 1; i <= N; ++i) {
        int a = loc[i][1], b = loc[i][2], c = loc[i][3];
        ans[a] = max(ans[a], sum[a] + max(sum[b] - mp[a][b], sum[c] - mp[a][c]));
        ans[b] = max(ans[b], sum[b] + max(sum[a] - mp[a][b], sum[c] - mp[b][c]));
        ans[c] = max(ans[c], sum[c] + max(sum[a] - mp[a][c], sum[b] - mp[b][c]));
    }
    
    scanf("%lld", &Q);
    while (Q--) {
        scanf("%lld", &u);
        printf("%lld\n", max(ans[loc[u][1]], max(ans[loc[u][2]], ans[loc[u][3]]))); 
    }
    
    return 0;
}

/*
10 10
3 1 7 6 3 6 10 4 1 2
10 9 1
10 9 1
2 1 1
3 1 3
4 3 2
5 2 2
6 4 1
7 6 3
8 7 2
10 8 1
7
2
1
8
7
9
5
9
*/

10.7 葡萄园

原文：https://www.cnblogs.com/VeniVidiVici/p/11631801.html