題意：平面上，一個圓，圓的邊上按順時針放著n個點。現(xiàn)在要連m條邊，比如a，b，那么a到b可以從圓的內(nèi)部連接，也可以從圓的外部連接。給你的信息中，每個點最多只會連接的一條邊。問能不能連接這m條邊，使這些邊都不相交。 題意可能剛開始不是很好理解，比如1 5連邊，2，6連邊，由于點是順序排列的，一畫圖就可以發(fā)現(xiàn)，這兩條邊必須一個從圓外面連，一個從內(nèi)部連，否則就會相交。如果再加入3 7這條邊，那么就必須相交了。 這樣，就可以轉(zhuǎn)化成標準的2-SAT問題： 1：每個邊看成2個點：分別表示在內(nèi)部連接和在外部連接，只能選擇一個。計作點i和點i' 2：如果兩條邊i和j必須一個畫在內(nèi)部，一個畫在外部（一個簡單判斷就可以） 那么連邊： i->j’, 表示i畫內(nèi)部的話，j只能畫外部，即j’ j->i’，同理 i’->j，同理 j’->i，同理 然后就是2-sat算法了，tarjan一下，如果有i和i'同屬于一個強聯(lián)通，返回false，否則就成立。 ? #include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int MAXN = 1005; const int MAXM = MAXN * MAXN; struct links{int u, v; }l[MAXN]; struct node{int u, v;int next; }arc[MAXM]; int cnt, head[MAXN]; void init(){cnt = 0;mem(head, -1);return ; } void add(int u, int v){arc[cnt].u = u;arc[cnt].v = v;arc[cnt].next = head[u];head[u] = cnt ++; } /* ------------------------------ Tarjan ------------------------- */ int scc_num, scc[MAXN]; int scc_acount[MAXN]; int dfn[MAXN], low[MAXN], id; stack st; bool vis[MAXN], instack[MAXN]; void dfs(int u){vis[u] = instack[u] = 1;st.push(u);dfn[u] = low[u] = ++ id;for (int i = head[u]; i != -1; i = arc[i].next){int v = arc[i].v;if (!vis[v]){dfs(v);low[u] = min(low[u], low[v]);}else if (instack[v]){low[u] = min(low[u], dfn[v]);}}if (low[u] == dfn[u]){++ scc_num;while(st.top() != u){scc[st.top()] = scc_num;scc_acount[scc_num] ++;instack[st.top()] = 0;st.pop();}scc_acount[scc_num] ++;scc[st.top()] = scc_num;st.pop();}return ; } void tarjan(int n){mem(scc_acount, 0);mem(vis, 0);mem(instack, 0);mem(dfn, 0);mem(low, 0);mem(scc, 0);id = scc_num = 0;while(!st.empty())st.pop();for (int i = 1; i <= n; i ++){ //枚舉節(jié)點if (!vis[i])dfs(i);}return ; } /* ------------------------------ Tarjan ------------------------- *//* ------------------------------ 2-SAT -------------------------- */ void add_clause(int m){ //根據(jù)條件加邊,不同題目具體分析init();for (int i = 1; i <= m; i ++){for (int j = i+1; j <= m; j ++){if ((l[i].u < l[j].u && l[i].v < l[j].v && l[j].u < l[i].v)|| l[i].u > l[j].u && l[i].v > l[j].v && l[i].u < l[j].v){//如果i,j矛盾，則選i必須選j'; 選i'必須選j;……//i+m表示i'; j+m表示j'add(i, j + m);add(i + m, j);add(j, i + m);add(j + m, i);}}}return ; } bool check(int m){ //2-SAT無解判定。m為2-SAT節(jié)點數(shù)tarjan(2*m);for (int i = 1; i <= m; i ++){if (scc[i] == scc[i+m]){return false;}}return true; } /* ------------------------------ 2-SAT -------------------------- */int main(){int n, m;scanf("%d %d", &n, &m);for (int i = 1; i <= m; i ++){scanf("%d %d", &l[i].u, &l[i].v);if (l[i].u > l[i].v) swap(l[i].u, l[i].v);}add_clause(m);if (check(m)){puts("panda is telling the truth...");}else{puts("the evil panda is lying again");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AbandonZHANG/archive/2013/06/06/4114030.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3207 Ikki's Story IV - Panda's Trick (POJ 六道2-SAT之一)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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