【二分+2-SAT驗證】POJ2749[Building roads]題解

題目概述

有兩個中轉點和n個谷倉，每個谷倉隻能連向兩個中轉點的一個。某些谷倉中的牛互相厭惡，不能同時連向同一個中轉點，某些谷倉中的牛是朋友，必須同時連向同一個中轉點。求一種方案使得谷倉之間的曼哈頓距離的最大值最小。

解題報告

每個谷倉隻能連接配接中轉點1(S1)和中轉點2(S2)的一個，并且還有很多限制條件，我們不難發現這是2-SAT。但無論是暴力還是Tarjan，都不具備求距離最大值最小的功能，而求最大值最小經常是二分的題目，是以我們想到二分枚舉答案mid。

厭惡和朋友的限制比較明顯，但我們還需要用到答案mid來進行進一步的限制。由于所有谷倉之間的距離都不大于mid，那麼對于兩個谷倉i,j有下面四種情況：

1.dis(i,S1)+dis(S1,j)>MAX，意味着i谷倉和j谷倉不能同時選S1。

2.dis(i,S2)+dis(S2,j)>MAX，意味着i谷倉和j谷倉不能同時選S2。

3.dis(i,S1)+dis(S1,S2)+dis(S2,j)>MAX，意味着i谷倉選了S1，j谷倉就不能選S2，且j谷倉選了S2，i谷倉就不能選S1。

4.dis(i,S2)+dis(S2,S1)+dis(S1,j)>MAX，意味着i谷倉選了S2，j谷倉就不能選S1，且j谷倉選了S1，i谷倉就不能選S2。

接下來用Tarjan判斷2-SAT是否有解即可。

建邊的時候需要仔細，不能有遺漏，否則就會出錯。

示例程式

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxA=,maxB=,maxm=(maxA+maxB)*4+maxn*maxn*8;

int n,A,B,Sx[],Sy[],D;
int x[maxn+],y[maxn+],Aa[maxA+],Ab[maxA+],Ba[maxB+],Bb[maxB+];
int E,lnk[*maxn+],nxt[maxm+],son[maxm+];
int ti,tot,dfn[*maxn+],low[*maxn+],SCC[*maxn+];
int top,stk[*maxn+];bool instk[*maxn+];

int absi(int x) {if (x<) return -x; else return x;}
int getdis(int i,int j) {return absi(x[i]-Sx[j])+absi(y[i]-Sy[j]);}
void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void Build(int MAX)
{
    E=;memset(lnk,,sizeof(lnk));
    for (int i=;i<=A;i++)
    {
        Add(Aa[i]<<,Ab[i]<<^);Add(Ab[i]<<,Aa[i]<<^);
        Add(Aa[i]<<^,Ab[i]<<);Add(Ab[i]<<^,Aa[i]<<);
    }
    for (int i=;i<=B;i++)
    {
        Add(Ba[i]<<,Bb[i]<<);Add(Bb[i]<<^,Ba[i]<<^);
        Add(Ba[i]<<^,Bb[i]<<^);Add(Bb[i]<<,Ba[i]<<);
    }
    for (int i=;i<n-;i++)
    for (int j=i+;j<n;j++)
    {
        if (getdis(i,)+getdis(j,)>MAX) Add(i<<,j<<^),Add(j<<,i<<^);
        if (getdis(i,)+getdis(j,)>MAX) Add(i<<^,j<<),Add(j<<^,i<<);
        if (getdis(i,)+D+getdis(j,)>MAX) Add(i<<,j<<),Add(j<<^,i<<^);
        if (getdis(i,)+D+getdis(j,)>MAX) Add(i<<^,j<<^),Add(j<<,i<<);
    }
}
void Tarjan(int x)
{
    dfn[x]=low[x]=++ti;instk[x]=true;stk[++top]=x;
    for (int j=lnk[x];j;j=nxt[j])
        if (!dfn[son[j]]) Tarjan(son[j]),low[x]=min(low[x],low[son[j]]); else
        if (instk[son[j]]) low[x]=min(low[x],dfn[son[j]]);
    if (dfn[x]==low[x])
    {
        int y;tot++;
        do y=stk[top--],instk[y]=false,SCC[y]=tot;
        while (x!=y);
    }
}
bool Two_SAT()
{
    memset(dfn,,sizeof(dfn));
    for (int i=;i<*n;i++) if (!dfn[i]) Tarjan(i);
    for (int i=;i<*n;i+=) if (SCC[i]==SCC[i^]) return false;
    return true;
}
int main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%d%d%d%d%d",&n,&A,&B,&Sx[],&Sy[],&Sx[],&Sy[]);
    D=absi(Sx[]-Sx[])+absi(Sy[]-Sy[]);
    for (int i=;i<n;i++) scanf("%d%d",&x[i],&y[i]);
    for (int i=;i<=A;i++) scanf("%d%d",&Aa[i],&Ab[i]),Aa[i]--,Ab[i]--;
    for (int i=;i<=B;i++) scanf("%d%d",&Ba[i],&Bb[i]),Ba[i]--,Bb[i]--;
    int L=,R=;
    while (L<=R)
    {
        int mid=L+(R-L>>);Build(mid);
        if (Two_SAT()) R=mid-; else L=mid+;
    }
    if (L>) L=-;
    return printf("%d\n",L),;
}