Poj 2749 & Hdu 1815 Building roads (2-SAT + 二分建图)

╰半橙微兮° 2022-08-11 19:58 6阅读 0赞

以下分析摘自：http://www.cnblogs.com/wally/p/3251968.html

题意：给出n个牛棚、两个特殊点S1,S2的坐标。S1、S2直连。牛棚只能连S1或S2，还有，某些牛棚只能连在同一个S，某些牛棚不能连在同一个S。求使最长的牛棚间距离最小 距离是曼哈顿距离，使最大值最小。

思路：二分的经典应用，利用二分将最值问题转化为判定性问题，二分枚举最大值limit，然后重新构图，用2-SAT判定可行性。

用Xi表示第i个牛棚连到S1,~Xi表示连到S2，检查每一个约束条件，构图：

1.hate关系的i,j Xi->~Xj ~Xi->Xj Xj->~Xi ~Xj->Xi

2.friend关系的i,j Xi->Xj ~Xi->~Xj Xj->Xi ~Xj->~Xi

接下来的也要检查，因为引入参数，就是多了约束条件了

这四种情况就是i,j到达对方的所有情况了

3.dist(i,S1)+dist(S1,j)>limit Xi->~Xj Xj->Xi

4.dist(i,S2)+dist(S2,j)>limit ~Xi->Xj ~Xj->Xi

5.dist(i,S1)+dist(S1,S2)+dist(S2,j)>limit Xi->Xj ~Xj->~Xi

5.dist(i,S2)+dist(S2,S1)+dist(S1,j)>limit ~Xi->~Xj Xj->Xi

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int MAXN = 1005;
    const int VN   = MAXN*2;
    const int EN   = 1200000;
    int n,m;
    
    struct Edge{
    	int v, next;
    };
    
    class Graph{
    public:
    	int head[VN],size;
    	Edge E[EN];
    	void init(){
    		size = 0;
    		memset(head, -1, sizeof(head));
    	}
    	void Add (int u,int v){
    		E[size].v = v;
    		E[size].next = head[u];
    		head[u] = size++;
    	}
    }g;
    
    class Two_Sat{
    public:
    	bool Check(const Graph&g, const int n){
    		SCC(g,n);//传入几对点
    		for (int i=0;i<n;i++)
    			if (belong[i*2] == belong[i*2+1])
    				return false;
    		return true;
    	}
    private:
    	int top, bcnt, idx;
    	int sta[VN],belong[VN];
    	int dfn[VN],low[VN];
    	bool inStack[VN];
    	
    	void targan (const Graph&g, const int u){
    		int v;
    		dfn[u] = low[u] = ++idx;
    		sta[top++] = u;
    		inStack[u] = true;
    		
    		for (int i=g.head[u]; i!=-1; i=g.E[i].next){
    			v = g.E[i].v;
    			if (dfn[v] < 0){
    				targan(g, v);
    				low[u] = min(low[u], low[v]);
    			}
    			else if(inStack[v])
    				low[u] = min(low[u], dfn[v]);
    		}
    		
    		if (dfn[u] == low[u]){
    			++bcnt;
    			do{
    				v = sta[--top];
    				inStack[v] = false;
    				belong[v] = bcnt;
    			}while(u != v);
    		}
    	}
    
    	void SCC (const Graph&g, int n){
    		top=bcnt=idx=0;
    		memset(dfn,-1,sizeof(dfn));
    		memset(low,0,sizeof(low));
    		memset(belong,0,sizeof(belong));
    		memset(inStack,false,sizeof(inStack));
    		for (int i=0; i<2*n;i++)
    			if (dfn[i] < 0) targan(g,i);
    	}
    }sat;
    
    int hateNum, likeNum;
    int d[VN], sLen;
    
    struct Node
    {
        int x, y;
    }loc[VN],hate[VN],like[VN],s1,s2;
    
    int Dis (const Node& a, const Node& b)
    {
    	return abs(a.x-b.x)+abs(a.y-b.y);
    }
    
    void buildGraph (int maxLen)
    {
    	int u,v,i;
    	g.init ();
    	for (i=0;i<n;i++)
    		for (int j=i+1;j<n;j++)
    		{
    			u=i*2,v=j*2;
    			int l1=d[u],l2=d[u^1];
    			int r1=d[v],r2=d[v^1];
    			if (l1+r1 > maxLen)
    				g.Add(u,u^1),g.Add(v,v^1);
    			if (l1+r2+sLen > maxLen)
    				g.Add(u,v),g.Add(v^1,u^1);
    			if (l2+r1+sLen > maxLen)
    				g.Add(u^1,v^1),g.Add(v,u);
    			if (l2+r2 > maxLen)
    				g.Add(u^1,v),g.Add(v^1,u);
    		}
    
    	for (i=0;i<hateNum;i++)
    	{
    		u=hate[i].x*2;
    		v=hate[i].y*2;
    		g.Add(u,v^1);
    		g.Add(v^1,u);
    		g.Add(v,u^1);
    		g.Add(u^1,v);
    	}
    	for (i=0;i<likeNum;i++)
    	{
    		u=like[i].x*2;
    		v=like[i].y*2;
    		g.Add(u,v);
    		g.Add(v^1,u^1);
    		g.Add(v,u);
    		g.Add(u^1,v^1);
    	}
    }
    
    void Input ()
    {
    	int i;
    	scanf("%d%d%d%d", &s1.x,&s1.y,&s2.x,&s2.y);
    	sLen = Dis(s1, s2);
    	for (i=0;i<n;i++)
    	{
    		scanf("%d%d", &loc[i].x, &loc[i].y);
    		d[i*2] = Dis(loc[i], s1);
    		d[i*2+1] = Dis(loc[i], s2);
    	}
    	for (i=0;i<hateNum;i++)
    	{
    		scanf("%d%d", &hate[i].x, &hate[i].y);
    		hate[i].x--;
    		hate[i].y--;
    	}
    	for (i=0;i<likeNum;i++)
    	{
    		scanf("%d%d", &like[i].x, &like[i].y);
    		like[i].x--;
    		like[i].y--;
    	}
    }
    
    int main ()
    {
    	while (~scanf("%d%d%d",&n,&hateNum,&likeNum))
    	{
    		Input ();
    		int low=0,high=8000000,mid,ans=-1;
    		while (low<=high)
    		{
    			mid=(low+high)>>1;
    			buildGraph(mid);
    			if (sat.Check(g,n))
    				ans=mid,high=mid-1;
    			else
    				low=mid+1;
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }