2 – SAT
2 – SAT 就是2判定性問題，是一種特殊的邏輯判定問題。
例，n對東西，每對只能選一個（i0或i1），不能不選。即：A or _A = 1 , A xor _A = 1
還存在一些約束關系(i0,j0)，表示i0不能跟j0一起選。那需連邊
i0-> j1 如果選i0的話必須選j1
j0-> i1如果選j0的話必須選i1
表示了一種遞推的關系：選哪個必選哪一個
一般題目給的都是一對一對的東西，二選一，不能不選。本身那幾對東西是沒有關系的，然后題目會定義一些規則，或者我們自己加入條件（如二分的參數），使對與對之間有了一些約束關系： 1)選a必選b a->b
2)a必選 _a->a
對這個新圖求SCC，同一SCC的要么全選，要么都不選。
如果發現a,_a在同一SCC，表明矛盾了。
不矛盾的話，對縮點后的圖按照自底向上選擇一個還未被標記的點，標記選上，然后把它的對立點及其前代都刪除。
（選擇一個點要把它及其所有后代都選上。不選一個點，要把它及其前代都不選。）
算法流程：
1、建圖，求SCC。若某一個點，a與_a在同一個SCC,則無解，退出；
2、對求得的縮點，用原來的反圖建一個DAG；
3、TopoSort得到一個原圖的自底向上的序列，點是縮點后的SCC，沒必要原來的每個點；
4、從左往右，對整個序列的點，如果未標記刪除，就標記選它，同時把這個SCC里的所有原來的點的對立點及其各自的后代（因為是反圖）都標記刪除；
5、重復上面過程，最后被標記選上的SCC內的點都是選擇的點。其個數=n
雖然被刪除的點也是n個，但是他們可能會存在沖突關系。而標記選上的點間是相容的。
挺多用二分的。對于二分設定的參數，可能建圖時要考慮這個條件，如POJ 2749
  /**//*
 POJ 2749 Building roads
題意：給出n個牛棚、兩個特殊點S1,S2的坐標。S1、S2直連。牛棚只能連S1或S2
還有，某些牛棚只能連在同一個S，某些牛棚不能連在同一個S
求使最長的牛棚間距離最小 距離是曼哈頓距離
使最大值最小，二分的經典應用
二分枚舉最大值limit，然后重新構圖，用2-SAT判定可行性
用布爾變量Xi表示第i個牛棚連到S1,~Xi表示連到S2
檢查每一個約束條件，構圖：
1.hate關系的i,j Xi->~Xj ~Xi->Xj Xj->~Xi ~Xj->Xi
2.friend關系的i,j Xi->Xj ~Xi->~Xj Xj->Xi ~Xj->~Xi
接下來的也要檢查，因為引入參數，就是多了約束條件了
這四種情況就是i,j到達對方的所有情況了
3.dist(i,S1)+dist(S1,j)>limit Xi->~Xj Xj->Xi
4.dist(i,S2)+dist(S2,j)>limit ~Xi->Xj ~Xj->Xi
5.dist(i,S1)+dist(S1,S2)+dist(S2,j)>limit Xi->Xj ~Xj->~Xi
5.dist(i,S2)+dist(S2,S1)+dist(S1,j)>limit ~Xi->~Xj Xj->Xi
然后求SCC 判斷Xi與~Xi是否在同一個SCC中，是的話就有矛盾
 */
 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 500;
const int INF = 1000000000;
int N,A,B;
struct Two
 {
int x,y;
};
Two pt[MAXN+10],s1,s2;
Two fre[MAXN*2+10],hate[MAXN*2+10];
struct Graph
{
vector<int>G[2*MAXN+10],_G[2*MAXN+10];
int ID[MAXN*2+10],ord[MAXN*2+10];
int SCC;
void init(int n)
  {
for(int i=1;i<=n;i++)
{
G[i].clear();
_G[i].clear();
 }
}
void add(int a,int b)
{
G[a].push_back(b);
_G[b].push_back(a);
}
void dfs1(int u)
{
ID[u]=1;
for(int i=0,size=_G[u].size();i<size;i++)
{
int v=_G[u][i];
if(!ID[v])dfs1(v);
}
ord[++SCC]=u;
}
void dfs2(int u)
{
ID[u]=SCC;
for(int i=0,size=G[u].size();i<size;i++)
{
int v=G[u][i];
if(!ID[v])dfs2(v);
}
}
void kosaraju()
{
memset(ID,0,sizeof(ID));
SCC=0;
for(int i=1;i<=2*N;i++)
{
if(!ID[i])dfs1(i);
}
memset(ID,0,sizeof(ID));
SCC=0;
for(int i=2*N;i;i--)
{
if(!ID[ord[i]])
{
SCC++;
dfs2(ord[i]);//
}
}
}
}graph;
inline int dist(Two &a,Two &b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}
bool chk(int limit)
{
graph.init(2*N);
//build
for(int i=1;i<N;i++)
for(int j=i+1;j<=N;j++)
{
//dist(i,s1)+dist(j,s1)>L i0->j1 j0->i1
if(dist(pt[i],s1)+dist(pt[j],s1)>limit)
{
graph.add(i,j+N);
graph.add(j,i+N);
}
//dist(i,s2)+dist(j,s2)>L i1->j0 j1->i0
if(dist(pt[i],s2)+dist(pt[j],s2)>limit)
{
graph.add(i+N,j);
graph.add(j+N,i);
}
//dist(i,s1)+dist(s1,s2)+dist(s2,j)>L i0->j0 j1->i1
if(dist(pt[i],s1)+dist(s1,s2)+dist(s2,pt[j])>limit)
{
graph.add(i,j);
graph.add(j+N,i+N);
}
//dist(i,s2)+dist(s2,s1)+dist(s1,j)>L i1->j1 j0->i0
if(dist(pt[i],s2)+dist(s2,s1)+dist(s1,pt[j])>limit)
{
graph.add(i+N,j+N);
graph.add(j,i);
}
}
for(int i=1;i<=A;i++)
{
//i0->j1,i1->j0,j0->i1,j1->i0
graph.add(hate[i].x,hate[i].y+N);
graph.add(hate[i].x+N,hate[i].y);
graph.add(hate[i].y,hate[i].x+N);
graph.add(hate[i].y+N,hate[i].x);
}
for(int i=1;i<=B;i++)
{
//i0->j0,i1->j1,j0->i0,j1->i1
graph.add(fre[i].x,fre[i].y);
graph.add(fre[i].x+N,fre[i].y+N);
graph.add(fre[i].y,fre[i].x);
graph.add(fre[i].y+N,fre[i].x+N);
}
graph.kosaraju();
for(int i=1;i<=N;i++)
{
if(graph.ID[i]==graph.ID[i+N])return false;
}
return true;
}
int main()
{
int Max;
while(~scanf("%d%d%d",&N,&A,&B))
{
scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);
//Max = 0;
for(int i=1;i<=N;i++)
{
scanf("%d%d",&pt[i].x,&pt[i].y);
//Max = max(Max,dist(pt[i],s1));
//Max = max(Max,dist(pt[i],s2));
}
//Max = 2*Max+dist(s1,s2)+1;
for(int i=1;i<=A;i++)
scanf("%d%d",&hate[i].x,&hate[i].y);
for(int i=1;i<=B;i++)
scanf("%d%d",&fre[i].x,&fre[i].y);
int left = 0,right = INF;
while(right-left>1)
{
int mid = (right+left)>>1;
if(chk(mid))right=mid;
else left=mid;
}
if(right==INF)puts("-1");
else printf("%d\n",right);
}
return 0;
}
/**//*
POJ 2723 Get Luffy Out
題意：給出N對鑰匙，一對鑰匙只能用一個 M個門，每個門上2個值，只要有其中一個值的鑰匙即可開門了，問最大能開的門，門得按順序開。
既然是按順序開，就可以二分枚舉能開的門的個數
然后用2-SAT判可行性
建圖方法為，對于門上的兩個值a,b 顯然有_a->b,_b->a
*/
/**//*
POJ 3678 Katu Puzzle
6個邏輯表達式，建圖用
a AND b = 1 <==> _a->a _b->b
a AND b = 0 <==> a->_b b->_a
a OR b = 1 <==> _a->b _b->a
a OR b = 0 <==> a->_a b->_b
a XOR b = 1 <==> _a->b a->_b _b->a b->_a
a XOR b = 0 <==> a->b _a->_b b->a _b->_a
其實記住三個就夠了，另外三個就兩邊取反就可以了
*/
/**//*
POJ 3648 Wedding
題意：n對夫妻，夫妻不能坐在同一排。m種通奸關系，有通奸關系的a，b不能同時坐在新娘的對面一排，求方案
以新娘為參考系，x表示坐在新娘一側，_x表示坐在對面一側
有通奸關系的a,b 有_a->b _b->a
最后！新娘一定要選上，所以連0h->0w 這樣子連，拓撲排序后自底向上肯定會選上新娘
縮點建圖后再拓撲排序
select的過程，遇到沒有標記的塊就選上它，并把它內所有點的對立點及其前代都標記刪除
最后刪除掉的肯定是n個
這里對反圖建圖，所以直接拓撲排序就可以自底向上了
*/
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 1000;
struct Graph
{
vector<int>G[MAXN*2+10],_G[MAXN*2+10];
vector<int>Dag[MAXN*2+10],inDag[MAXN*2+10];
int n,SCC;
int ID[MAXN*2+10],ord[MAXN*2+10];
int in[MAXN*2+10],pos[MAXN*2+10];
int color[MAXN*2+10];
void init(int nn)
{
n=nn;
for(int i=0;i<2*n;i++)
{
G[i].clear();
_G[i].clear();
}
}
void add(int u,int v)
{
G[u].push_back(v);
_G[v].push_back(u);
}
void dfs1(int u)
{
ID[u]=1;
for(int i=0,size=_G[u].size();i<size;i++)
{
int v=_G[u][i];
if(ID[v]==-1)dfs1(v);
}
ord[SCC++]=u;
}
void dfs2(int u)
{
ID[u]=SCC;
for(int i=0,size=G[u].size();i<size;i++)
{
int v=G[u][i];
if(ID[v]==-1)dfs2(v);
}
}
void kosaraju()
{
SCC = 0;
memset(ID,-1,sizeof(ID));
for(int i=0;i<2*n;i++)
if(ID[i]==-1)dfs1(i);
SCC = 0;
memset(ID,-1,sizeof(ID));
for(int i=2*n-1;i>=0;i--)
if(ID[ord[i]]==-1)
{
dfs2(ord[i]);
SCC++;
}
}
bool chk()
{
for(int i=0;i<2*n;i+=2)
if(ID[i]==ID[i+1])return false;
return true;
}
void build_Dag()//對反圖建DAG 這樣topoSort就是自底向上的了
{
for(int i=0;i<SCC;i++)
{
Dag[i].clear();
inDag[i].clear();
}
memset(in,0,sizeof(in));
for(int u=0,v;u<2*n;u++)
{
inDag[ID[u]].push_back(u);
for(int i=0,size=_G[u].size();i<size;i++)
{
v=_G[u][i];
if(ID[u]!=ID[v])
{
Dag[ID[u]].push_back(ID[v]);
++in[ID[v]];
}
}
}
}
void topo_Sort()
{
queue<int>Q;
for(int i=0;i<SCC;i++)
if(in[i]==0)Q.push(i);
int cnt = 0;
while(!Q.empty())
{
int u=Q.front();Q.pop();
pos[cnt++]=u;
for(int i=0,size=Dag[u].size();i<size;i++)
{
int v=Dag[u][i];
if(--in[v]==0)Q.push(v);
}
}
}
void setColor(int u)
{
color[u]=2;
for(int i=0,size=Dag[u].size();i<size;i++)
{
int v=Dag[u][i];
if(color[v]!=2)setColor(v);
}
}
void select()
{
memset(color,0,sizeof(color));
for(int i=0;i<SCC;i++)
{
int u=pos[i];
if(color[u]==0)
{
color[u]=1;//select
for(int j=0,size=inDag[u].size();j<size;j++)//set every _v
{
int v=inDag[u][j]^1;
if(color[ID[v]]==2)continue;
setColor(ID[v]);
}
}
}
}
void solve()
{
build_Dag();
topo_Sort();
select();
for(int i=2;i<2*n;i++)
if(color[ID[i]]==1)printf("%d%c ",i/2,(i&1)?'h':'w');
puts("");
}
}graph;
int main()
{
//freopen("in","r",stdin);
int n,m,a,b;
char ca,cb;
while(scanf("%d%d",&n,&m),n)
{
graph.init(n);
for(int i=0;i<m;i++)
{
scanf("%d%c%d%c",&a,&ca,&b,&cb);
a=a*2+(ca=='h');
b=b*2+(cb=='h');
//_a->b _b->a
graph.add(a^1,b);
graph.add(b^1,a);
}
//0h->0w 0wife一定要選
graph.add(1,0);
graph.kosaraju();
if(!graph.chk())puts("bad luck");
else graph.solve();
}
return 0;
}
還有2道
POJ 3207 把線當成SAT的點
POJ 3683 跟wedding類似
|
|
常用鏈接
隨筆分類
Links
搜索
最新評論
|
|