HDU 1815 Building roads

二分答案 + 2-SAT验证

POJ 稳过，HDU C++ 超时，G++ 550ms左右AC

#include
#include
#include
#include
#include
#include
using namespace std;const int maxn=1000+10;
int N,A,B;
int left,right,mid;
int s1x,s1y,s2x,s2y;
struct point
{int x,y;int p_s1;int p_s2;
}p[maxn];
int Hx[maxn],Hy[maxn];
int Lx[maxn],Ly[maxn];stack<int>S;
vector<int>G[maxn];
vector<int>FG[maxn];
int Belong[maxn];
int flag[maxn];
int Block;int dis1,dis2,dis3;void init()
{for(int i=0;i) G[i].clear();for(int i=0;i) FG[i].clear();memset(Belong,0,sizeof Belong);memset(flag,0,sizeof flag);while(!S.empty()) S.pop();Block=0;
}void addEgde(int x,int y)
{G[x].push_back(y);FG[y].push_back(x);
}int Dis(int x1,int y1,int x2,int y2)
{return abs(x1-x2)+abs(y1-y2);
}void read()
{scanf("%d%d%d%d",&s1x,&s1y,&s2x,&s2y);for(int i=0;i)scanf("%d%d",&p[i].x,&p[i].y);for(int i=1;i<=A;i++){scanf("%d%d",&Hx[i],&Hy[i]);Hx[i]--;Hy[i]--;}for(int i=1;i<=B;i++){scanf("%d%d",&Lx[i],&Ly[i]);Lx[i]--;Ly[i]--;}
}void dfs1(int now)
{flag[now]=1;for(int i=0;i)if(!flag[G[now][i]])dfs1(G[now][i]);S.push(now);
}void dfs2(int now)
{Belong[now]=Block;for(int i=0;i)if(!Belong[FG[now][i]])dfs2(FG[now][i]);
}bool judge()
{for(int i=0;i<2*N;i++) if(!flag[i]) dfs1(i);while(!S.empty()){int Top=S.top(); S.pop();if(!Belong[Top]){Block++;dfs2(Top);}}for(int i=0;i)if(Belong[2*i]==Belong[2*i+1])return 0;return 1;
}void solve()
{left=0;right=8000000;int ans=-1;while(left<=right){mid=(left+right)/2;init();for(int i=0;i){for(int j=i+1;j){int pi_s1=p[i].p_s1;int pi_s2=p[i].p_s2;int pj_s1=p[j].p_s1;int pj_s2=p[j].p_s2;int s1_s2=Dis(s1x,s1y,s2x,s2y);if(pi_s1+pj_s1>mid) {addEgde(2*i,2*j+1);addEgde(2*j,2*i+1);}if(pi_s2+pj_s2>mid) {addEgde(2*i+1,2*j);addEgde(2*j+1,2*i);}if(pi_s1+s1_s2+pj_s2>mid) {addEgde(2*i,2*j);addEgde(2*j+1,2*i+1);}if(pi_s2+s1_s2+pj_s1>mid) {addEgde(2*i+1,2*j+1);addEgde(2*j,2*i);}}}for(int i=1;i<=A;i++){addEgde(2*Hx[i],2*Hy[i]+1);addEgde(2*Hy[i]+1,2*Hx[i]);addEgde(2*Hx[i]+1,2*Hy[i]);addEgde(2*Hy[i],2*Hx[i]+1);}for(int i=1;i<=B;i++){addEgde(2*Lx[i],2*Ly[i]);addEgde(2*Ly[i],2*Lx[i]);addEgde(2*Lx[i]+1,2*Ly[i]+1);addEgde(2*Ly[i]+1,2*Lx[i]+1);}if(judge()) ans=mid,right=mid-1;else left=mid+1;}printf("%d\n",ans);
}
int main()
{while(~scanf("%d%d%d",&N,&A,&B)) {read();for(int i=0;i){p[i].p_s1=Dis(p[i].x,p[i].y,s1x,s1y);p[i].p_s2=Dis(p[i].x,p[i].y,s2x,s2y);}solve();}return 0;
}

转载于:https://www.cnblogs.com/zufezzt/p/4914231.html

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