building roads(二分＋2-sat).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define min(a,b)    (((a) < (b)) ? (a) : (b))

#define NMAX 510*2
#define MMAX 1100

int n,a,b;
struct node {
	int x,y;
}point[NMAX],s[2],hate[MMAX],love[MMAX];

struct node2 {
	int d0,d1;
}dist[NMAX];
int DD;

vector< vector<int> > path;
vector< vector<int> > temp_path;

int scc, step;
int order[NMAX], order_pos, id[NMAX];
int order2[NMAX], order2_pos;
int vis[NMAX];

void dfs(int pos)
{
    int i,next,l,pre;
	
    vis[pos] = step ++;
    order[ order_pos ++ ] = pos;
    order2[ order2_pos ++ ] = pos;
    l = path[pos].size();
    for (i=0;i<l;i++) {
        next = path[pos][i];
        if (vis[next] == 0) {
            dfs(next);
        }
        else if (id[next] == 0) {//have a circle and belong to nothing
            while (vis[ order2[order2_pos -1] ] > vis[next]) {//back to begin of circle
                order2_pos --;
            }
        }
    }//for i
    if (order2[order2_pos -1] == pos) {//if pos back to begin of scc
        order2_pos --;
    }
    else {
        return ;
    }
    do {//record scc
        pre = order[order_pos -1];
        id[pre] = scc;
        order_pos --;
    } while(pre != pos);
    scc ++;
}

bool Gabow()
{
    int i;
    //dfs in original graph
    memset(id, 0, sizeof(id));
    memset(vis, 0, sizeof(vis));
    scc = step = 1;
    order_pos = order2_pos = 0;
    for (i=0; i<2*n ;i++) {
        if (vis[i] == 0) {
            dfs(i);
        }
    }
    //statist
    scc --;
	for (i=0;i<2*n;i+=2) {
		if (id[i] == id[i+1]) {
			return false;
		}
	}
	return true;
}

bool check(int s)
{
	int i,j;
	for (i=0; i<n ;i++) {
		for (j=i+1; j<n ;j++) {
			if (dist[i].d0 + dist[j].d0 > s) {//D1i + D1j > S，add（~Xi + ~Xj）
				path[2*i].push_back(2*j +1);
				path[2*j].push_back(2*i +1);
			}
			if (dist[i].d1 + dist[j].d1 > s) {//D2i + D2j > S，add（Xi + Xj）
				path[2*i +1].push_back(2*j);
				path[2*j +1].push_back(2*i);
			}
			if (dist[i].d0 + DD + dist[j].d1 > s) {//D1i + D2j + DD > S，add（~Xi + Xj）
				path[2*i].push_back(2*j);
				path[2*j +1].push_back(2*i +1);
			}
			if (dist[i].d1 + DD + dist[j].d0 > s) {//D2i + D1j + DD > S，add（Xi + ~Xj）
				path[2*i +1].push_back(2*j +1);
				path[2*j].push_back(2*i);
			}
		}//for j
	}//for i
	return Gabow();
}

void build_original_path() 
{
	int i;
	//2*x : x -> s0
	//2*x+1 : x -> s1
	for (i=0;i<a;i++) {//(Xi + Xj)(~Xi + ~Xj)
		int x = hate[i].x;
		int y = hate[i].y;
		path[2*x].push_back(2*y +1);
		path[2*y].push_back(2*x +1);
		path[2*x +1].push_back(2*y);
		path[2*y +1].push_back(2*x);
	}
	for (i=0;i<b;i++) {//(Xi + ~Xj)(~Xi + Xj)		
		int x = love[i].x;
		int y = love[i].y;
		path[2*x].push_back(2*y);
		path[2*y].push_back(2*x);
		path[2*x +1].push_back(2*y +1);
		path[2*y +1].push_back(2*x +1);
	}
}

int main()
{
	int i;
	while (scanf("%d %d %d",&n,&a,&b)==3) {
		scanf("%d %d %d %d",&s[0].x,&s[0].y,&s[1].x,&s[1].y);
		for (i=0;i<n;i++) {
			scanf("%d %d",&point[i].x, &point[i].y);
		}
		for (i=0;i<a;i++) {
			scanf("%d %d",&hate[i].x, &hate[i].y);
			hate[i].x --;	hate[i].y --;
		}
		for (i=0;i<b;i++) {
			scanf("%d %d",&love[i].x, &love[i].y);
			love[i].x --;	love[i].y --;
		}//read data
		path.resize(2*n+10);
		for (i=0;i<=2*n;i++) {
			path[i].clear();
		}
		build_original_path();
		temp_path = path;
		if ( !Gabow() ) {
			puts("-1");
		}
		else {//binary enum dist
			DD = abs(s[0].x - s[1].x) + abs(s[0].y - s[1].y);
			int max1, max0, min1, min0;
			max1 = max0 = INT_MIN;
			min1 = min0 = INT_MAX;
			for (i=0;i<n;i++) {
				dist[i].d0 = abs(point[i].x - s[0].x) + abs(point[i].y - s[0].y);
				dist[i].d1 = abs(point[i].x - s[1].x) + abs(point[i].y - s[1].y);
				max0 = max(max0, dist[i].d0);
				max1 = max(max1, dist[i].d1);
				min0 = min(min0, dist[i].d0);
				min1 = min(min1, dist[i].d1);
			}
			int right, left, mid;
			right = max(max0+max1+DD, max0*2);
			right = max(right, max1*2);
			left = min0 + min1;
			while (right > left) {
				path = temp_path;
				mid = (right + left) / 2;
				if ( check(mid) ) {
					right = mid;
				}
				else {
					left = mid +1;
				}
			}//binary search
			printf("%d\n", right);
		}
	}
}