Astronauts题解
Pwtking
·
·
题解
传送门
介绍一种 2-sat 的新做法。
考虑在建图时开三倍数组：[1,n] 代表选择 A 任务，[n+1,2n] 代表选择 B 任务，[2n+1,3n] 代表选择 C 任务。
在此基础上分四种情况讨论：
分别设每一对关系中第一个人的年龄为 a，第二个人的年龄为 b，所有人中总年龄和为 sum。
则分别有：
$a\times n< sum$ 且 $b\times n<sum$；
$a\times n\ge sum$ 且 $b\times n\ge sum$；
$a\times n< sum$ 且 $b\times n\ge sum$；
对应到代码上如下：
```cpp
for (ll i=1;i<=m;++i) {
ll a=in(),b=in();
// old[i] 表示下标为 i 的人的年龄
if (old[a]*n>=sum&&old[b]*n<sum) G[a+2*n].push_back(b+n),G[b+2*n].push_back(a);
else if(old[a]*n<sum&&old[b]*n<sum) G[a+n].push_back(b+2*n),G[b+n].push_back(a+2*n),G[a+2*n].push_back(b+n),G[b+2*n].push_back(a+n);
else if (old[a]*n>=sum&&old[b]*n>=sum) G[a].push_back(b+2*n),G[b].push_back(a+2*n),G[b+2*n].push_back(a),G[a+2*n].push_back(b);
else if (old[a]*n<sum&&old[b]*n>=sum) G[a+2*n].push_back(b),G[b+2*n].push_back(a+n);
}
```
注意：这个地方是将每个人的年龄乘上 $n$ 来进行比较的，为避免精度问题。
接下来 Tarjan 的时候也是将 $n$ 遍历到三倍。
最后取值的时候只取这个人能取到的即可，代码如下：
```cpp
for (ll i=1;i<=n;++i) {
if (old[i]*n<sum) {
if (color[i+n]>color[i+2*n]) cout<<"C"<<endl;
else cout<<"B"<<endl;
}
else {
if (color[i]>color[i+2*n]) cout<<"C"<<endl;
else cout<<"A"<<endl;
}
}
```