=.=鉴于昨天ZOJ月赛我的题坑了不少神牛，于是发发solution。
【题目大意】
给定n个变量，m个约束关系，p个得分规则，问在满足约束关系的前提下最多能得多少分。
n个变量的值只能为0或1
m个约束关系有a or b = x , a and b = x , a xor b = x三种类型
p个得分规则的形式为：(i,x,j,y,w)，分别表示第i个变量值为x，第j个变量值为y，则可以得到w的分数。最终得分为所有得分之和。
1<=n,m<=100 1<=p<=5000
【标程解法】
只关注n个变量和m个约束关系，那么显然是一个2-sat的模型，但是加入得分规则以后，瞬间就变成了NPC。
于是就搜它…T_T
先对2-sat那个图(不知道怎么搞的看这里http://hi.baidu.com/edwardmj/blog/item/13faf30338fb2a057bec2c81.html)求个传递闭包。
然后顺手按强连通缩下点。强调一下2-sat那个图里一条边(x,y)的意思是如果选了x，那么一定要选y。
题目保证有解，那么我们只考虑有解的情况。
定义：我们称两个缩后的点A,B间有冲突，当且仅当存在var_i∈A，且var_i’∈B
先来证明一个东西：如果这个2-sat存在解，那么只要保证选择的每一步不会构成矛盾(就是说每次新选进一个缩后的点，此点均不和任何已选的点有冲突)，并且选到不能选为止，则最终选出的缩后点集里，一定包含n个缩前的点，且这些点间互不冲突。
也就是说，只要每次都不矛盾，一定能选满所有变量从而得出一组解。
证明如下：
会造成选不满的情形只可能是var_i和var_i’都和已选的点冲突了。也就是说像这样(图中把已经放入已选集合的点标为红色)：
我们回忆一下2-sat里面一条边的意义：(x,y) -> 选了x，那么一定要选y。因为我先作了传递闭包，所以根据图中的逻辑关系，可以想象必然存在对应的这两条红色的边。
不要忘记2-sat这个意义下边的传递性，于是再补两条边。
围观上面的两组点，因为2-sat里边的意义，所以左边的两个蓝点也要选。。。
于是得出结论，如果出现两个都不能选，那么一定是已选集合里已经出现了矛盾，而我们选的时候保证不出现矛盾，那么就一定能选满。。。所以就证完了。
于是乎，我就按变量的编号顺序搜索，如果这个点已经被选择了一个值，自然就不选另外一个值，否则就两个值都选选看…
至于剪枝什么的，就设一个贪心的估价函数，具体方法是在还不能被确定值的变量里面，当成两个都可以同时取，算算可以拿到多少分。由于这个值一定比实际值优，所以最优化剪枝的时候如果当前得分加上这个贪心的得分还超不过目前的最优值，那肯定没意义了。
还有就是在搜到两个都可以选的时候，先搜贪心出的解比较大的一个。
【吐槽】
本来想出个用最小割解的，然后纠结到后来发现实在不会了，v老师就提供了好多个奇葩的代码给我，然后全被我cha掉了。那些代码大部分上都是最小割求的较优解…
看完以后离deadline只剩8小时了T_T,于是死马当活马医出成了搜索题，胡乱加了两个剪枝以后随机了几十个数据发现100都妥妥的，于是就脑抽把范围打成100了…
如果是刻意卡的话，我觉得这个其实跑40都有问题，毕竟大致复杂度是O(2^n)的。
总之这不是一道好题，在此向各位被坑的童鞋表示歉意。。。
【代码】
PS.缩进可能看起来略疼…把tab换成4个空格的大小就好