백준11670 초등 수학

작성일 | In

문제 링크

  • http://icpc.me/11670

문제 출처

  • 2015 NWERC E번

사용 알고리즘

  • 이분 매칭

풀이

이분 매칭 문제입니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

typedef long long ll;

ll n, a[2525], b[2525];
vector<ll> comp;
vector<int> g[10101];
void addEdge(int s, int e){
    g[s].push_back(e);
    g[e].push_back(s);
}

int chk[10101], pv, par[10101], mat[10101];
bool dfs(int v){
    chk[v] = pv;
    for(auto i : g[v]){
        if(chk[i] == pv) continue;
        chk[i] = pv;
        if(par[i] == -1 || dfs(par[i])){
            par[i] = v; mat[v] = i; return true;
        }
    }
    return false;
}
int match(){
    int ret = 0;
    memset(par, -1, sizeof par);
    for(int i=1; i<=n; i++){
        pv++; ret += dfs(i);
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
        comp.push_back(a[i] + b[i]);
        comp.push_back(a[i] - b[i]);
        comp.push_back(a[i] * b[i]);
    }
    compress(comp);
    for(int i=1; i<=n; i++){
        int t1 = IDX(comp, a[i] + b[i]) + 2525;
        int t2 = IDX(comp, a[i] - b[i]) + 2525;
        int t3 = IDX(comp, a[i] * b[i]) + 2525;
        addEdge(i, t1); addEdge(i, t2); addEdge(i, t3);
    }
    int t = match();
    if(t != n){ cout << "impossible"; return 0; }
    for(int i=1; i<=n; i++){
        ll val = comp[mat[i] - 2525];
        if(a[i] + b[i] == val) cout << a[i] << " + " << b[i] << " = " << val << "\n";
        else if(a[i] - b[i] == val) cout << a[i] << " - " << b[i] << " = " << val << "\n";
        else cout << a[i] << " * " << b[i] << " = " << val << "\n";
    }
}