SDUT4532-雀士分组（二分图+二分）

题目链接

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2956/pid/4532

解题思路

首先用二分图进行染色，如果在染色过程中发现冲突就直接输出impossible，对于每个染色的连通分量都记录其中甲方的最大最小值和乙方的最大最小值，然后二分答案，check函数取循环检查每一个连通分量的四个最大最小值与全图的最大最小值的搭配是否有大于传入的mid的，若没有则可行，否则不可行。

代码

#include <bits/stdc++.h>
const int maxn=1e5+100;
const int inf=0x3f3f3f3f;
using namespace std;
int n,m,tot,flag;
int minn,maxx,id;
int vis[maxn],head[maxn],a[maxn];
struct node{
    int v,to;
}edge[maxn*2];
struct data{
    int minn[3],maxx[3],sum;
}w[maxn];
void add(int u,int v){
    edge[tot]={v,head[u]};
    head[u]=tot++;
}
void dfs(int x,int f,int fa){
    w[id].minn[f]=min(w[id].minn[f],a[x]);
    w[id].maxx[f]=max(w[id].maxx[f],a[x]);
    if(vis[x]!=-1){
        if(vis[x]!=f)
            flag=1;
        return;
    }
    w[id].sum++;
    vis[x]=f;
    for(int i=head[x];i!=-1;i=edge[i].to){
        int v=edge[i].v;
        if(v!=fa)
            dfs(v,f^1,x);
    }
}
bool check(int mid){
    for(int i=1;i<=id;i++){
        if(w[i].sum==1){//连通分量中只有一个点的时候
            if(w[i].maxx[0]-minn>mid&&maxx-w[i].minn[0]>mid)
                return 0;
        }
        else{//枚举两种情况下差的最小值
            int big=inf;
            big=min(big,max(w[i].maxx[1]-minn,maxx-w[i].minn[0]));
            big=min(big,max(w[i].maxx[0]-minn,maxx-w[i].minn[1]));
            if(big>mid)return 0;
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    memset(vis,-1,sizeof(vis));
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        head[i]=-1;
    }
    cin>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    minn=inf;
    for(int i=1;i<=n;i++){
        if(vis[i]==-1){//二分图染色并求连通分量中的最大最小值
            ++id;
            w[id].sum=0;
            w[id].minn[1]=w[id].minn[0]=inf;
            w[id].maxx[1]=w[id].maxx[0]=0;
            dfs(i,0,0);
            minn=min(minn,min(w[id].minn[1],w[id].minn[0]));
            maxx=max(maxx,max(w[id].maxx[1],w[id].maxx[0]));
        }
    }
    if(flag)cout<<"impossible"<<endl;
    else{
        int l=0,r=100000002;
        int ans=-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid))ans=mid,r=mid-1;
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}