封锁阳光大学：最小割问题求解

曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。

阳光大学的校园是一张由 $n$ 个点构成的无向图，$n$ 个点之间由 $m$ 条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，曹就无法在这些道路上刷街了。非常悲剧的一点是，河蟹是一种不和谐的生物，当两只河蟹封锁了相邻的两个点时，他们会发生冲突。

询问：最少需要多少只河蟹，可以封锁所有道路并且不发生冲突。

输入格式

第一行两个正整数，表示节点数和边数。接下来 $m$ 行，每行两个整数 $u,v$，表示点 $u$ 到点 $v$ 之间有道路相连。

输出格式

仅一行如果河蟹无法封锁所有道路，则输出 'Impossible'，否则输出一个整数，表示最少需要多少只河蟹。

样例 #1

样例输入 #1

样例输出 #1

Impossible

样例 #2

样例输入 #2

3 2
1 2
2 3

样例输出 #2

提示

【数据规模】对于 $100%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，保证没有重边。

分析

这是一个最小割问题，可以使用最大流算法来解决。

将每个点拆分成两个点，一个表示入点，一个表示出点。然后连接源点和入点，容量为1，连接出点和汇点，容量为1。对于每条边 $(u,v)$，连接点 $u$ 的出点和点 $v$ 的入点，容量为1。

如果最大流等于边数 $m$，则可以封锁所有道路，输出最小割的值即可。否则，输出 'Impossible'。

算法步骤

创建图，并初始化源点和汇点。
读入边的信息，并连接相应的点。
使用最大流算法计算最大流。
判断最大流是否等于边数 $m$，如果是，则输出最小割的值，否则输出 'Impossible'。

代码实现

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int v;  // 目标点
    int cap;  // 容量
    int rev;  // 反向边的下标
};

// 添加边
void addEdge(vector<vector<Edge>>& graph, int u, int v, int cap) {
    graph[u].push_back({v, cap, graph[v].size()});
    graph[v].push_back({u, 0, graph[u].size() - 1});
}

// 通过BFS寻找增广路径
bool bfs(vector<vector<Edge>>& graph, int s, int t, vector<int>& level) {
    queue<int> q;
    q.push(s);
    
    level[s] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = 0; i < graph[u].size(); ++i) {
            Edge& e = graph[u][i];
            int v = e.v;
            
            if (level[v] < 0 && e.cap > 0) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    
    return level[t] >= 0;
}

// 通过DFS寻找增广路径
int dfs(vector<vector<Edge>>& graph, int u, int t, int f, vector<int>& level, vector<int>& iter) {
    if (u == t) {
        return f;
    }
    
    for (int& i = iter[u]; i < graph[u].size(); ++i) {
        Edge& e = graph[u][i];
        
        if (e.cap > 0 && level[u] + 1 == level[e.v]) {
            int d = dfs(graph, e.v, t, min(f, e.cap), level, iter);
            
            if (d > 0) {
                e.cap -= d;
                graph[e.v][e.rev].cap += d;
                return d;
            }
        }
    }
    
    return 0;
}

// 计算最大流
int maxFlow(vector<vector<Edge>>& graph, int s, int t) {
    int n = graph.size();
    vector<int> level(n, -1);  // 节点的层次
    vector<int> iter(n, 0);  // 每个节点当前遍历到的边的下标
    
    int maxFlow = 0;
    
    while (bfs(graph, s, t, level)) {
        int f;
        
        while ((f = dfs(graph, s, t, INF, level, iter)) > 0) {
            maxFlow += f;
        }
    }
    
    return maxFlow;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 创建图
    int numNodes = n * 2 + 2;  // 总节点数
    int source = numNodes - 2;  // 源点
    int sink = numNodes - 1;  // 汇点
    vector<vector<Edge>> graph(numNodes);
    
    // 初始化源点和汇点
    for (int i = 0; i < n; ++i) {
        addEdge(graph, source, i, 1);
        addEdge(graph, i + n, sink, 1);
    }
    
    // 读入边的信息，并连接相应的点
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        addEdge(graph, u, v + n, 1);
        addEdge(graph, v, u + n, 1);
    }
    
    // 计算最大流
    int maxFlowValue = maxFlow(graph, source, sink);
    
    if (maxFlowValue == m) {
        cout << maxFlowValue << endl;
    } else {
        cout << 'Impossible' << endl;
    }
    
    return 0;
}

复杂度分析

最大流算法的时间复杂度为 $O(V^2E)$，其中 $V$ 是节点数，$E$ 是边数。在本题中，$V=n2+2$，$E=m+n$。因此，总的时间复杂度为 $O((n2+2)^2*(m+n))$。

空间复杂度为 $O(V+E)$。在本题中，空间复杂度为 $O((n*2+2)+(m+n))$。