BOJ)11670 초등 수학

문제: icpc.me/11670

n개의 줄에 순서 쌍 a,b가 주어진다. 각 a,b에 대하여 a+b또는a-b또는a*b 에 일치하는 수들이 중복 없이 n개 존재한다면 그 답을 출력하는 문제이다.

이 문제는 잘 생각해보면 순서 쌍 a,b와 답이 될 수 있는 후보인 수들의 이분 그래프로 모델링 할 수 있다.

따라서 답을 구하기 위하여 이분 매칭을 구해주어 최대 매칭이 n이 된다면 답을 역추적하여 구해주고, n이 안된다면 impossible을 출력하면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll n, visited[2555], b[7555];
pair<ll, ll> inp[2555];
pair<char, ll> res[2555];
vector<vector<ll>> vt;
vector<ll> ele;
ll getidx(ll x) {
    return lower_bound(ele.begin(), ele.end(), x) - ele.begin() + 1;
}
bool dfs(ll here) {
    if (visited[here])return false;
    visited[here] = true;
    for (auto next : vt[here]) {
        if (!b[next] || dfs(b[next])) {
            b[next] = here;
            return true;
        }
    }
    return false;
}
ll bipartitematching() {
    ll match = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i))match++;
    }
    return match;
}
int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &inp[i].first, &inp[i].second);
        ele.push_back(inp[i].first + inp[i].second);
        ele.push_back(inp[i].first - inp[i].second);
        ele.push_back(inp[i].first*inp[i].second);
    }
    vt.resize(n + 1);
    sort(ele.begin(), ele.end());
    ele.erase(unique(ele.begin(), ele.end()), ele.end());
    for (int i = 1; i <= n; i++) {
        ll x = getidx(inp[i].first + inp[i].second);
        ll y = getidx(inp[i].first - inp[i].second);
        ll z = getidx(inp[i].first*inp[i].second);
        vt[i].push_back(x);
        vt[i].push_back(y);
        vt[i].push_back(z);
    }
    ll match = bipartitematching();
    if (match != n)
        puts("impossible");
    else {
        for (int i = 1; i <= ele.size(); i++) {
            if (!b[i])continue;
            if (inp[b[i]].first + inp[b[i]].second == ele[i - 1])
                res[b[i]] = { '+',ele[i - 1] };
            else if (inp[b[i]].first - inp[b[i]].second == ele[i - 1])
                res[b[i]] = { '-',ele[i - 1] };
            else
                res[b[i]] = { '*',ele[i - 1] };
        }
        for (int i = 1; i <= n; i++) 
            printf("%lld %c %lld = %lld\n", inp[i].first, res[i].first, inp[i].second, res[i].second);
    }
    return 0;
}