UVA - 11082 Dinic 上下界最大流

发表于 | 分类于 | 阅读次数：

这也能用最大流？？

好吧，其实我是知道它能用最大流的，否则我也不会千里迢迢来A它了，这是省赛选拔赛第一场的一道题目，比赛的时候没有人A，但是我觉得这个题目很不错，所以赛后就记住这是最大流类型的了，5个月之后，我终于把它A了。

题目链接

题意

告诉你一个矩阵前i行的和，前i列的和，实际上就是告诉你每一行的和， 每列的和，然后让你构造这个矩阵。

思路

利用最大流来求，但是注意这个下界是1，因此需要先减1，最后再把对应答案加上1. 我们把每一行的和A[i]看成一个点，源点到这些点的权值为A[i]-m, 把每一列的和B[i]看成一个点，这些点到汇点的权值为B[i]-n， 行点到列点的权值为19，这样形成的图求最大流，最后我们输出反边对应的权值+1就是答案，因为反边记录了流体的情况。

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;
const int inf = 0x3f3f3f3f;
int G[101][101];
int n, m, deep[501];
int A[50], B[50];
int bfs(int s, int t)
{
    queue<int>Q;
    Q.push(s);
    memset(deep, 0, sizeof(deep));
    deep[s] = 1;
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i = 0; i <= n + m + 1; ++i)
        {
            if(G[u][i] == 0) continue;
            int w = G[u][i];
            if(w > 0 && deep[i] == 0){
                deep[i] = deep[u] + 1;
                Q.push(i);
            }
        }
    }
    if(deep[t] == 0) return 0;
    return 1;
}

int dfs(int s, int dis)
{
    if(s == n + m + 1) return dis;
    for(int i = 0; i <= n + m + 1; ++i){
        if(G[s][i] == 0) continue;
        int w = G[s][i];
        if(w > 0 && deep[i] == deep[s] + 1){
            int d = dfs(i, min(w, dis));
            if(d > 0){
                G[s][i] -= d;
                G[i][s] += d;
                return d;
            }
        }
    }
    return 0;
}
int main()
{
    int T, caser = 1;
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        memset(G, 0, sizeof(G));
        int sum = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&A[i]);
            A[i] -= sum;
            sum += A[i];
            G[0][i] = A[i] - m;
        }
        sum = 0;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d",&B[i]);
            B[i] -= sum;
            sum += B[i];
            G[i + n][n + m + 1] = B[i] - n;
        }

        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                G[i][j + n] = 19;
            }
        }
        sum = 0;
        while(bfs(0, n + m + 1))
        {
            while(int d = dfs(0, inf))
            {
                sum += d;
            }
        }
        cout << "Matrix " << caser++ << '\n';
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= m; ++j)
            {
                printf("%d%c",G[j + n][i] + 1 , j == m?'\n':' ');
            }
        }
    }
}