本文主要是介绍HDU 1815 Building roads 二分+2-sat充分理解建图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你两个中转点s1，s2，和很多其他的点d{}，d{}里面的点只能连接s1或s2，不能同时连接两个，给你一些关系：com(a,b)表示a，b要同时连接同一个中转点，dex(a,b)表示a，b不能同时连接同一个中转点，问你d{}里面的两对点的最大距离的最小值。
想法：看到了最大距离的最小值，显然用二分枚举，这里有一个小优化，我们不容易确定最大的一个距离点对，但是我们可以很容易的找到一个最小的。
这道题就是考建图，分为两个方面：1.com和dex的建图。2.极限距离的限制建图
还有就是一个很重要的一点：建图的时候，你的建边顺序不正确，你的答案也可能超时，这是我的亲身经历，之前以为无所谓的。（但是我不知道为什么？会的留言）
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<stack>
#define inf 0x7fffffff
using namespace std;
const int nd=1000+50;
int N,A,B;
struct node
{int x,y;
}Dian[500+5],s1,s2;
int downlimit;
int fuck[1100][2],sex[1100][2];
struct nodee
{int v,next;
}e[nd*nd*10];
int head[nd],cnt;
int s_1[500+5],s_2[500+5];
int dfn[nd],low[nd],instack[nd],paint[nd],index,col;
stack<int>s;
void Init()
{index=col=1;while(!s.empty()) s.pop();memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(paint,0,sizeof(paint));memset(instack,0,sizeof(instack));memset(head,-1,sizeof(head));cnt=0;
}
void add(int a,int b)
{e[cnt].v=b;e[cnt].next=head[a];head[a]=cnt++;
}
int MIN(int a,int b)
{if(a<b) return a;return b;
}
void tarjan(int u)
{dfn[u]=low[u]=index++; instack[u]=1;s.push(u);for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(!dfn[v]){tarjan(v);low[u]=MIN(low[u],low[v]);}else if(instack[v]){low[u]=MIN(low[u],dfn[v]);}}if(dfn[u]==low[u]){int k=s.top();while(k!=u){s.pop();paint[k]=col;instack[k]=0;k=s.top();}s.pop();paint[u]=col;instack[u]=0;col++;}
}
int abss(int x)
{if(x>0) return x;return -x;
}
inline int dis(node a,node b)
{return abss(a.x-b.x)+abss(a.y-b.y);
}
void Input()
{scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);downlimit=inf;for(int i=1;i<=N;i++){scanf("%d%d",&Dian[i].x,&Dian[i].y);s_1[i]=dis(Dian[i],s1);s_2[i]=dis(Dian[i],s2);if(downlimit>s_1[i]) downlimit=s_1[i];if(downlimit>s_2[i]) downlimit=s_2[i];}for(int i=1;i<=A;i++){scanf("%d%d",&fuck[i][0],&fuck[i][1]);}for(int i=1;i<=B;i++){scanf("%d%d",&sex[i][0],&sex[i][1]);}
}
bool judge(int limt)
{Init();for(int i=1;i<=A;i++){int a=fuck[i][0],b=fuck[i][1];add(a,b+N);add(b,a+N);add(b+N,a);add(a+N,b);}for(int i=1;i<=B;i++){int a=sex[i][0],b=sex[i][1];add(a,b);add(a+N,b+N);add(b,a);add(b+N,a+N);}int D=dis(s1,s2);for(int i=1;i<N;i++){for(int j=i+1;j<=N;j++){if(limt<s_1[i]+s_1[j]){//不能都选是 add(i,j+N);add(j,i+N);}if(limt<s_2[i]+s_2[j]){//不能都选否 add(i+N,j);add(j+N,i);}if(limt<s_1[i]+D+s_2[j]){//不能同时i选是，j选否 add(i,j);add(j+N,i+N);}if(limt<s_1[j]+D+s_2[i]){//不能同时i选否，j选是 add(i+N,j+N);add(j,i);}}}for(int i=1;i<=2*N;i++){if(!dfn[i]) tarjan(i);}for(int i=1;i<=N;i++){if(paint[i]==paint[i+N]){return false;}}return true;
}
void treatment()
{int low=downlimit,up=8000000;int ans=-1;while(low<=up){int mid=(low+up)/2;if(judge(mid)){ans=mid;up=mid-1;}else low=mid+1;}printf("%d\n",ans);
}
int main()
{while(~scanf("%d%d%d",&N,&A,&B)){Input();treatment();}return 0;
}
这篇关于HDU 1815 Building roads 二分+2-sat充分理解建图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
