参照报告写得 二分法 + 2sat  贡献n多wa
我写了注释那位看看 问题在那。 无限感激！！！！
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
using namespace std;

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

#define MAXIN 500

int N, A, B;
int sx1, sy1, sx2, sy2;
int xy[MAXIN][2];     //坐标
int dist[MAXIN][2];  //距离 
int Dij;
bool G[MAXIN*2][MAXIN*2];   //邻接图矩阵
bool TG[MAXIN*2][MAXIN*2];  //备份矩阵
bool visited[MAXIN*2];   //访问标志
int  finished[MAXIN*2];  //完成顺序 
int  cid[MAXIN*2];   //强连通分量的id

void fDFS(int i)  //2sat第一遍的  DFS
{
	static int index = 0;	
	visited[i] = true; 
    int k;
	for(k = 0; k < 2*N; k ++)
	{
		if(G[i][k] && !visited[k])
              fDFS(k);
	}
	finished[index++] = i; //储存完成顺序
}
void bDFS(int i, int id)  //第二遍的 DFS
{
	visited[i] = false; 
	cid[i] = id;  //标记强连通分量id
	int k;
	for(k = 0; k < 2*N; k ++)
	{
		if(G[k][i] && visited[k]) //搜索G的转置图
              bDFS(k, id); 
	}	
}
bool check()  //2sat 判断
{ 
    int i;
 	for(i = 0; i < 2*N; i ++)
		if(!visited[i])
	        fDFS(i);

	int id = 0;
	for(i = 2*N - 1; i >= 0; i --)
		if(visited[finished[i]])
		   bDFS(finished[i], id ++);

	for(i = 0; i < N; i ++)
	{
		if(cid[2*i] == cid[2*i + 1])  //cid[2*i]表示Xi标记 cid[2*i + 1]表示~Xi的标记
			return false;
	}
	return  true;
}
bool checkdist(int mid)
{
    int i, j;
	for(i = 0; i < N; i ++)
		for(j = i + 1; j < N; j ++)
		{	
			if(dist[i][0] + dist[j][0] > mid)  //D1i + D1j 〉S，就增加和取范式（~Xi + ~Xj） 
			{ 
				G[2*i][2*j + 1] = 1;
				G[2*j][2*i + 1] = 1;
			}
			if(dist[i][1] + dist[j][1] > mid) //D2i + D2j 〉S，就增加和取范式（Xi + Xj）
			{
				G[2*i + 1][2*j] = 1;
				G[2*j + 1][2*i] = 1;
			}
			if(dist[i][0] + Dij + dist[j][1] > mid) //D1i + D2j + DD 〉S，就增加和取范式（~Xi + Xj）
			{
				G[2*i][2*j] = 1;
				G[2*j + 1][2*i + 1] = 1;
			}
			if(dist[i][1] + Dij + dist[j][0] > mid) //D2i + D1j + DD 〉S，就增加和取范式（Xi + ~Xj）
			{
				G[2*i + 1][2*j + 1] = 1;
				G[2*j][2*i] = 1;
			}
		}
	return check();
}
void main()
{
    memset(G, false, 1000*1000);
	memset(visited, false, 1000);

	scanf("%d %d %d", &N, &A, &B);
	scanf("%d %d %d %d", &sx1, &sy1, &sx2, &sy2);

	int i, j;
	for(i = 0; i < N; i ++)
	{
		scanf("%d %d", &xy[i][0], &xy[i][1]);
	}

	int t1, t2;
	for(i = 0; i < A; i ++)
	{
        scanf("%d %d", &t1, &t2);
		t1 --;
		t2 --; //下标0开始
		G[t1*2 + 1][t2*2] = G[t2*2][t1*2 + 1] = 1;  
		G[t2*2 + 1][t1*2] = G[t1*2][t2*2 + 1] = 1;  
		//增加和取范式(Xi + Xj)(~Xi + ~Xj)。
	}
	for(i = 0; i < B; i ++)
	{
        scanf("%d %d", &t1, &t2);
		t1 --;
		t2 --;
		G[t1*2 + 1][t2*2 + 1] = G[t2*2 + 1][t1*2 + 1] = 1;
		G[t2*2][t1*2] = G[t1*2][t2*2] = 1; 
        //增加和取范式(Xi + ~Xj)(~Xi + Xj)。 
	}		  

    if(!check())  //检测存在解不
       printf("-1\n");
	else
	{	
		for(i = 0; i < 2*N; i ++)
		  for(j = 0; j < 2*N; j ++)
			TG[i][j] = G[i][j];	  //备份G

		Dij = abs(sx1 - sx2) + abs(sy1 - sy2);

		int max1 = 0, max2 = 0;
	 	for(i = 0; i < N; i ++)
		{
			dist[i][0] = abs(xy[i][0] - sx1) + abs(xy[i][1] - sy1);
			dist[i][1] = abs(xy[i][0] - sx2) + abs(xy[i][1] - sy2);
			max1 = max(dist[i][0], max1);
			max2 = max(dist[i][1], max2);
		}		
	    int high = max(max1 + max2 + Dij, max1*2);
		high = max(high, max2*2);  //可能的最大的距离
		int low = 0;
		int mid;
		while(high != low)
		{
            mid = (high + low)/2;

			if(checkdist(mid))
				high = mid;
			else
				low = mid + 1;
		    for(i = 0; i < 2*N; i ++)
		      for(j = 0; j < 2*N; j ++)
			     G[i][j] = TG[i][j]; //恢复G			 
		}
		printf("%d\n", high);
	}
}

• 找到错误了，终于变成了 TLE (1005) xiaxia 2006-02-16 12:01:49
  • 同TLE >____< (0) RoBa 2006-04-04 18:24:22
    • 用G++就过了,ft (0) RoBa 2006-04-04 21:03:32
      • buggy code, hehe (0) frkstyc 2006-04-04 21:38:22
      • 后来用临接图那样就过了，早知道换g++ (0) first 2006-04-04 21:44:19