PS와 개발을 공부하자

BOJ 9169번 나는 9999번 문제를 풀 수 있다 본문

Algorithm/Problem Solving

BOJ 9169번 나는 9999번 문제를 풀 수 있다

sgc109 2017.07.15 02:05

https://www.acmicpc.net/problem/9169




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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
struct edge{int to, cap, rev;};
vector<edge> G[303];
void connect(int from, int to, int cap){
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, 0, (int)G[from].size()-1});
}
int N, M, T;
int think[303];
int main() {
    ios_base::sync_with_stdio(false),cin.tie(NULL);
    int src = 0, sink = 1;
    while(1){
        for(int i = 0 ; i < 303; i++) G[i].clear();
        cin >> N >> M;
        if(!&& !M) break;
        for(int i = 0 ; i < N; i++cin >> think[i];
        for(int i = 0 ; i < M; i++){
            int a,b;
            cin >> a >> b;
            if(think[a-1== think[b-1]) {
                connect(a + 1, b + 11);
                connect(b + 1, a + 11);
                continue;
            }
            if(think[a-1]) swap(a, b);
            connect(a + 1, b + 11);
        }
        for(int i = 0 ; i < N; i++){
            if(think[i]) connect(i + 2, sink, 1);
            else connect(src, i + 21);
        }
        Dinic dinic(G, 303, src, sink);
        cout << dinic.getMaxflow() << endl;
    }
    return 0;
}
cs


0 Comments
댓글쓰기 폼