View Code
/*2-sat问题 2-SAT问题，通俗的说就是有n对点（2n个点），从每对点中选出一个点，共选出n个点， 而且要满足若干个这样的条件：某两点不能同时被选出。 设一对点为x、~x，如果a被选出则b一定要被选出，就在图中加有向弧(a,b)表示这种关系。 那么如果a,b（a!=b,a!=~b）不能同时被选出，那么加两条有向弧(a,~b),(b,~a)。 这样由图的对称性可以证明，2-SAT有解等价于任取x、~x，x、~x不在一个强联通分量中。 题意就是：平面上，一个圆，圆的边上按顺时针放着n个点。现在要连m条边，比如a，b， 那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只会连接的一条边。 问能不能连接这m条边，使这些边都不相交。 1：每个边看成2个点：分别表示在内部连接和在外部连接，只能选择一个。计作点i和点i' 2：如果两条边i和j必须一个画在内部，一个画在外部（一个简单判断就可以） 那么连边： i->j’, 表示i画内部的话，j只能画外部，即j’ j->i’，同理 i’->j，同理 j’->i，同理 然后就是2-sat算法了，tarjan一下，如果有i和i'同属于一个强联通，返回false，否则就成立 Problem: 3207 User: HEU_daoguang Memory: 2860K Time: 63MS Language: G++ Result: Accepted */ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; #define E 1000500 #define V 2005 int top,cnt,index,n,m,ecnt; bool instack[V]; int stack[V],id[V],dfn[V],low[V],in[V],link[E][2]; int head[V]; struct edge{ int s,t,next; }e[E]; void addedge(int u,int v){ e[ecnt].s=u; e[ecnt].t=v; e[ecnt].next=head[u]; head[u]=ecnt++; } void tarjan(int u){ int v; int tmp; dfn[u]=low[u]=++index; instack[u]=true; stack[++top]=u; for(int k=head[u];k!=-1;k=e[k].next){ v=e[k].t; if(!dfn[v]){ tarjan(v); if(low[v]<low[u]) low[u]=low[v]; } else if(instack[v] && dfn[v]<low[u]){ low[u]=dfn[v]; } } if(dfn[u]==low[u]){ cnt++; do{ tmp=stack[top--]; instack[tmp]=false; id[tmp]=cnt; } while(tmp!=u); } } void build(){ memset(head,-1,sizeof(head)); ecnt=0; for(int i=0;i<m;i++) for(int j=i+1;j<m;j++){ if(link[i][0] < link[j][1] && link[i][0] > link[j][0] && link[i][1] > link[j][1] || link[i][1] < link[j][1] && link[i][1] > link[j][0] && link[i][0] < link[j][0]) { addedge(i,j+m); addedge(j,i+m); addedge(j+m,i); addedge(i+m,j); } } } void solve(){ top=cnt=index=0; memset(dfn,0,sizeof(dfn)); for(int i=0;i<2*m;i++) if(!dfn[i]) tarjan(i); } void judge(){ bool flag=true; for(int i=0;i<m;i++) { if(id[i]==id[i+m]) { flag=false; break; } } if(flag) printf("panda is telling the truth...\n"); else printf("the evil panda is lying again\n"); } int main() { while(cin >> n >> m){ for(int i=0;i<m;i++){ cin >> link[i][0] >> link[i][1]; if(link[i][0]>link[i][1]) swap(link[i][0],link[i][1]); } build(); solve(); judge(); } return 0; }
第一道2-SAT,今天一定要A第二道,加油。