1. 首页
2. 二分匹配
3. 本页

UVALive 7427 Elementary Math (二分匹配)

题意：~

思路：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PI;

const int MAXN = 10010;
const int MAXM = 10010;
struct Edge
{
    int to,next;
}edge[MAXM];
int head[MAXN],tot;
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[tot].to = v; edge[tot].next = head[u];
    head[u] = tot++;
}
int linker[MAXN];
bool used[MAXN];
int uN;
bool dfs(int u)
{
    for(int i = head[u]; i != -1 ;i = edge[i].next)
    {
        int v = edge[i].to;
        if(!used[v])
        {
            used[v] = true;
            if(linker[v] == -1 || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int hungary()
{
    int res = 0;
    memset(linker,-1,sizeof(linker));
    for(int u = 0; u < uN;u++)
    {
        memset(used,false,sizeof(used));
        if(dfs(u)) res++;
    }
    return res;
}

map<LL, int> mp;
LL a[2510], b[2510], c[2510];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while(cin >> n)
    {
        init();
        mp.clear();
        int cnt = n;
        for(int i = 0; i < n; ++i)
        {
            cin >> a[i] >> b[i];
            LL tmp = a[i] - b[i];
            if(mp.find(tmp) == mp.end()) mp[tmp] = cnt++;
            addedge(i, mp[tmp]);
            tmp = a[i] + b[i];
            if(mp.find(tmp) == mp.end()) mp[tmp] = cnt++;
            addedge(i, mp[tmp]);
            tmp = a[i] * b[i];
            if(mp.find(tmp) == mp.end()) mp[tmp] = cnt++;
            addedge(i, mp[tmp]);
        }
        uN = n;
        int ans = hungary();
        if(ans < n)
        {
            cout << "impossible" << endl;
            continue;
        }
        for(int i = n; i < cnt; ++i)
        {
            if(linker[i] != -1)
            {
                for(auto &j : mp)
                {
                    if(j.second == i)
                    {
                        c[linker[i]] = j.first;
                        break;
                    }
                }
            }
        }
        for(int i = 0; i < n; ++i)
        {
            cout << a[i];
            if(a[i] + b[i] == c[i]) cout << " + ";
            else if(a[i] - b[i] == c[i]) cout << " - ";
            else cout << " * ";
            cout << b[i] << " = " << c[i] << endl;
        }
    }
    
    return 0;
}