HDOJ 3062 Party - 2-sat入门

HDOJ 3062 Party - 2-sat入门

每组两个元素或者说一类物品有两种状态..每组(类)选且仅选一个..某些元素(状态)不能共存..通常是问能否选择成功..若成功输出选择方案...

本题很裸...而且只是要求能否成功...判断一个2-sat是否成功..就是连了边用Tarjan求强联通分量...若同组的两个在一个强联通分量中...则说明不可成功....因为一个强联通分量的意思是这个内部的点选择了其中一个..内部其他的点就必须全部选择..所以与题目要求矛盾...

Program:

#include#include#include#include#include#include#include#include#define ll long long#define oo 10007#define pi acos(-1.0)#define MAXN 2005using namespace std; vector T[MAXN];int n,dfn[MAXN],low[MAXN],_DfsIndex,tpnum,tp[MAXN];stack mystack;bool instack[MAXN];void tarjan(int x){ int i,y,m=T[x].size(); dfn[x]=low[x]=++_DfsIndex; mystack.push(x); instack[x]=true; for (i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。