正题
题目链接:https://www.luogu.com.cn/problem/P3825
题目大意
n
n
n场比赛，对于场地
a
a
a不能用赛车
A
A
A（
b
,
c
b,c
b,c以此类推），对于场地
x
x
x可以用任何赛车。然后给定
m
m
m条条件形如
i
I
j
J
i\ I\ j\ J
i I j J表示在第
i
i
i场比赛使用赛车
I
I
I的话那么必须在第
j
j
j场比赛使用赛车
J
J
J。
求一组合法安排方案
解题思路
因为对于场地
x
x
x我们有三种选择方法，所以这是一个
3
−
S
A
T
3-SAT
3−SAT问题，无法计算。而因为
x
x
x场地数量很少，我们可以枚举每个场地
x
x
x使用哪辆车（是场地
a
a
a还是场地
b
b
b）即可。
然后就是很普通的
2
−
S
A
T
2-SAT
2−SAT问题了，时间复杂度
O
(
2
d
n
)
O(2^dn)
O(2dn)
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define p(n,k) (((n)-1)*6+(k)+1)
using namespace std
;
const int N
=5e4*6;
struct node
{
int to
,next
;
}a
[N
*8];
struct quee
{
int a
,b
,va
,vb
;
}q
[N
];
int n
,d
,m
,tot
,scc
,cnt
,ls
[N
];
int dfn
[N
],low
[N
],color
[N
];
bool ins
[N
];char s
[N
];
stack
<int> S
;
void addl(int x
,int y
,int w
){
if(w
)addl(y
,x
,0);
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
return;
}
void tarjan(int x
){
dfn
[x
]=low
[x
]=++cnt
;
S
.push(x
);ins
[x
]=1;
for(int i
=ls
[x
];i
;i
=a
[i
].next
){
int y
=a
[i
].to
;
if(!dfn
[y
])tarjan(y
),low
[x
]=min(low
[x
],low
[y
]);
else if(ins
[y
])low
[x
]=min(low
[x
],dfn
[y
]);
}
if(dfn
[x
]==low
[x
]){
++scc
;
while(S
.top()!=x
){
color
[S
.top()]=scc
;
ins
[S
.top()]=0;
S
.pop();
}
color
[S
.top()]=scc
;
ins
[S
.top()]=0;
S
.pop();
}
return;
}
bool solve(){
memset(ls
,0,sizeof(ls
));
memset(dfn
,0,sizeof(dfn
));
cnt
=scc
=tot
=0;
for(int i
=1;i
<=n
;i
++){
if(s
[i
]=='a'){
addl(p(i
,0),p(i
,1),0);
addl(p(i
,2),p(i
,5),1);
addl(p(i
,4),p(i
,3),1);
}
if(s
[i
]=='b'){
addl(p(i
,2),p(i
,3),0);
addl(p(i
,0),p(i
,5),1);
addl(p(i
,4),p(i
,1),1);
}
if(s
[i
]=='c'){
addl(p(i
,4),p(i
,5),0);
addl(p(i
,0),p(i
,3),1);
addl(p(i
,2),p(i
,1),1);
}
}
for(int i
=1;i
<=m
;i
++)
{addl(p(q
[i
].a
,q
[i
].va
),p(q
[i
].b
,q
[i
].vb
),0);addl(p(q
[i
].b
,q
[i
].vb
+1),p(q
[i
].a
,q
[i
].va
+1),0);}
for(int i
=1;i
<=n
*6;i
++)
if(!dfn
[i
])tarjan(i
);
for(int i
=1;i
<=n
;i
++)
if(color
[p(i
,0)]==color
[p(i
,1)]||color
[p(i
,2)]==color
[p(i
,3)]||color
[p(i
,4)]==color
[p(i
,5)]){return 0;}
for(int i
=1;i
<=n
;i
++){
if(color
[p(i
,0)]<color
[p(i
,1)])printf("A");
else if(color
[p(i
,2)]<color
[p(i
,3)])printf("B");
else if(color
[p(i
,4)]<color
[p(i
,5)])printf("C");
}
return 1;
}
int main()
{
scanf("%d%d",&n
,&d
);
scanf("%s",s
+1);d
=0;
int wz
[10];
for(int i
=1;i
<=n
;i
++)
if(s
[i
]=='x')wz
[++d
]=i
;
scanf("%d",&m
);
for(int i
=1;i
<=m
;i
++){
int a
,b
,va
,vb
;char oa
[3],ob
[3];
scanf("%d %s %d %s",&q
[i
].a
,oa
,&q
[i
].b
,ob
);
if(oa
[0]=='A')va
=0;else q
[i
].va
=(oa
[0]=='B')?2:4;
if(ob
[0]=='A')vb
=0;else q
[i
].vb
=(ob
[0]=='B')?2:4;
}
int MS
=1<<d
;
for(int i
=0;i
<MS
;i
++){
for(int j
=1;j
<=d
;j
++)
s
[wz
[j
]]='a'+((i
>>j
)&1);
if(solve())return 0;
}
printf("-1");
}
