2-sat问题
方案可行性O（M）算法：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; struct{ int to,next; }edge[30000100]; //边结点数组 int head[10005],stack[10005],dfn[10005],low[10005],belong[10005]; // head[]头结点数组,stack[]为栈,dfn[]为深搜次序数组，belong[]为每个结点所对应的强连通分量标号数组 // low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号 int instack[10005],cnt,scnt,top,n,tot; // instack[]为是否在栈中的标记数组 void Add(int x,int y){ //构建邻接表 edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot++; } void Tarjan(int v) //Tarjan算法求有向图的强连通分量 { int min,i,t,j; dfn[v]=low[v]=++cnt; //cnt为次序计数器 instack[v]=1; //标记在栈中 stack[top++]=v; //入栈 for(i=head[v];i!=-1;i=edge[i].next){ //枚举v的每一条边 j=edge[i].to; //v所邻接的边 if(!dfn[j]){ //未被访问 Tarjan(j); //继续向下找 if(low[v]>low[j])low[v]=low[j]; // 更新结点v所能到达的最小次数层 }else if(instack[j]&&dfn[j]<low[v]){ //如果j结点在栈内, low[v]=dfn[j]; } } if(dfn[v]==low[v]){ //如果节点v是强连通分量的根 scnt++; //连通分量标号加1 do{ t=stack[--top]; //退栈 instack[t]=0; //标记不在栈中 belong[t]=scnt; //出栈结点t属于cnt标号的强连通分量 }while(t!=v); //直到将v从栈中退出 } } bool Slove(){ int i; scnt=cnt=top=0; //初始化连通分量标号，次序计数器，栈顶指针为0 memset(dfn,0,sizeof(dfn)); //结点搜索的次序编号数组为0，同时可以当是否访问的数组使用 for(i=0;i<2*n;i++) //枚举每个结点，搜索连通分量 if(!dfn[i]) //未被访问 Tarjan(i); //则找i结点的连通分量 for(int i=0;i<n;i++) if(belong[2*i]==belong[2*i+1])//相等表示两个数据在同一个集合之中 return false; return true; } int main(){ int m,i,x,y,c1,c2,a,b,c,d; while(~scanf("%d",&n)) { memset(head,-1,sizeof(head)); //邻接表的头结点数组初始化为-1 memset(stack,0,sizeof(instack)); memset(belong,-1,sizeof(belong)); memset(low,0,sizeof(low)); scanf("%d",&m); tot=0; while(m--){ scanf("%d%d%d%d",&a,&b,&c,&d); Add((a<<1)+c,(b<<1)+1-d); Add((b<<1)+d,(a<<1)+1-c); /*Add(2*a+c,2*b+(1-d)); Add(2*b+d,2*a+(1-c));*/ } //求强连通分量 if(Slove()) //只有一个强连通分量，说明此图各个结点都可达 printf("YES\n"); else printf("NO\n"); } return 0; }
hdu1824
题意多个group，每个group有个队长，两个队员。一个group至少要队长留下或者两个队员同时留下。然后给边表示这两个队员不能同时留下。
(开始一直想怎么让两个队员并到一起呢？看了别人的代码，大悟2-sat的“精髓”，每个点有两个状态，每个队员当一个点来处理，so great。)
#include<iostream> #include<cstdio> #include<cstring> using namespace std; struct{ int to,next; }edge[30000100]; //边结点数组 int head[10005],stack[10005],dfn[10005],low[10005],belong[10005]; // head[]头结点数组,stack[]为栈,dfn[]为深搜次序数组，belong[]为每个结点所对应的强连通分量标号数组 // low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号 int instack[10005],cnt,scnt,top,n,tot; // instack[]为是否在栈中的标记数组 void Add(int x,int y){ //构建邻接表 edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot++; } void Tarjan(int v) //Tarjan算法求有向图的强连通分量 { int min,i,t,j; dfn[v]=low[v]=++cnt; //cnt为次序计数器 instack[v]=1; //标记在栈中 stack[top++]=v; //入栈 for(i=head[v];i!=-1;i=edge[i].next){ //枚举v的每一条边 j=edge[i].to; //v所邻接的边 if(!dfn[j]){ //未被访问 Tarjan(j); //继续向下找 if(low[v]>low[j])low[v]=low[j]; // 更新结点v所能到达的最小次数层 }else if(instack[j]&&dfn[j]<low[v]){ //如果j结点在栈内, low[v]=dfn[j]; } } if(dfn[v]==low[v]){ //如果节点v是强连通分量的根 scnt++; //连通分量标号加1 do{ t=stack[--top]; //退栈 instack[t]=0; //标记不在栈中 belong[t]=scnt; //出栈结点t属于cnt标号的强连通分量 }while(t!=v); //直到将v从栈中退出 } } bool Slove(){ int i; scnt=cnt=top=0; //初始化连通分量标号，次序计数器，栈顶指针为0 memset(dfn,0,sizeof(dfn)); //结点搜索的次序编号数组为0，同时可以当是否访问的数组使用 for(i=0;i<2*n;i++) //枚举每个结点，搜索连通分量 if(!dfn[i]) //未被访问 Tarjan(i); //则找i结点的连通分量 for(int i=0;i<n;i++) if(belong[2*i]==belong[2*i+1])//相等表示两个数据在同一个集合之中 return false; return true; } int z[100001]; int main(){ int m,i,x,y,c1,c2,a,b,c,d; while(~scanf("%d%d",&n,&m)) { memset(head,-1,sizeof(head)); //邻接表的头结点数组初始化为-1 memset(stack,0,sizeof(instack)); memset(belong,-1,sizeof(belong)); memset(low,0,sizeof(low)); tot=0; int id=0; for(int i=0;i<n;i++){ scanf("%d%d%d",&a,&b,&c); Add((a<<1)+1,(b<<1)); Add((a<<1)+1,(c<<1)); Add((b<<1)+1,(a<<1)); Add((c<<1)+1,(a<<1)); } int flag=0; while(m--){ scanf("%d%d",&a,&b); Add((a<<1),(b<<1)+1); Add((b<<1),(a<<1)+1); /*Add(2*a+c,2*b+(1-d)); Add(2*b+d,2*a+(1-c));*/ } if(flag){printf("NO\n");continue;} //求强连通分量 if(Slove()) //只有一个强连通分量，说明此图各个结点都可达 printf("yes\n"); else printf("no\n"); } return 0; }
hdu3622
题意给了n对点，没对任选一个点做炸弹的圆心 每个炸弹之间不能有重叠 求炸弹最大最大半径。
二分+2-sat
在于建图，对于一个radio 判断每个点之间距离，小于2*radio这说明这两个是不能同时存在的。 构好图对于该2-sat的可行性判断。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define eps 1e-6 6 using namespace std; 7 8 9 struct{ 10 int to,next; 11 }edge[30000100]; //边结点数组 12 13 int head[10005],stack[10005],dfn[10005],low[10005],belong[10005]; 14 // head[]头结点数组,stack[]为栈,dfn[]为深搜次序数组，belong[]为每个结点所对应的强连通分量标号数组 15 // low[u]为u结点或者u的子树结点所能追溯到的最早栈中结点的次序号 16 int instack[10005],cnt,scnt,top,n,tot; 17 // instack[]为是否在栈中的标记数组 18 19 void Add(int x,int y){ //构建邻接表 20 edge[tot].to=y; 21 edge[tot].next=head[x]; 22 head[x]=tot++; 23 } 24 25 void Tarjan(int v) //Tarjan算法求有向图的强连通分量 26 { 27 int min,i,t,j; 28 dfn[v]=low[v]=++cnt; //cnt为次序计数器 29 instack[v]=1; //标记在栈中 30 stack[top++]=v; //入栈 31 for(i=head[v];i!=-1;i=edge[i].next){ //枚举v的每一条边 32 j=edge[i].to; //v所邻接的边 33 if(!dfn[j]){ //未被访问 34 Tarjan(j); //继续向下找 35 if(low[v]>low[j])low[v]=low[j]; // 更新结点v所能到达的最小次数层 36 }else if(instack[j]&&dfn[j]<low[v]){ //如果j结点在栈内, 37 low[v]=dfn[j]; 38 } 39 } 40 if(dfn[v]==low[v]){ //如果节点v是强连通分量的根 41 scnt++; //连通分量标号加1 42 do{ 43 t=stack[--top]; //退栈 44 instack[t]=0; //标记不在栈中 45 belong[t]=scnt; //出栈结点t属于cnt标号的强连通分量 46 }while(t!=v); //直到将v从栈中退出 47 } 48 } 49 50 bool Slove(){ 51 int i; 52 scnt=cnt=top=0; //初始化连通分量标号，次序计数器，栈顶指针为0 53 memset(dfn,0,sizeof(dfn)); //结点搜索的次序编号数组为0，同时可以当是否访问的数组使用 54 for(i=0;i<2*n;i++) //枚举每个结点，搜索连通分量 55 if(!dfn[i]) //未被访问 56 Tarjan(i); //则找i结点的连通分量 57 for(int i=0;i<n;i++) 58 if(belong[2*i]==belong[2*i+1])//相等表示两个数据在同一个集合之中 59 return false; 60 return true; 61 } 62 void init(){ 63 memset(head,-1,sizeof(head)); //邻接表的头结点数组初始化为-1 64 memset(stack,0,sizeof(instack)); 65 memset(belong,-1,sizeof(belong)); 66 memset(low,0,sizeof(low)); 67 tot=0; 68 } 69 struct node{ 70 double x; 71 double y; 72 double len(node &a){ 73 return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y)); 74 } 75 void in(){ 76 scanf("%lf%lf",&x,&y); 77 } 78 }P[1000]; 79 int cal(double mid){ 80 init(); 81 // cout<<mid<<" dafsdf"<<endl; 82 for(int i=0;i<(n<<1);i++){ 83 for(int j=i+1;j<(n<<1);j++)if(j!=(i^1)){ 84 if(P[i].len(P[j])<mid){ 85 Add(i,j^1); 86 Add(j,i^1); 87 } 88 } 89 } 90 if(Slove())return 1; 91 return 0; 92 } 93 int main(){ 94 int m,i,x,y,c1,c2,a,b,c,d; 95 while(~scanf("%d",&n)) 96 { 97 for(int i=0;i<n;i++){ 98 P[i<<1].in(); 99 P[(i<<1)+1].in(); 100 } 101 double l=0,r=10001; 102 double mid; 103 while(l<=r){ 104 mid=(l+r)/2.0; 105 if(cal(mid)){ 106 l=mid+eps; 107 } 108 else{ 109 r=mid-eps; 110 } 111 } 112 printf("%.2lf\n",l/2.0); 113 /* 114 while(m--){ 115 scanf("%d%d%d%d",&a,&b,&c,&d); 116 Add((a<<1)+c,(b<<1)+1-d); 117 Add((b<<1)+d,(a<<1)+1-c); 118 Add(2*a+c,2*b+(1-d)); 119 Add(2*b+d,2*a+(1-c)); 120 }*/ 121 //求强连通分量 122 /*if(Slove()) //只有一个强连通分量，说明此图各个结点都可达 123 printf("YES\n"); 124 else 125 printf("NO\n");*/ 126 } 127 return 0; 128 129 }
原文：http://www.cnblogs.com/youyouyou/p/3633347.html
