Codeforces Round #818 (Div.2)F(最大流)

Codeforces Round #818 (Div.2)F(最大流)

原题链接：https://codeforc.es/contest/1717/problem/F

参考资料：https://zhuanlan.zhihu.com/p/560930180

前言：由于本人刚学完Acwing的网络流课程，但是由于本身codeforces分数不高 ( 某些地方可能理解不到位，请指出，感谢！！！

题意

给定长度为 n 的数组 a[],s[], 和 m 对数对(u , v) ，其中u ，v对应数组a[] 的索引下标(下标从1开始)，有以下的操作 (如果是 (u ,v)) 那么即有 b[u] -= 1, b[v] += 1（下标从1开始）；并有一个初始化为0，长度为 n 的数组b[]; s[]由’0’ ‘1’ 2种字符构造，要求在经过 m个数对的操作后 。 （1）当s[i] = ‘1’ 时，a[i] == b[i]

（2）当s[i] = ‘0’ 时，不做要求（b[i] 任意为一个数字均可）

输入

第一行输入 n, m

第二行输入 s[]

第三行输入 a[]

接下来的 m 行输入 数对（u ，v）

输出

第一行：如果经过 m 次操作 可以使得 b数组 == a数组，输出"YES" ，反之输出 “NO”

如果 可以构造得出来 b数组，则 接下来的 m 行 输出 构造的的方案

(u , v) 表示 b[u] -= 1, b[v] += 1， 可以交换 前后顺序 —>> (v , u)

思路

（1）转化问题

简化题意：相当于是给出了 m 对操作， 当s[i] = ‘1’ 时，要求构造出 a[i] = b[i]

其中则 m 对操作 分别时 -1 和 +1

那么将 b 变成 a，也相当于 a 变成 b；也就是经过这 m 对操作，使得 当s[i] = ‘1’ 时 a[i] = 0

接下来考虑操作：

对于 一个数对 (u , v) 有 a[u] -= 1, a[v] += 1，那么如果绕一个弯呢？

先让 a[u] += 1, a[v] += 1,然后再让 a[u] -= 2，也能达到相同的效果

这样做有什么好处呢 ?

(1) 可以进行对答案的过滤，因为我们是需要将 a数组，当s[i] = 1的 部分 a[i] = 0的，因此只要先对 a[i] + 1 后，再看看 此刻的 a[i] % 2 的结果：

​ <1> 如果 模数是 ‘1’ 说明无解 输出"NO",因为 -2 不论多少次都无法将这个位置的 a[i] 变成0

​ <2> 如果 模数是 ‘0’ ，此情况合理

<3> 如果 a[i] < 0 ，那么也输出 “NO”, 与 <1> 同理

(2) 那么接下来就是 选择 (m对数对中的2 * m 个待选择的索引 ：划分为集合A) 和 (数组中的位置索引i ： 划分为集合B) 进行匹配

那么问题就转化为了 网络流中的匹配问题

接下来就是要考虑如何去建图了

<1> 首先建立 S，T

<2> m 对数对中的 2 * m个索引，每个只能被选择一次，所以从 S -> 向 第i个数对连容量是 1的边

<3> 对于第 i 个数对中的 (u , v) 分别有 i - > u + m; i - > v + m，容量均为 1

<4> 对于 (数组中的位置索引i 且 s[i] == 1) ，从它向 T 连一条容量是 a[i] / 2 的边，表示选择(a[i]/2)的意思

<5> 我们还要加一个限制，让A中所有点都用到。记ceCnt为进入A的流量减去B中s[i] 不为0的点出去的流量，则我们只需让这些剩余的流量也都流出去。 对于<4> 它对数字的操作相当于 -1,对于ceCnt 一开始初始化为 m，然后再 - |（-1）st[i] == 1| 的操作，得到 | (- 1) st[i] == 0|的操作的容量

<6>增加一个中间点tmp，让每个s[i]为0的点连接到tmp，流量为INF（>=CeCnt即可），然后tmp连接到汇点，流量为ceCnt。

根据上面建图可得：我画的网络流图

然后就是求最大流，判断最大流是否等于 m :(表示 - 1的个数)

方案数就是依次枚举 m个数对 i，然后看i ，寻找i 的两个(u , v) 路中哪条漫流了，就代表 选择了 u或v -1 了（具体看代码展示）

C++ 代码

#include 
using namespace std;

#define endl '\n'

const int N = 1e5 + 10, M = N << 1;
int n, m, S, T;
const int INF = 0x3f3f3f3f;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c) // 添加一条边a->b，容量为c；同时添加一条反向边
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() // 创建分层图
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T)
                    return true;
                q[++tt] = ver;
            }
        }
    }
    return false; // 没有增广路
}

int find(int u, int limit) // 在残留网络中增广
{
    if (u == T)
        return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i; // 当前弧优化
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t)
                d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs())
        while (flow = find(S, INF))
            r += flow;
    return r;
}

void solve()
{
    cin >> n >> m;
    vector<int> s(n), a(n), b(n);
    vector<pair<int, int>> edges(m);

    for (int i = 0; i < n; i++)
        cin >> s[i];

    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        edges[i].first = a;
        edges[i].second = b;
    }

    for (auto &[u, v] : edges)
    {
        u--;
        v--;
        a[u]++;
        a[v]++;
    }

    int ceCnt = m;
    for (int i = 0; i < n; i++)
    {
        if (!s[i])
            continue;
        if (a[i] < 0 || (a[i] & 1))
        {
            cout << "No" << endl;
            return;
        }
        ceCnt -= a[i] / 2;
    }

    S = n + m;
    T = n + m + 1;
    int tmp = n + m + 2;

    for (int i = 0; i < m; i++)
    {
        auto &[u, v] = edges[i];
        add(S, i, 1);
        add(i, u + m, 1);
        add(i, v + m, 1);
    }

    for (int i = 0; i < n; i++)
    {
        if (s[i])
        {
            add(i + m, T, a[i] / 2);
        }
        else
        {
            add(i + m, tmp, ceCnt);
        }
    }
    add(tmp, T, ceCnt);

    if (ceCnt < 0 || dinic() != m)
    {
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;
    for (int i = 0; i < m; i++)
    {
        auto &[u, v] = edges[i];
        if (f[i * 6 + 2] == 0) //看图上边的标号
            swap(v, u);
        cout << u + 1 << " " << v + 1 << "\n";
    }
    return 0;
}
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152