2018 China Collegiate Programming Contest Final (CCPC-Final 2018) B. Balance of the Force(二分图染色+尺取)-白红宇的个人博客

2018 China Collegiate Programming Contest Final (CCPC-Final 2018) B. Balance of the Force(二分图染色+尺取)

发布日期：2021-06-30 10:32:39 浏览次数：2 分类：技术文章

本文共 2428 字，大约阅读时间需要 8 分钟。

考虑把 $m$ 个限制关系看成边,一条边的两个端点颜色不能相同,这实际上就是一个二分图染色问题

(当然你也可以用 $2 - S A T$ 来处理,设置每个人为 $0 / 1$ 连边,会得到若干连通块的选择情况)

我们从每个点开始 $d f s$ 染色,会得到若干个连通块

每个连通块有两种选择方式,连通块中的人要么都是光明,要么都是黑暗

问题转化为 $x$ 个连通块

每个连通块要么选择 $l_i,r_i]$ ,要么选择 $L_i,R_i]$

求最优情况下,最小点和最大点的差值是多少

实际上我们可以尺取,把所有点装进结构体排序

一个区间如果两个端点都在我们尺取范围内,我们就涵盖了它

一个人的两个区间被涵盖任意一个我们就说涵盖了这个人

就是尺取一个区间使得涵盖所有人且长度最短

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;struct p{
       int pos,nxt,id;//分别表示自己的位置,属于哪个区间,属于哪个人    bool operator < ( const p&tmp ) const    {
           return pos

vec[maxn];void dfs(int u,int fa,int col){

if( col==0 ) {

mil[fa] = min( mil[fa],L[u] ), mir[fa] = max( mir[fa],L[u] ); mxl[fa] = min( mxl[fa],R[u] ), mxr[fa] = max( mxr[fa],R[u] ); } else {

mil[fa] = min( mil[fa],R[u] ), mir[fa] = max( mir[fa],R[u] ); mxl[fa] = min( mxl[fa],L[u] ), mxr[fa] = max( mxr[fa],L[u] ); } for( auto v:vec[u] ) {

if( vis[v] ) {

if( co[v]!=( col^1 ) ) flag = -1; continue; } vis[v] = 1; co[v] = col^1; dfs( v,fa,col^1 ); }}int qujian[maxn],ren[maxn],colnum;int add(p r){

qujian[r.nxt]++; if( qujian[r.nxt]==2 && ren[r.id]==0 ) ren[r.id]++,colnum++; else if( qujian[r.nxt]==2 ) ren[r.id]++;}int del(p r){

qujian[r.nxt]--; if( qujian[r.nxt]==1 && ren[r.id]==1 ) ren[r.id]--,colnum--; else if( qujian[r.nxt]==1 ) ren[r.id]--;}int ruler(int n,int m)//n是端点个数,m是连通块个数{

sort( a+1,a+1+n ); int ans = 1e18; for(int l=1,r=0;l<=n;l++) {

while( r

> t; while( t-- ) {

int n,m; cin >> n >> m; for(int i=1;i<=m;i++) {

int x,y; scanf("%lld%lld",&x,&y); vec[x].push_back( y ); vec[y].push_back( x ); } for(int i=1;i<=n;i++) scanf("%lld%lld",&L[i],&R[i] ); for(int i=1;i<=n;i++) {

if( vis[i] ) continue;//访问过了就不再访问 mil[i] = mir[i] = L[i], mxl[i] = mxr[i] = R[i]; lian++; vis[i] = 1; dfs(i,i,0); ++top; a[top] = (p){

mil[i],lian*2-1,lian }; ++top; a[top] = (p){

mir[i],lian*2-1,lian }; ++top; a[top] = (p){

mxl[i],lian*2,lian }; ++top; a[top] = (p){

mxr[i],lian*2,lian }; } cout << "Case " << ++casenum << ": "; if( flag==-1 ) cout << "IMPOSSIBLE" << endl; else ruler(top,lian); for(int i=1;i<=n;i++) vec[i].clear(); memset( ren,0,sizeof ren ); memset( qujian,0,sizeof qujian ); memset( vis,0,sizeof vis ); memset( co,0,sizeof co ); top = lian = colnum = flag = 0; }}

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116172143 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：P6793 [SNOI2020] 字符串(SAM树上贪心合并)

下一篇：2018 ccpc final G. Pastoral Life in Stardew Valley(组合数学)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章