題意：
? ? ? 給你兩個(gè)總部，s1 ,s2,和n個(gè)點(diǎn)，任意兩點(diǎn)之間都是通過(guò)這個(gè)總部相連的，其中有一些點(diǎn)不能連在同一個(gè)總部上，有一些點(diǎn)可以連接在同一個(gè)總部上，總部和總部之間可以直接連接，就是假如a,b相連，可以使這樣四中情況中的一種
a-s1 ?s1 - b
a-s2 ?s2 - b
a-s1 ?s1 - s2 ?s2 - b
a-s2 ?s2 - s1 ?s1 - b
最后問(wèn)你任意ab距離最遠(yuǎn)的最近是多少。


思路：
? ? ? 首先這個(gè)題目的總部有兩個(gè)，還有一些限制關(guān)系，那么很容易就想到2sat問(wèn)題，關(guān)鍵是怎么建邊，怎樣找到限制關(guān)系，還是舉例子說(shuō)容易懂，
s_x1[i] : 表示i點(diǎn)到S1的距離。
s_x2[i] : 表示i點(diǎn)到S2的距離。
D 表示S1,S2的距離。

彼此厭惡 x -> ~y ,y -> ~x ,~y -> x ,~x -> y
彼此喜歡 x -> y ,~x -> ~y ,y -> x ,~y -> ~x

s_x1[x] + s_x1[y] > mid ? ? ? ? ?x -> ~y ,y -> ~x

s_x2[x] + s_x2[y] > mid ? ? ? ? ?~x -> y ,~y -> x
s_x1[x] + s_x2[y] + D > mid ? ? ?x -> y ,~y -> ~x
s_x2[x] + s_x1[y] + D > mid ? ? ?~x -> ~y ,y -> x

每次二分就這么建邊就ok了，還有提示下，之前在網(wǎng)上看到有個(gè)人的題解是直接先跑了便彼此厭惡和喜歡的，然后二分的時(shí)候就不管那個(gè)了，那個(gè)我感覺(jué)正確性說(shuō)不通，我是每次都全部從新建邊的，上面的如果寫(xiě)錯(cuò)了請(qǐng)大家留言指教，互相學(xué)習(xí)。

#include<stdio.h> #include<string.h> #include<stack>#define N_node 1000 + 10 #define N_edge 5000000 + 300 using namespace std;typedef struct {int to ,next; }STAR;typedef struct {int x ,y; }NODE;STAR E1[N_edge] ,E2[N_edge]; NODE S1 ,S2 ,A; int s_x1[550] ,s_x2[550]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,cnt; int mark[N_node]; int F[1100][2] ,NF[1100][2]; stack<int>st;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot; }void DFS1(int s) {mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next)if(!mark[E1[k].to]) DFS1(E1[k].to);st.push(s); }void DFS2(int s) {mark[s] = 1;Belong[s] = cnt;for(int k = list2[s] ;k ;k = E2[k].next)if(!mark[E2[k].to]) DFS2(E2[k].to); }int abss(int x) {return x > 0 ? x : -x; }int dis(NODE a ,NODE b) {return abss(a.x - b.x) + abss(a.y - b.y); }bool ok(int mid ,int n ,int m ,int q) {memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;for(int i = 1 ;i <= m ;i ++){int x = NF[i][0] * 2 ,xx = NF[i][0] * 2 + 1;int y = NF[i][1] * 2 ,yy = NF[i][1] * 2 + 1;add(x ,yy) ,add(y ,xx);add(yy ,x) ,add(xx ,y);}for(int i = 1 ;i <= q ;i ++){int x = F[i][0] * 2 ,xx = F[i][0] * 2 + 1;int y = F[i][1] * 2 ,yy = F[i][1] * 2 + 1;add(x ,y) ,add(xx ,yy);add(y ,x) ,add(yy ,xx);}int D = dis(S1 ,S2);for(int i = 0 ;i < n ;i ++)for(int j = i + 1 ;j < n ;j ++){int x = i * 2 ,xx = i * 2 + 1;int y = j * 2 ,yy = j * 2 + 1;if(s_x1[i] + s_x1[j] > mid) add(x ,yy) ,add(y ,xx);if(s_x2[i] + s_x2[j] > mid) add(xx ,y) ,add(yy ,x);if(s_x1[i] + s_x2[j] + D > mid) add(x ,y) ,add(yy ,xx);if(s_x2[i] + s_x1[j] + D > mid) add(xx ,yy) ,add(y ,x);}memset(mark ,0 ,sizeof(mark));while(!st.empty()) st.pop();for(int i = 0 ;i < n * 2 ;i ++)if(!mark[i]) DFS1(i);memset(mark ,0 ,sizeof(mark));cnt = 0;while(!st.empty()){int xin = st.top();st.pop();if(mark[xin]) continue;++ cnt;DFS2(xin);}int mk = 0;for(int i = 0 ;i < n * 2 && !mk;i += 2)if(Belong[i] == Belong[i^1]) mk = 1;return !mk; }int main () {int n ,m ,q;int i ,low ,mid ,up;while(~scanf("%d %d %d" ,&n ,&m ,&q)){scanf("%d %d %d %d" ,&S1.x ,&S1.y ,&S2.x ,&S2.y);low = up = 8000000;for(i = 0 ;i < n ;i ++){scanf("%d %d" ,&A.x ,&A.y);s_x1[i] = dis(A ,S1);s_x2[i] = dis(A ,S2);if(low > s_x1[i]) low = s_x1[i];if(low > s_x2[i]) low = s_x2[i];}for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&NF[i][0] ,&NF[i][1]);NF[i][0] -- ,NF[i][1] --;}for(i = 1 ;i <= q ;i ++){scanf("%d %d" ,&F[i][0] ,&F[i][1]);F[i][0] -- ,F[i][1] -- ;}int ans = -1;while(low <= up){mid = (low + up) >> 1;if(ok(mid ,n ,m ,q))ans = mid ,up = mid - 1;else low = mid + 1;}printf("%d\n" ,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu1815 2sat + 二分 + 建图不错的题目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。