gym 101485E 二分匹配

gym 101485E题意:
给出 n 个 a,b 对,有三种运算符 + 、- 、* 。要你给出每对 a, b 指定运算符,使得最后 n个答案都不相同。
tags:
真是该退役了,写个二分匹配都写这么久 -_-
离散化,建个图跑匹配就好了。。也可以网络流// gym 101485E #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 2505, M = 1000005; const ll inf = 1e13; int n; ll a[N], b[N]; vector< int > G[M]; map< pair<int , int > , pair<char, ll> > mp; int match[M]; bool used[M]; bool dfs(int u) { used[u] = true; for(int to : G[u]) if(match[to]==-1 || !used[match[to]] && dfs(match[to])) { match[u] = to, match[to] = u; return true; } return false; } bool solve() { memset(match, -1, sizeof(match)); for(int i=1; i<=n; ++i) if(match[i]==-1) { memset(used, false, sizeof(used)); if(!dfs(i)) return false; } return true; } ll c[N]; int cnt=0; int get_id(ll x) { return lower_bound(c+1, c+1+cnt, x) - c; } int main() { scanf("%d", &n); rep(i,1,n) { scanf("%lld%lld", &a[i], &b[i]); c[++cnt] = a[i]+b[i]+inf; c[++cnt] = a[i]-b[i]+inf; c[++cnt] = a[i]*b[i]+inf; c[++cnt] = i; } sort(c+1, c+1+cnt); cnt = unique(c+1, c+1+cnt) - (c+1); rep(i,1,n) { int tmp = get_id(a[i]+b[i]+inf); // + G[tmp].PB(i), G[i].PB(tmp); mp[MP(i, tmp)] = MP('+', a[i]+b[i]); tmp = get_id(a[i]-b[i]+inf); //- G[tmp].PB(i), G[i].PB(tmp); mp[MP(i, tmp)] = MP('-', a[i]-b[i]); tmp = get_id(a[i]*b[i]+inf); //* G[tmp].PB(i), G[i].PB(tmp); mp[MP(i, tmp)] = MP('*', a[i]*b[i]); } if(!solve()) puts("impossible"); else { rep(i,1,n) { int to = match[i]; printf("%lld %c %lld = %lldn", a[i], mp[MP(i, to)].fi, b[i], mp[MP(i,to)].se); } } return 0; }

相关内容推荐