The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

I saw that the existing solutions did not use an STL vector, so I came to submit one.

Problem link

1: Reformulating the Problem

There are pp nodes and cc undirected edges in a graph, and there are nn nodes that cannot be deleted. Find the minimum number of nodes that need to be deleted so that none of these nn fixed points can reach node 1.

2: Analysis and Modeling

After reformulating the problem, we see that we need to delete some nodes (as few as possible) to make the entire graph become two disconnected parts. The minimum-cut (maximum-flow) algorithm in network-flow algorithms can handle this problem.

【Students unfamiliar with maximum-flow algorithms can first solve this template problem】
Maximum-flow template

However, ordinary minimum cut handles “deleting some edges of a graph so that its two parts become disconnected,” while this problem asks us to delete some nodes. Therefore, we need to convert nodes into edges.

I use the method of splitting every node into two nodes (an outgoing node and an incoming node). For a specific implementation, refer to the solution for P1345 Telecowmunication.

Here is a brief explanation. First, split every point in the graph into two points: an outgoing point and an incoming point.

There is a directed edge connecting these two nodes:

Every directed edge pointing to this point can only connect to the point’s incoming node. Every directed edge starting from this point can only start at its outgoing node.

What is the use of splitting every node into an outgoing point and an incoming point? In an ordinary minimum-cut problem, if we want to know how many edges must be removed to disconnect the sink and source of a graph, we can set the weight of every edge to 11, paying a cost of 11 to delete that edge.

In a minimum-cut problem based on cut vertices, we can set the weight of the edge connecting each node’s outgoing and incoming points to 11. Then, if we want to delete this node, we can pay a cost of 11 to cut this edge, which deletes the node as well.

This raises a problem: the statement explicitly says that some nodes cannot be deleted. If all weights are set to 11, how do we handle nodes that cannot be deleted?

For these key nodes (the undeletable nodes), we can set the capacity of their internal edges to INFINF, so the algorithm will not delete them (a minimum-cut algorithm computes the minimum cost that makes the graph disconnected, and setting a capacity to INFINF makes deleting that node very uneconomical).

Also note that, in addition to the key points mentioned in the statement, the source and sink cannot be deleted either, so this needs to be handled when building the graph. The problem asks for the minimum number of deleted nodes, so the edges connecting these nodes cannot be deleted either; their capacities must be set to INFINF.

After resolving the edge-capacity issue, we consider the source and sink. We can set node 1 as the source and connect every key point to the sink. The resulting answer is the minimum number of nodes to delete so that none of the key points can reach node 1 (if any key point can reach node 1, then the sink can also reach node 1).

Summary of the Graph-Building Steps

  1. Split every node into an incoming node and an outgoing node, with an internal edge between them.
  2. For a deletable node, set the capacity of its internal edge to 11.
  3. For an undeletable node, set the capacity of its internal edge to INFINF.
  4. The undeletable edges include:
    1. The source’s internal edge.
    2. The sink’s internal edge.
    3. The edges connecting every node.
    4. The internal edges of key points.
  5. Set the source to node 1 and connect the sink to every key point.

3: Algorithm

I use the Dinic algorithm, because each augmentation can find multiple augmenting paths, making it faster than the EK algorithm. If you are unfamiliar with it, see the solution for the maximum-flow template problem mentioned above.

4: Implementation Details

When implementing node splitting, we can set the number of a node’s incoming point to the node’s own number, and set the number of its outgoing point to its own number plus pp (the total number of nodes). This ensures that there are no duplicate numbers.

When implementing the Dinic algorithm, we need to operate on reverse edges. I use an STL vector to store edges, so I add a rev (reverse) variable to the node structure to record the index of the current edge’s reverse edge.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct node
{
    int to, mflow, rev; // to stores the number of the next node.
                        // mflow (maxflow) records the capacity of the current edge.
                        // rev (reverse) records the index of the current edge's reverse edge.
};
int p, c, n, s, t;
vector<node> edge[MAXM];
int g_farm[MAXM];                            // Intact farms (key points).
int layer[MAXM];                             // The layer of each node.
node assign_node(int to, int mflow, int rev) // Assignment function.
{
    node temp;
    temp.to = to, temp.mflow = mflow, temp.rev = rev;
    return temp;
}

void add_edge(int from, int to, int mflow) // Add an edge.
{
    edge[from].push_back(assign_node(to, mflow, edge[to].size()));   // No -1 is needed because edge[to] has not pushed node from yet.
    edge[to].push_back(assign_node(from, 0, edge[from].size() - 1)); // -1 is needed because vector indices start at 0, while .size() returns the number of elements.
}

namespace dinic
{
    bool layering() // Build layers.
    {
        bool vis[MAXM];
        memset(vis, false, sizeof(vis));
        memset(layer, 0, sizeof(layer));
        queue<int> q;
        vis[s] = true;
        layer[s] = 1;
        q.push(s);
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            for (auto nex : edge[cur]) // A C++11 feature: use nex to traverse all elements in edge[cur].
            {
                if (nex.mflow > 0 && vis[nex.to] == false)
                {
                    layer[nex.to] = layer[cur] + 1;
                    q.push(nex.to);
                    vis[nex.to] = true;
                }
            }
        }
        return (layer[t] != 0); // Return whether layering succeeded (whether the sink is reachable from the source).
    }

    int find_aug_path(int cur, int cur_flow) // Find an augmenting path.
    {
        if (cur == t)
        {
            return cur_flow;
        }
        int ans = 0;
        for (int i = 0; i < int(edge[cur].size()); i++)
        {
            if (edge[cur][i].mflow > 0 && layer[edge[cur][i].to] == layer[cur] + 1)
            {
                int nex_flow = find_aug_path(edge[cur][i].to, min(cur_flow, edge[cur][i].mflow));
                edge[cur][i].mflow -= nex_flow;                            // Forward edge.
                edge[edge[cur][i].to][edge[cur][i].rev].mflow += nex_flow; // Reverse edge.
                cur_flow -= nex_flow;
                ans += nex_flow;
                if (cur_flow <= 0) // If the current capacity is insufficient, return directly to save time.
                {
                    return ans;
                }
            }
        }
        return ans;
    }

    int find_maxflow()
    {
        int ans = 0;
        while (layering())
        {
            ans += find_aug_path(s, INF);
        }
        return ans;
    }
}

void input_creat() // Input and build the graph.
{
    scanf("%d%d%d", &p, &c, &n);
    s = 0, t = 2 * p + 1;
    add_edge(0, 1, INF);     // Add another node connected to the source's incoming point; its capacity is also set to INF.
    add_edge(1, 1 + p, INF); // Set the source's incoming and outgoing points to INF.
    for (int i = 1; i <= c; i++)
    {
        int from, to;
        scanf("%d%d", &from, &to);
        add_edge(from + p, to, INF); // Connect from's outgoing point to to's incoming point.
        add_edge(to + p, from, INF); // Connect to's outgoing point to from's incoming point.
    }
    for (int i = 1; i <= n; i++)
    { // n is the number of points that cannot be cut.
        int point;
        scanf("%d", &point);
        add_edge(point + p, t, INF);     // Connect all key points to the sink.
        add_edge(point, point + p, INF); // Set the capacity of every key point's internal edge to INF.
        g_farm[point] = 1;               // Mark the key point.
    }
    for (int i = 2; i <= p; i++)
    {
        if (!g_farm[i])
        {
            add_edge(i, i + p, 1); // All non-key points can be deleted, so set their internal edge capacity to 1.
        }
    }
}

main()
{
    input_creat();
    printf("%d", dinic::find_maxflow());
    system("pause");
}

This is my first time writing a solution, so there may be many problems. If you find anything incorrect, feel free to point it out in the comments or contact me privately. Questions about anything unclear are also welcome. Finally, if this solution helped you, please give it a like or share your thoughts in the comments.