本文共 2099 字，大约阅读时间需要 6 分钟。

我原本以为2-SAT只有裸题…太憨了…

说实话刚看到这题我还以是网络流,我是fw把

二者取一模型

先只考虑$x$地图以外的地图,发现比较特殊

虽然你有三种车,但是除掉不适合的类型就只有两种合适的车

2-SAT一般是解决二者取一问题,那么现在就是从两种合适的车选一个

简化状态

之前的2-SAT每个点的状态都是真/假,现在可是有$A/B/C$三种车啊!!

但是每次游戏只有两种选择

可以把状态抽象为选择第一种合适的车,或者选择第二种合适的车

建图满足限制

现在每次游戏都拆分为了两个点,都适合本次游戏

对于每条限制形如第$i$场比赛若选$h_i$车,则第$j$场比赛必选$h_j$车

若第$i$场比赛不适合$h_i$车,忽略即可,本来第$i$场比赛就不可能选

若第$i$场比赛适合$h_i$车且第$j$场比赛不适合$h_j$车

那么第$i$场比赛不能选$h_i$车,建边$h_i->h_i^{\prime }$(其中$h_i^{\prime }$表示另外一种合适车的选择)

表示不能选$h_i$车

若第$i$场比赛适合$h_i$车且第$j$场比赛适合$h_j$车

那么连边$h_i->h_j$和$h_j^{\prime }->h_i^{\prime }$,分别表示要么全选,要么全不选

处理特殊地图

上面的建图已经处理的差不多了,但是有一张地图不符合二者取一模型

x地图适用于三种车,三种选择!!不可做。

注意到$d$不大,直接二进制枚举每张地图用哪两个车,复杂度$O(3^d)$

但是发现把$AB,AC,BC$都枚举一遍是很浪费的,因为一张地图只会选一辆车

枚举$AB,AC$即可,不管这张地图想选$A,B,C$都是可以满足的,让2-SAT为你挑。

当然,你想枚举$BC,AC$也没关系。

(代码中的点是i,i+1一组的不是i,i+n一组的,稍微注意一下下)

#include 
   
    using namespace std;const int maxn = 1e7+10;struct edge{
   	int to,nxt;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v){
   	d[++cnt] = ( edge ){
   v,head[u]},head[u] = cnt;}int l[maxn],r[maxn],n,m,D;int dfn[maxn],low[maxn],stac[maxn],vis[maxn],scc[maxn],id,top,sc;char cn[maxn][2],s[maxn],hi[maxn],hj[maxn];void tarjan(int u){
   	dfn[u] = low[u] = ++id; stac[++top] = u, vis[u] = 1;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( !dfn[v] )	tarjan(v),low[u] = min( low[u],low[v] );		else if( vis[v] )	low[u] = min( low[u],dfn[v] );	}	if( dfn[u]==low[u] )	{
   		sc++; int temp;		while( temp = stac[top--] )		{
   			scc[temp] = sc; vis[temp] = 0;			if( u==temp )	break;		}	}}int solve(int x){
   	cnt = 1, id = top = sc = 0;	for(int i=1;i<=n+n;i++)	dfn[i] = low[i] = head[i] = 0;	int now = 0;	for(int i=1;i<=n;i++)	{
   		if( s[i]=='a' )	cn[i][0] = 'B',cn[i][1] = 'C';		else if( s[i]=='b' )	cn[i][0] = 'A',cn[i][1] = 'C';		else if( s[i]=='c' )	cn[i][0] = 'A',cn[i][1] = 'B';		else		{
   			if( (1<
    
     > l[i] >> hi[i] >> r[i] >> hj[i] ;	for(int i=0;i<(1<
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/115439598 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！