题目分析

这道题目描述了一个社交网络中的联系问题。给定$N$个人（编号$1$到$N$），以及他们之间的联系方式（通过电话号码）。两个人$A$和$B$可以保持联系的条件是：

1. $A$知道$B$的电话号码，或者
2. $A$知道$C$的电话号码，且$C$可以与$B$保持联系。

题目保证如果$A$知道$B$的号码，那么$B$也知道$A$的号码（即关系是对称的）。现在给定两个人$S$和$T$，要求找出最少需要让多少人失去联系（即删除这些人），才能使$S$和$T$无法保持联系。注意不能删除$S$或$T$本身。

解题思路

1. 问题建模：

   • 将问题转化为图论中的最小顶点割问题。
   • 每个人是图中的一个顶点，如果两个人互相知道电话号码，则他们之间有一条无向边。
   • 我们需要找到最小的顶点集合，使得删除这些顶点后，$S$和$T$不再连通。

2. 算法选择：

   • 使用网络流算法（Dinic算法）来解决最小顶点割问题。
   • 具体步骤：
     • 将每个顶点拆分为两个节点（入点和出点），入点到出点的边容量为$1$（表示删除该顶点的代价）。
     • 原始图中的边转换为出点到入点的无限容量边（表示这些边不能被割断）。
     • 求从$S$的出点到$T$的入点的最小割。

3. 输出结果：

   • 根据最小割的结果输出需要删除的人，并按题目要求排序（升序）。
   • 如果存在多个解，选择分数最小的解（按题目给定的评分规则）。

标程代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 0x7fffffff
using namespace std;

const int MAXN = 405; // 拆点后最多2*200=400个点

struct Edge {
    int to, capacity, rev;
    Edge(int t, int c, int r) : to(t), capacity(c), rev(r) {}
};

vector<Edge> graph[MAXN];
int level[MAXN], iter[MAXN];
bool vis[MAXN];
int mp[205][205];
int n, s, t, S, T;

void add_edge(int from, int to, int capacity) {
    graph[from].emplace_back(to, capacity, graph[to].size());
    graph[to].emplace_back(from, 0, graph[from].size() - 1);
}

void build() {
    for (int i = 0; i < MAXN; i++) graph[i].clear();
    add_edge(S, s, INF);
    add_edge(t + n, T, INF);
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && i != s && i != t) add_edge(i, i + n, 1);
        for (int j = 1; j <= n; j++) {
            if (mp[i][j]) add_edge(i + n, j, INF);
        }
    }
    add_edge(s, s + n, INF);
    add_edge(t, t + n, INF);
}

bool bfs(int S, int T) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[S] = 0;
    q.push(S);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (const Edge& e : graph[v]) {
            if (e.capacity > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
    return level[T] != -1;
}

int dfs(int v, int T, int f) {
    if (v == T) return f;
    for (int& i = iter[v]; i < graph[v].size(); i++) {
        Edge& e = graph[v][i];
        if (e.capacity > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, T, min(f, e.capacity));
            if (d > 0) {
                e.capacity -= d;
                graph[e.to][e.rev].capacity += d;
                return d;
            }
        }
    }
    return 0;
}

int Dinic(int S, int T) {
    int flow = 0;
    while (bfs(S, T)) {
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(S, T, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

int main() {
    while (~scanf("%d%d%d", &n, &s, &t)) {
        S = 0;
        T = 2 * n + 1;
        memset(vis, 0, sizeof(vis));
        memset(mp, 0, sizeof(mp));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &mp[i][j]);
            }
        }
        if (mp[s][t]) {
            printf("NO ANSWER!\n");
            continue;
        }
        build();
        int ans = Dinic(S, T);
        printf("%d\n", ans);
        if (ans == 0) continue;
        int tmp = ans;
        vector<int> cut;
        for (int i = 1; i <= n; i++) {
            if (i == s || i == t) continue;
            vis[i] = 1;
            build();
            int sum = Dinic(S, T);
            if (sum < tmp) {
                tmp = sum;
                cut.push_back(i);
            } else {
                vis[i] = 0;
            }
            if (tmp == 0) break;
        }
        sort(cut.begin(), cut.end());
        for (int i = 0; i < cut.size(); i++) {
            if (i > 0) printf(" ");
            printf("%d", cut[i]);
        }
        printf("\n");
    }
    return 0;
}

代码解释

1. 数据结构：

   • Edge结构体表示图的边，包含目标节点、容量和反向边索引。
   • graph数组存储图的邻接表。
   • level和iter数组用于Dinic算法的BFS和DFS步骤。

2. 核心函数：

   • add_edge：添加边到图中，并建立反向边。
   • build：构建拆点后的网络流图。
   • bfs：计算层次图。
   • dfs：寻找增广路径。
   • Dinic：计算最大流（最小割）。

3. 主流程：

   • 读取输入并初始化。
   • 检查$S$和$T$是否直接相连。
   • 构建网络流图并计算最小割。
   • 输出结果，包括最小割的大小和具体删除的顶点。

注意事项

1. 顶点编号：

   • 原始顶点$i$拆分为$i$（入点）和$i+n$（出点）。
   • 超级源点$S=0$，超级汇点$T=2n+1$。

2. 边界条件：

   • 如果$S$和$T$直接相连，直接输出NO ANSWER!。
   • 如果最小割为$0$，表示不需要删除任何顶点。

3. 时间复杂度：

   • Dinic算法的时间复杂度为$O(V^2E)$，其中$V=2N$，$E=O(N^2)$，适用于$N \leq 200$的规模。