2-SAT求任意解模板
2024-10-20 00:51:13
int stk[N],vis[N],low[N],link[N],mark[N];
int top,index,id,du[N];//记录入度数
int pre[N],cnt,g[N];// g 用来记录topsort后的结果
int g1[N]; //用来记录缩点后的每一个点所含的点 void dfs(int s)
{
mark[s]=;
vis[s]=index++;
low[s]=vis[s];
stk[top++]=s;
for(int p=pre[s];p!=-;p=edge[p].next)
{
int v=edge[p].to;
if(mark[v]==) dfs(v);
if(mark[v]==) low[s]=min(low[s],low[v]);
}
if(low[s]==vis[s])
{
int tmp;
id++;
do
{
tmp=stk[top-];
link[tmp]=id;
mark[tmp]=-;
}while(stk[--top]!=s);
}
} void add_edge(int u,int v)
{
edge[cnt].from=u;
edge[cnt].to=v;
edge[cnt].next=pre[u];
pre[u]=cnt++;
} void topsort()
{
memset(mark,,sizeof(mark));
top=;
int tcnt=;
for(int i=;i<=id;i++)
if(du[i]==)
{
mark[i]=;
stk[top++]=i;//把这个节点入栈
g[tcnt++]=i;
}
while(top!=)
{
int cur=stk[--top];
for(int p=pre[cur];p!=-;p=edge[p].next)
{
int v=edge[p].to;
if(mark[v]==) continue;
du[v]--;
if(du[v]==)
{
mark[v]=;
stk[top++]=v;
g[tcnt++]=v;
}
}
} } void dfs1(int s) //将所有不可能的情况标记
{
mark[s]=-;
for(int p=pre[s];p!=-;p=edge[p].next)
{
int v=edge[p].to;
dfs1(v);
}
} void sat2(int sn) //top 表示传入的点数。 其中要保证标号从0开始而且0和1是一组
{
top=index=id=;
memset(mark,,sizeof(mark));
for(int i=;i<sn;i++)
if(mark[i]==)
dfs(i);
int flag=;
for(int i=;i<sn;i+=)
{
if(link[i]==link[i+])
{
flag=;
break;
}
}
if(flag)
{
/* 当不可行的时候输出 */
printf("bad luck\n");
}
else
{
/* 可行的时候输出 */
printf("YES\n"); int tcnt=cnt;
memset(g1,,sizeof(g1));
cnt=;
memset(pre,-,sizeof(pre));
for(int i=;i<sn;i++)
{
g1[ link[i] ]=i;
} memset(du,,sizeof(du)); for(int i=;i<tcnt;i++)
{
int x=edge[i].from;
int y=edge[i].to;
if(link[x] != link[y])
{
add_edge(link[y],link[x]);//建逆图
du[ link[x] ]++;
}
}
topsort();
memset(mark,,sizeof(mark)); for(int i=;i<id;i++)
{
if(mark[ g[i] ]!=-)//表示这个点可以选
{
mark[ g[i] ]=;
int key=g1[ g[i] ];
key=key^;
key=link[key];
dfs1(key);
}
}
/* print mark[ link[i] ]==1 的表示可选的 */ }
}
最新文章
- python字符串内容替换的方法(转载)
- careercup-中等难度 17.5
- POJ 2135 Farm Tour
- awk的日志模块追加日期时间字段的方案
- Linux命令(持续更新中)
- jquery-bootgrid
- [物理学与PDEs]第1章习题8 磁场分布 $\ra$ 电流分布
- poj 3273";Monthly Expense";(二分搜索+最小化最大值)
- LeetCode(169. 求众数)
- 【PAT】B1038 统计同成绩学生(20)(20 分)
- jQuery File Upload 判断图片尺寸,限定图片宽高的办法
- Android在开发中的使用技巧之解决ScrollView嵌套RecyclerView出现的系列问题
- nginx+php+memcache实现hash一致性memcache 集群
- 02_数据库基础之(二)sql语句入门
- Spring Boot使用JWT实现系统登录验证
- 重命名和重定向RF执行生成的output文件
- mysqlint类型的长度值mysql在建表的时候int类型后的长度代表什么
- jQuery基础(常用插件 表单验证,图片放大镜,自定义对象级,jQuery UI,面板折叠)
- Php发送post请求方法
- multiprocessor(中)