2-Sat问题
2024-04-19 23:18:44
二分+2-Sat
判断是否可行
输出字典序最小的解
输出字典序可行解
其实这些都是小问题，最重要的是建图，请看论文。
特殊的建边方式，如果a b是一对，a必须选，那么就是b->a建边。
模板题
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define LL long long
struct node
{
int u,v,next;
}edge[*];
int t,scnt,top;
int first[];
int DFN[];
int Low[];
int Belong[];
int in[],stack[];
void CL()
{
t = top = scnt = ;
memset(first,-,sizeof(first));
memset(DFN,,sizeof(DFN));
}
void add(int u,int v)
{
edge[t].u = u;
edge[t].v = v;
edge[t].next = first[u];
first[u] = t ++;
}
void Tarjan(int u)
{
int v,i;
DFN[u] = Low[u] = ++ t;
in[u] = ;
stack[top++] = u;
for(i = first[u];i != -;i = edge[i].next)
{
v = edge[i].v;
if(!DFN[v])
{
Tarjan(v);
if(Low[u] > Low[v])
{
Low[u] = Low[v];
}
}
else if(in[v] && Low[u] > DFN[v])
{
Low[u] = DFN[v];
}
}
if(DFN[u] == Low[u])
{
scnt ++;
do
{
v = stack[--top];
in[v] = ;
Belong[v] = scnt;
}while(u != v);
}
}
int main()
{
int n,m,a1,a2,c1,c2,i,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
CL();
for(i = ;i < m;i ++)
{
scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
u = a1*+c1;
v = a2*+c2;
add(u,v^);
add(v,u^);
}
for(i = ;i < *n;i ++)
{
if(!DFN[i])
{
Tarjan(i);
}
}
for(i = ;i < n;i ++)
{
if(Belong[*i] == Belong[*i+])
break;
}
if(i == n)
printf("YES\n");
else
printf("NO\n");
} return ;
}
论文上的例题，输出字典序。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define LL long long
#define N 8001
int que[*N];
int flag[*N];
int first[*N];
int t,n,num;
struct node
{
int u,v,next;
}edge[];
void CL()
{
t = ;
memset(first,-,sizeof(first));
memset(flag,,sizeof(flag));
}
void add(int u,int v)
{
edge[t].u = u;
edge[t].v = v;
edge[t].next = first[u];
first[u] = t ++;
}
int dfs(int x)
{
int i,v;
if(flag[x] == )
return ;
else if(flag[x] == )
return ;
flag[x] = ;
flag[x^] = ;
que[num++] = x;
for(i = first[x];i != -;i = edge[i].next)
{
v = edge[i].v;
if(!dfs(v)) return ;
}
return ;
}
int judge()
{
int i,j;
for(i = ;i < *n;i ++)
{
if(flag[i]) continue;
num = ;
if(!dfs(i))
{
for(j = ;j < num;j ++)
{
flag[que[j]] = ;
flag[que[j]^] = ;
}
if(!dfs(i^))
return ;
}
}
return ;
}
int main()
{
int m,u,v,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
CL();
for(i = ;i < m;i ++)
{
scanf("%d%d",&u,&v);
u --;
v --;
add(u,v^);
add(v,u^);
}
if(judge())
{
for(i = ;i < *n;i ++)
{
if(flag[i] == ) printf("%d\n",i+);
}
}
else
{
printf("NIE\n");
}
}
return ;
}
输出可行解。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
struct node
{
int u,v,next;
}edge[],g[];
int t,scnt,top,T;
int first[];
int DFN[];
int op[];
int Low[];
int Belong[];
int in[],stack[];
int input[];
int flag[];
void CL()
{
T = t = top = scnt = ;
memset(first,-,sizeof(first));
memset(DFN,,sizeof(DFN));
memset(flag,,sizeof(flag));
}
void add(int u,int v)
{
edge[t].u = u;
edge[t].v = v;
edge[t].next = first[u];
first[u] = t ++;
}
void _add(int u,int v)
{
g[T].u = u;
g[T].v = v;
g[T].next = first[u];
first[u] = T ++;
}
void Tarjan(int u)
{
int v,i;
DFN[u] = Low[u] = ++ t;
in[u] = ;
stack[top++] = u;
for(i = first[u];i != -;i = edge[i].next)
{
v = edge[i].v;
if(!DFN[v])
{
Tarjan(v);
if(Low[u] > Low[v])
{
Low[u] = Low[v];
}
}
else if(in[v] && Low[u] > DFN[v])
{
Low[u] = DFN[v];
}
}
if(DFN[u] == Low[u])
{
scnt ++;
do
{
v = stack[--top];
in[v] = ;
Belong[v] = scnt;
}while(u != v);
}
}
void tpsort()
{
queue<int> que;
memset(first,-,sizeof(first));
int i,v,u;
for(i = ;i < t;i ++)
{
u = Belong[edge[i].u];
v = Belong[edge[i].v];
if(u != v)
{
_add(v,u);
input[u] ++;
}
}
for(i = ;i <= scnt;i ++)
{
if(input[i] == ) que.push(i);
}
while(!que.empty())
{
u = que.front();
que.pop();
if(flag[u] == )
{
flag[u] = ;
flag[op[u]] = ;
}
for(i = first[u];i != -;i = g[i].next)
{
v = g[i].v;
if(--input[v] == ) que.push(v);
}
} }
int main()
{
int n,m,i,u,v;
char s1,s2;
while(scanf("%d%d%*c",&n,&m)!=EOF)
{
if(n == &&m == ) break;
CL();
for(i = ;i < m;i ++)
{
scanf("%d%c%*c%d%c%*c",&u,&s1,&v,&s2);
if(s1 == 'w') u = u*;
else u = u* + ;
if(s2 == 'w') v = v*;
else v = v* + ;
if(u != (v^))
{
add(u,v^);
add(v,u^);
}
}
add(,);
for(i = ;i < *n;i ++)
{
if(!DFN[i])
{
Tarjan(i);
}
}
for(i = ;i < n;i ++)
{
if(Belong[*i] == Belong[*i+])
break;
op[Belong[*i]] = Belong[*i+];
op[Belong[*i+]] = Belong[*i];
}
if(i != n)
{
printf("bad luck\n");
continue;
}
tpsort();
int z = ;
for(i = ; i < *n; i++)
{
if(flag[Belong[i]] == && i != )
{
if(z) printf(" ");
z = ;
printf("%d", i/);
if(i% == )
printf("h");
else
printf("w");
}
}
printf("\n");
}
return ;
}
最新文章
- 【web前端面试题整理05】做几道前端面试题休息休息吧
- C# 图片处理(压缩、剪裁，转换，优化)
- Java Servlet Filter(转)
- Java IO流中的File类学习总结
- log4net使用（包括单个文件和按日期生成多个文件）
- google浏览器翻译失败解决方案
- 让C#、VB.NET实现复杂的二进制操作
- NoSQL数据库种类
- zookeeper client API实现(python kazoo 的实现)
- ucloud中的udisk错误“Read-only file system”修复指南
- Docker exec 宿主对容器执行命令 - 五
- EF分别使用IQueryable和IEnumerable实现更新和删除
- Excel技巧--巧用分列功能整理日期格式
- Eureka核心知识点
- C. The Tower is Going Home
- 解决问题的方法=>现象-->原因-->方案-->方案的优缺点
- MongDB备份error: boost::filesystem::create_directory
- 通过ajax GET方式查询数据，Django序列化objects
- RHEL和Centos常用版本
- 【laravel54】关于用户权限认证RBAC和无限极分类