题目链接

小欧皇

题目描述

在一个由 个城市和 条道路构成的图中，一部分城市已被占领。如果两个城市可以通过一条完全由已占领城市构成的路径相连，则它们属于同一个“商业区”。一个大小为 的商业区，内部可以产生 对商业关系，每对关系产生 点收益。

现在需要从未占领的城市中选择一个进行占领，目标是使占领后所有商业区的总收益之和最大。如果有多个城市能达到相同的最大收益，则选择编号最小的城市。

解题思路

  1. 问题转化

    问题的核心是计算图的连通分量带来的收益。一个由 个已占领城市构成的连通分量（商业区），其内部的城市两两之间都可以经商，产生的收益为 。总收益是所有这样连通分量收益的总和。

    我们需要枚举每一个未占领的城市，假设占领它，然后计算新的总收益，并找出能使总收益最大化的选择。

  2. 利用并查集 (DSU) 维护连通分量

    直接为每个选择重新计算总收益效率低下。我们可以先计算出初始状态（未占领任何新城市时）的总收益，然后对于每个选择，只计算它带来的收益增量。

    并查集是维护图连通性的绝佳工具。我们可以用它来表示当前所有已占领城市形成的各个“商业区”。

  3. 算法步骤

    1. 初始化：

      • 建立一个并查集，包含 个城市。为每个集合（根节点）维护一个 size 属性，记录该集合中已占领的城市数量。
      • 根据输入的 01 串，初始化每个城市的 size（已占领为 1，未占领为 0）。
      • 遍历所有 条道路。如果一条道路连接的两个城市 都是初始已占领的，则在并查集中合并 u 和 v。
      • 完成上述操作后，并查集就表示了初始的商业区格局。

    2. 计算初始总收益：

      • 遍历所有城市。如果一个城市 是其所在集合的根节点 (parent[i] == i)，则该集合是一个独立的连通分量。
      • 获取其已占领城市数量 ，累加其收益 到 initial_profit。

    3. 枚举未占领城市：

      • 遍历所有城市 （从 1 到 ）。如果 是一个未占领的城市：
      • 计算占领 后的收益：
        • 占领 后，它可能会将它连接的多个现有商业区合并成一个大的商业区。
        • 找出 的所有邻居中，哪些是已占领的。
        • 通过并查集的 find 操作，找到这些邻居所属的、互不相同的商业区（根节点）。
        • 假设 连接了 个不同的商业区，其大小分别为 。
        • 计算收益变化：
          • 在合并前，这 个商业区贡献的收益为 。
          • 占领 并合并后，形成了一个新的大商业区，其大小为 。
          • 这个新商业区贡献的收益为 。
          • 因此，总收益的变化量为（新收益 - 旧收益）。
        • 占领 后的总收益为 current_profit = initial_profit - (旧收益) + (新收益)。
      • 更新最优解：
        • 维护 max_profit 和 best_city。如果 current_profit > max_profit，则更新最优解。由于我们是按城市编号从小到大枚举的，所以收益相同时自然会保留编号最小的城市。

    4. 输出结果：

      • 输出 best_city 和 max_profit。如果没有任何未占领的城市，则总收益就是初始收益。

代码

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <set>
#include <algorithm>

using namespace std;

// DSU 结构体
struct DSU {
    vector<int> parent;
    vector<long long> occupied_size;

    DSU(int n, const string& s) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        occupied_size.assign(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                occupied_size[i + 1] = 1;
            }
        }
    }

    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            // 简单的合并，可以让编号小的作为根
            if (root_i > root_j) swap(root_i, root_j);
            parent[root_j] = root_i;
            occupied_size[root_i] += occupied_size[root_j];
        }
    }
};

// 计算组合数 C(k, 2)
long long calculate_profit(long long k) {
    if (k < 2) return 0;
    return k * (k - 1) / 2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<vector<int>> adj(n + 1);
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.push_back({u, v});
    }

    // 1. 初始化并查集，处理初始状态
    DSU dsu(n, s);
    for (const auto& edge : edges) {
        if (s[edge.first - 1] == '1' && s[edge.second - 1] == '1') {
            dsu.unite(edge.first, edge.second);
        }
    }

    // 2. 计算初始总收益
    long long initial_profit = 0;
    for (int i = 1; i <= n; ++i) {
        if (dsu.parent[i] == i) {
            initial_profit += calculate_profit(dsu.occupied_size[i]);
        }
    }

    long long max_profit = -1;
    int best_city = -1;

    // 3. 枚举所有未占领的城市
    bool has_unoccupied = false;
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '0') {
            has_unoccupied = true;
            // 找出邻居所在的、不同的、已占领的连通分量
            set<int> neighbor_roots;
            for (int neighbor : adj[i]) {
                if (s[neighbor - 1] == '1') {
                    neighbor_roots.insert(dsu.find(neighbor));
                }
            }

            long long profit_to_remove = 0;
            long long new_component_size = 1; // 城市 i 自己

            for (int root : neighbor_roots) {
                long long sz = dsu.occupied_size[root];
                profit_to_remove += calculate_profit(sz);
                new_component_size += sz;
            }

            long long profit_to_add = calculate_profit(new_component_size);
            long long current_total_profit = initial_profit - profit_to_remove + profit_to_add;

            if (best_city == -1 || current_total_profit > max_profit) {
                max_profit = current_total_profit;
                best_city = i;
            }
        }
    }
    
    // 如果没有未占领的城市，收益就是初始收益，按题意不会发生
    if (!has_unoccupied) {
        cout << "-1 " << initial_profit << endl; // 题目保证有未占领城市
    } else {
        cout << best_city << " " << max_profit << endl;
    }


    return 0;
}


import java.util.*;

public class Main {
    static class DSU {
        int[] parent;
        long[] occupiedSize;

        public DSU(int n, String s) {
            parent = new int[n + 1];
            occupiedSize = new long[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
                if (s.charAt(i - 1) == '1') {
                    occupiedSize[i] = 1;
                }
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        public void unite(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                if (rootI > rootJ) {
                    int temp = rootI;
                    rootI = rootJ;
                    rootJ = temp;
                }
                parent[rootJ] = rootI;
                occupiedSize[rootI] += occupiedSize[rootJ];
            }
        }
    }

    private static long calculateProfit(long k) {
        if (k < 2) return 0;
        return k * (k - 1) / 2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String s = sc.next();
        
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        
        int[][] edges = new int[m][2];
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
            adj.get(v).add(u);
            edges[i][0] = u;
            edges[i][1] = v;
        }

        DSU dsu = new DSU(n, s);
        for (int[] edge : edges) {
            if (s.charAt(edge[0] - 1) == '1' && s.charAt(edge[1] - 1) == '1') {
                dsu.unite(edge[0], edge[1]);
            }
        }

        long initialProfit = 0;
        for (int i = 1; i <= n; i++) {
            if (dsu.parent[i] == i) {
                initialProfit += calculateProfit(dsu.occupiedSize[i]);
            }
        }

        long maxProfit = -1;
        int bestCity = -1;
        boolean hasUnoccupied = false;

        for (int i = 1; i <= n; i++) {
            if (s.charAt(i - 1) == '0') {
                hasUnoccupied = true;
                Set<Integer> neighborRoots = new HashSet<>();
                for (int neighbor : adj.get(i)) {
                    if (s.charAt(neighbor - 1) == '1') {
                        neighborRoots.add(dsu.find(neighbor));
                    }
                }

                long profitToRemove = 0;
                long newComponentSize = 1;

                for (int root : neighborRoots) {
                    long sz = dsu.occupiedSize[root];
                    profitToRemove += calculateProfit(sz);
                    newComponentSize += sz;
                }

                long profitToAdd = calculateProfit(newComponentSize);
                long currentTotalProfit = initialProfit - profitToRemove + profitToAdd;

                if (bestCity == -1 || currentTotalProfit > maxProfit) {
                    maxProfit = currentTotalProfit;
                    bestCity = i;
                }
            }
        }
        
        if (!hasUnoccupied) {
             System.out.println("-1 " + initialProfit);
        } else {
             System.out.println(bestCity + " " + maxProfit);
        }
    }
}


import sys

# 提高递归深度限制
sys.setrecursionlimit(200005)

def find(parent, i):
    if parent[i] == i:
        return i
    parent[i] = find(parent, parent[i])
    return parent[i]

def unite(parent, occupied_size, i, j):
    root_i = find(parent, i)
    root_j = find(parent, j)
    if root_i != root_j:
        # 简单的合并策略，让小编号作为根
        if root_i > root_j:
            root_i, root_j = root_j, root_i
        parent[root_j] = root_i
        occupied_size[root_i] += occupied_size[root_j]

def calculate_profit(k):
    if k < 2:
        return 0
    return k * (k - 1) // 2

def solve():
    # 读取输入
    lines = sys.stdin.readlines()
    if not lines:
        return
        
    n, m = map(int, lines[0].split())
    s = lines[1].strip()
    adj = [[] for _ in range(n + 1)]
    edges = []
    for i in range(2, m + 2):
        u, v = map(int, lines[i].split())
        adj[u].append(v)
        adj[v].append(u)
        edges.append((u, v))
    
    # 1. 初始化并查集
    parent = list(range(n + 1))
    occupied_size = [0] * (n + 1)
    for i in range(n):
        if s[i] == '1':
            occupied_size[i + 1] = 1

    # 2. 合并初始已占领的城市
    for u, v in edges:
        if s[u - 1] == '1' and s[v - 1] == '1':
            unite(parent, occupied_size, u, v)

    # 3. 计算初始收益
    initial_profit = 0
    for i in range(1, n + 1):
        if parent[i] == i:
            initial_profit += calculate_profit(occupied_size[i])

    max_profit = -1
    best_city = -1
    has_unoccupied = False

    # 4. 枚举未占领的城市
    for i in range(1, n + 1):
        if s[i - 1] == '0':
            has_unoccupied = True
            neighbor_roots = set()
            for neighbor in adj[i]:
                if s[neighbor - 1] == '1':
                    neighbor_roots.add(find(parent, neighbor))

            profit_to_remove = 0
            new_component_size = 1
            for root in neighbor_roots:
                sz = occupied_size[root]
                profit_to_remove += calculate_profit(sz)
                new_component_size += sz
            
            profit_to_add = calculate_profit(new_component_size)
            current_total_profit = initial_profit - profit_to_remove + profit_to_add

            if best_city == -1 or current_total_profit > max_profit:
                max_profit = current_total_profit
                best_city = i

    if not has_unoccupied:
        # 题目保证有未占领的城市，此分支理论上不可达
        print(f"-1 {initial_profit}")
    else:
        print(f"{best_city} {max_profit}")

solve()

算法及复杂度

  • 算法：并查集 (Disjoint Set Union)
  • 时间复杂度：，其中 是城市数量， 是道路数量， 是反阿克曼函数，其增长极其缓慢，可近似视为常数。初始化并查集和邻接表需要 ，计算初始连通分量需要 ，枚举每个未占领城市并检查其邻居的总操作次数与总边数成正比，为 。
  • 空间复杂度：，用于存储图的邻接表以及并查集所需的数组。