2018南京区域赛I 最大流 Dinic

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

奇思妙想最大流

题目链接

题意

给你N个士兵的信息，给出每个士兵可以杀的一些人的编号，但是士兵只能挑选一个敌人并杀死他，现在有K个药水，1瓶药水只能作用在一个士兵的身上，每个士兵服用一瓶药水就可以多杀一个人，每个敌人只能被一个士兵杀死，现在问你所有士兵最多可以杀死多少人。

思路

建最大流的图， 源点连到每个士兵上，权值为1，代表每个士兵一开始就可以杀一人，源点到另外特殊的一点权值为K，然后这个特殊点连到每个士兵身上，每个权值为1，代表这K个药水可以分给士兵，并且每人最多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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;

int G[1005][1005];
int n, m,k;
const int inf = 0x3f3f3f3f;
int deep[1005];
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 + 2; i++)
        {
            if(G[u][i] == 0) continue;
            int w = G[u][i];
            if(deep[i] == 0 && w > 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 + 2) return dis;
    for(int i = 0; i <= n + m + 2; 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(dis, w));
            if(d > 0){
                G[s][i] -= d;
                G[i][s] += d;
                return d;
            }
        }
    }
    return 0;
}
int main()
{
   int num, num1;
    cin >> n >> m >> k;
     memset(G, 0, sizeof(G));
    for(int i = 1; i <= n; ++i)
    {
        cin >> num;
        G[0][i] = 1;
        G[n + m + 1][i] = 1;
        for(int j = 1; j <= num; ++j)
        {
            scanf("%d",&num1);
            G[i][num1 + n] = 1;
            G[num1 + n][n + m + 2] = 1;
        }
    }
    G[0][n + m + 1] = k;
    int sum = 0;
    while(bfs(0, n + m + 2))
    {
        while(int d = dfs(0, inf))
            sum += d;
    }
    cout << sum << '\n';
}