HDU 1815

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1815

题意：n个点，每个点可以跟S1或者S2相连，两类约束条件，①a，b不能与同一个S相连 ② a,b必须与同一个相连，问满足条件的每两个点之间的距离的最大值 最小是多少

其中，给出的是每个点坐标，先算距离，距离是曼哈顿距离

分析：二分枚举答案，每次重新建图，边分三类

A表示点a连S1，A’表示点a连S2

① a,b不能与同一个S相连,加边A->B',A'->B,B->A',B'->A;

② a,b必须与同一个S相连,加边A->B,A'->B',B->A,B'->A';

③ a连S1，b连S1距离和大于当前枚举的最大距离 ，加边 A->B',B->A';

a连S2，b连S2距离和大于当前枚举的最大距离 ，加边 A'->B,B'->A;

a连S1，b连S2距离和大于当前枚举的最大距离 ，加边 A->B,B'->A';

a连S2，b连S1距离和大于当前枚举的最大距离 ，加边 A'->B',B->A;

*特别注意一下给的约束条件下标从1开始

#include 
#include
#include
#include
#include
#include
#define maxn 505
#include
using namespace std;
int ds1[maxn],ds2[maxn],l;
struct node{int x,y;
}p[maxn],s1,s2;
int dis(node a,node b){return abs(a.x-b.x)+abs(a.y-b.y);
}
struct request{int x,y;
}h[maxn],f[maxn];
struct TwoSAT{int n;vector G[maxn*2];bool mark[maxn*2];int S[maxn*2],c;bool dfs(int x){if(mark[x^1])return false;if(mark[x])return true;mark[x]=true;S[c++]=x;for(int i=0;in=n;for(int i=0;i0)mark[S[--c]]=false;if(!dfs(i+1))return false;}}return true;}
};
int main()
{int n,A,B;while(~scanf("%d%d%d",&n,&A,&B)){scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);for(int i=0;i>1;T.init(n);for(int i=0;im)T.add_clause(i,0,j,0);if(ds2[i]+ds2[j]>m)T.add_clause(i,1,j,1);if(ds1[i]+ds2[j]+l>m)T.add_clause(i,0,j,1);if(ds2[i]+ds1[j]+l>m)T.add_clause(i,1,j,0);}}if(T.solve()){flag=1;R=m;}else {L=m+1;}}if(flag)printf("%d\n",L);elseprintf("-1\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！