题目描述

给定一个 $n$ 个顶点,$m$ 条边的有向图.

你可以对这个有向图进行下面的操作.

1.删除一条边

2.增加一条边.

你的任务是求出最少操作几次才能将这个图变为和谐的图.

若不能,输出"Impossible".

和谐的图的定义如下.

1.每个顶点的入度不超过 $a$,但要大于等于 $b$.

2.每个顶点的出度不超过 $c$,但要大于等于 $d$.

输入格式

输入共 $m+1$ 行.

第一行有 $6$ 个正整数: $n,m,a,b,c,d$.

第 $2$ ~ $m+1$ 行,每行 $2$ 个正整数: $u,v$,表示有一条 $u$ 到 $v$ 的边.

输出格式

一个正整数,表示要操作的最少次数.

样例

4 3 3 1 2 1
1 2
1 4
2 3

2

数据规模

$a<b \le 50$

$c<d \le 50$

$n,m, \le 100$

原题链接(每天下午两点半左右才能访问,好像先注册一个账号才能看题,问那个网站的管理员吧)

我的代码

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

using namespace std;

const int INF = 1e9;
const int MAXN = 105;

struct Edge {
    int to, cap, rev;
};

vector<Edge> graph[MAXN];
int level[MAXN];
int iter[MAXN];

// 添加边
void add_edge(int from, int to, int cap) {
    graph[from].push_back((Edge){to, cap, (int)graph[to].size()});
    graph[to].push_back((Edge){from, 0, (int)graph[from].size() - 1});
}

// 通过BFS构建层次图
void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : graph[v]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
}

// 通过DFS寻找增广路
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.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                graph[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// 计算最大流
int max_flow(int s, int t) {
    int flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
}

int main() {
    int n, m, a, b, c, d;
    cin >> n >> m >> a >> b >> c >> d;
    
    vector<int> in_deg(n + 1, 0), out_deg(n + 1, 0);  // 入度和出度
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        out_deg[u]++;
        in_deg[v]++;
        edges.push_back({u, v});
    }

    int s = 0, t = 2 * n + 1;  // 源点和汇点

    // 构建流图
    for (int i = 1; i <= n; ++i) {
        // 顶点i的入度要求：b <= in_deg[i] <= a
        if (in_deg[i] < b) {
            add_edge(s, i, b - in_deg[i]);  // 从源点连边
        }
        if (in_deg[i] > a) {
            add_edge(i, t, in_deg[i] - a);  // 向汇点连边
        }

        // 顶点i的出度要求：d <= out_deg[i] <= c
        if (out_deg[i] < d) {
            add_edge(n + i, t, d - out_deg[i]);  // 向汇点连边
        }
        if (out_deg[i] > c) {
            add_edge(s, n + i, out_deg[i] - c);  // 从源点连边
        }

        // 顶点之间的平衡边
        add_edge(i, n + i, INF);  // 将入度和出度匹配
    }

    int result = max_flow(s, t);
    bool possible = true;
    for (int i = 1; i <= n; ++i) {
        if (in_deg[i] < b || in_deg[i] > a || out_deg[i] < d || out_deg[i] > c) {
            possible = false;
            break;
        }
    }

    if (possible) {
        cout << result << endl;
    } else {
        cout << "Impossible" << endl;
    }

    return 0;
}