# cf1027F. Session in BSU(并查集 匈牙利)

## 题意

$n$个人，每个人可以在第$a_i$天或第$b_i$，一天最多考一场试，问在最优的情况下，最晚什么时候结束

## Sol

1、边数大于点数：因为每个条边都必须与一个点匹配，因此这样肯定无解

2、边数 = 点数：很显然是一棵基环树，输出最大值即可

3、边数 < 点数：这是一棵树，输出次大值即可

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define LL long long
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 7;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N;
int a[MAXN], b[MAXN], date[MAXN << 1], cnt, vis[MAXN], link[MAXN], atk[MAXN];
vector<int> v[MAXN];
int Aug(int x, int tim) {
for(int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if(vis[to] == tim) continue;
vis[to] = tim;
{
return 1;
}
}
return 0;
}
main() {
for(int i = 1; i <= N; i++) a[i] = read(), b[i] = read(), date[++cnt] = a[i], date[++cnt] = b[i];
sort(date + 1, date + cnt + 1);
cnt = unique(date + 1, date + cnt + 1) - date - 1;
for(int i = 1; i <= N; i++) {
a[i] = lower_bound(date + 1, date + cnt + 1, a[i]) - date,
b[i] = lower_bound(date + 1, date + cnt + 1, b[i]) - date;
v[a[i]].push_back(i);
v[b[i]].push_back(i);
}
int ans = 0, tot = 0;
for(int i = 1; i <= cnt; i++) {
if(Aug(i, i))
tot++;
if(tot == N) {
printf("%d", date[i]); return 0;
}
}
puts("-1");
return 0;
}
/*
3
23 27
22 26
27 30
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 2 * 1e6 + 10;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, a[MAXN], b[MAXN], date[MAXN << 1], cnt = 0, fa[MAXN], tag[MAXN], mx[MAXN], smx[MAXN];
int find(int x) {
if(fa[x] == x) return fa[x];
else return fa[x] = find(fa[x]);
}
int main() {
for(int i = 1; i <= N; i++) a[i] = read(), b[i] = read(), date[++cnt] = a[i], date[++cnt] = b[i];
sort(date + 1, date + cnt + 1);
cnt = unique(date + 1, date + cnt + 1) - date - 1;
for(int i = 1; i <= N; i++)
a[i] = lower_bound(date + 1, date + cnt + 1, a[i]) - date,
b[i] = lower_bound(date + 1, date + cnt + 1, b[i]) - date;
for(int i = 1; i <= cnt; i++) fa[i] = i, mx[i] = i;

for(int i = 1; i <= N; i++) {
int x = a[i], y = b[i];
int fx = find(x), fy = find(y);
if(find(x) != find(y)) {
fa[fy] = fx;  tag[fx] |= tag[fy];
if(mx[fy] > mx[fx]) smx[fx] = max(smx[fx], max(smx[fy], mx[fx])), mx[fx] = mx[fy];
else smx[fx] = max(smx[fx], mx[fy]);
}
else if(!tag[fx]) tag[fx] = 1;
else {puts("-1"); return 0;}
}
int ans = 0;
for(int i = 1; i <= cnt; i++) {
if(fa[i] == i)
if(tag[i]) ans = max(ans, mx[i]);
else ans = max(ans, smx[i]);
}
printf("%d\n", date[ans]);
return 0;
}

1811 篇文章123 人订阅

0 条评论

## 相关文章

22020

### LWC 53：694. Number of Distinct Islands

LWC 53：694. Number of Distinct Islands 传送门：694. Number of Distinct Islands Probl...

26570

16330

### HDU-6249-Alice’s Stamps

ACM模版 描述 ? 题解 DPDP 问题，设 dp[i][j]dp[i][j] 表示前 ii 个位置选取 jj 个区间的最优解。当然 ii 要加以处理，因为我...

27070

### C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边，下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

34840

12930

### hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法，张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

17300

### HuffmanTree的浅析和在C#中的算法实现

无论是在我们的开发项目中，还是在我们的日常生活中，都会较多的涉及到文件压缩。谈到文件压缩，可能会有人想问文件压缩到底是怎么实现的，实现的原理是什么...

23070

8620

13140