-
Notifications
You must be signed in to change notification settings - Fork 0
/
11409.cpp
93 lines (80 loc) · 2.28 KB
/
11409.cpp
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
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAX_PEOPLE = 400;
const int MAX_JOB = 400;
const int MAX_V = 810;
const int INF = 987654321;
int flow[MAX_V][MAX_V], capacity[MAX_V][MAX_V], cost[MAX_V][MAX_V];
vector<int> connection[MAX_V];
vector<int> dist;
vector<bool> visited;
vector<int> parent;
int N, M;
void addEdge(int start, int end, int c) {
if (!flow[start][end] && !flow[end][start]) {
connection[start].push_back(end);
connection[end].push_back(start);
}
flow[start][end]++;
cost[start][end] = c;
cost[end][start] = -c;
}
int spfa() {
visited = vector<bool>(N + M + 2, false);
parent = vector<int>(N + M + 2, -1);
dist = vector<int>(N + M + 2, -INF);
dist[0] = 0;
visited[0] = true;
queue<int> q;
q.push(0);
while (!q.empty()) {
int here = q.front();
q.pop();
visited[here] = 0;
for (int i = 0; i < connection[here].size(); i++) {
int there = connection[here][i];
//이건 왜 하는건지 아직 잘 모르겠다
if (!flow[here][there]) continue;
if (dist[there] < dist[here] + cost[here][there]) {
dist[there] = dist[here] + cost[here][there];
parent[there] = here;
if (!visited[there]) {
visited[there] = true;
q.push(there);
}
}
}
}
return dist[M + N + 1] > -INF;
}
int main(void) {
int num, numOfWork, numOfCost;
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++) {
scanf("%d", &num);
for (int j = 0; j < num; j++) {
scanf("%d%d", &numOfWork, &numOfCost);
addEdge(i, N+numOfWork, numOfCost);
}
}
for (int i = 1; i <= N; i++)
addEdge(0, i, 0);
for (int i = 1; i <= M; i++)
addEdge(N+i, M + N + 1, 0);
int cnt = 0;
int totalFlow = 0;
while (spfa()) {
cnt++;
totalFlow += dist[M + N + 1];
//printf("%d\n", dist[M + N + 1]);
for (int p = N + M + 1; p !=0 ; p = parent[p]) {
flow[parent[p]][p]--;
flow[p][parent[p]]++;
}
}
printf("%d\n%d\n", cnt, totalFlow);
return 0;
}