[题目链接]
http://codeforces.com/contest/1027/problem/F
[算法]
二分图匹配
[代码]
#include<bits/stdc++.h>
#pragma GOC optimize("Ofast")
using namespace std;
const int MAXN = 1e6 + ; struct edge
{
int to,nxt;
} e[MAXN << ]; int n,q,len,ans,tot;
int a[MAXN],b[MAXN],ta[MAXN],tb[MAXN],tmp[MAXN << ],match[MAXN << ],head[MAXN << ],visited[MAXN << ]; template <typename T> inline void read(T &x)
{
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline bool hungary(int u,int k)
{
int v;
for (int i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (visited[v] != k)
{
visited[v] = k;
if (!match[v] || hungary(match[v],k))
{
match[v] = u;
return true;
}
}
}
return false;
} int main()
{ read(n);
for (int i = ; i <= n; i++)
{
read(a[i]); read(b[i]);
tmp[++len] = a[i]; tmp[++len] = b[i];
}
sort(tmp + ,tmp + len + );
len = unique(tmp + ,tmp + len + ) - tmp - ;
for (int i = ; i <= n; i++)
{
ta[i] = lower_bound(tmp + ,tmp + len + ,a[i]) - tmp;
tb[i] = lower_bound(tmp + ,tmp + len + ,b[i]) - tmp;
}
for (int i = ; i <= n; i++)
{
addedge(ta[i],len + i);
addedge(tb[i],len + i);
}
for (int i = ; i <= len; i++)
{
if (hungary(i,i))
{
ans++;
if (ans == n)
{
printf("%d\n",tmp[i]);
return ;
}
}
}
printf("-1\n"); return ; }