N coding

1575_졸업 본문

PS

1575_졸업

NYWOO19 2018. 9. 7. 18:49

고통받은 문제


어렵진 않은데 처음에 문제 잘못생각해서 겁나 어렵게 생각하다가 그래프 구성 못하고 가만히 있다가

잘못생각했다는 걸 깨닫고 짰는데 또오 출력 바로 하려고 하다가 오지게 틀린 문제다.

결과값 개수를 이미 들은 것중에 후보에 나온 애들의 개수를 세서 totalflow에서 빼서 출력했는데

생각해보니 그러면 음수값이 나올수도 있어서... 당연히 틀리는 코드였다 ㅠ


사전순으로 출력이 아니라면 그냥 유량으로 쉽게 풀리는데

사전순으로 출력이어서 mcmf로 풀었다.

이미 들은 과목이면 반드시 포함시키는 게 이득이니까 그럴수 있게 가중치를 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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
using namespace std;
 
struct Edge {
    int v, cap, rev, cost;
    Edge(int v, int cap, int rev, int cost) :v(v), cap(cap), rev(rev), cost(cost) {}
};
 
int ed, lec[101], N, a, b, cnt, totalcnt;
vector<vector<Edge>> adj;
int S, T, p[301], pidx[301], inq[301], dist[301];
 
void addEdge(int u, int v, int cap, int cost) {
    adj[u].emplace_back(v, cap, (int)adj[v].size(), cost);
    adj[v].emplace_back(u, 0, (int)adj[u].size() - 1-cost);
}
 
bool spfa() {
    memset(inq, 0sizeof(inq));
    fill(dist, dist + N + 1051e9);
    memset(p, -1sizeof(p));
    dist[S] = 0; inq[S] = 1;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int cur = q.front(); q.pop(); inq[cur] = 0;
        for (int i = 0; i < adj[cur].size(); ++i) {
            Edge next = adj[cur][i];
            if (next.cap > 0 && dist[next.v] > dist[cur] + next.cost) {
                dist[next.v] = dist[cur] + next.cost;
                p[next.v] = cur; pidx[next.v] = i;
                if (!inq[next.v]) {
                    q.push(next.v);
                    inq[next.v] = 1;
                }
            }
        }
    }
 
    return dist[T] != 1e9;
}
 
int solve() {
    int totalflow = 0;
 
    while (spfa()) {
        int flow = 1e9;
        for (int i = T; i != S; i = p[i]) {
            int prev = p[i], idx = pidx[i];
            flow = min(flow, adj[prev][idx].cap);
        }
 
        for (int i = T; i != S; i = p[i]) {
            int prev = p[i], idx = pidx[i];
            int rev = adj[prev][idx].rev;
            adj[prev][idx].cap -= flow;
            adj[i][rev].cap += flow;
        }
 
        totalflow += flow;
    }
 
    return totalflow;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> ed;
    for (int i = 0; i < ed; ++i) {
        cin >> a;
        lec[a] = 1;
    }
 
    cin >> N;
    adj.resize(100 + 2 + N + 1);
    S = 0, T = 100 + N + 1;
    for (int i = 1; i <= N; ++i) {
        cin >> cnt;
        cin >> b;
        for (int j = 0; j < b; ++j) {
            cin >> a;
            if (lec[a]) {
                addEdge(i, a + N, 10);
                lec[a] = 2;
            }
            else {//가중치는 그냥 숫자
                addEdge(i, a + N, 1, a);
            }
        }
 
        addEdge(S, i, cnt, 0);
        totalcnt += cnt;
    }
 
    ed = 0;
    for (int i = 1; i <= 100++i) {
        addEdge(i + N, T, 10);
        if (lec[i] == 2) ed++;
    }
 
    int totalflow = solve();
    if (totalflow != totalcnt) {
        cout << -1return 0;
    }
 
    
    //res는 sort
    vector<int> res;
    for (auto i : adj[T]) {
        if (i.cap && lec[i.v - N] == 0) {
            res.push_back(i.v - N);
        }
    }
 
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    cout << res.size() <<'\n';
    for (auto next : res)
        cout << next << ' ';
 
    return 0;
}
cs


'PS' 카테고리의 다른 글

5480_전함  (0) 2018.09.21
[Atcoder] ARC 102D - All Your Paths are Different Lengths  (2) 2018.09.13
9376_탈옥  (0) 2018.09.06
1886_프리즌 브레이크/Evacuation  (0) 2018.09.06
13576_Prefix와 Suffix  (0) 2018.08.31