cf1027F. Session in BSU(并查集 匈牙利)
2018-09-18 06:24:50来源:博客园 阅读 ()
题意
题目链接
$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; inline int read() { 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; if(!link[to] || Aug(link[to], tim)) { link[to] = x; return 1; } } return 0; } main() { N = read(); 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; inline int read() { 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() { N = read(); 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; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ4299: Codechef FRBSUM(主席树) 2018-09-18
- APUE 2 - 进程组(process group) 会话(session) job 2018-06-18
- ASP.NET 程序中删除文件夹导致session失效解决问题 2018-06-18
- iframe跨域与session失效问题 2018-06-18
- 如何在ashx页面获取Session值 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash