HS
AFO
HS的博客
CF908H New Year and Boolean Bridges

题目链接

洛谷

题目描述

Your friend has a hidden directed graph with $ n $ nodes. Let $ f(u,v) $ be true if there is a directed path from node $ u $ to node $ v $ , and false otherwise. For each pair of distinct nodes, $ u,v $ , you know at least one of the three statements is true:
1.$ f(u,v) \ And \ f(v,u) $
2.$ f(u,v) \ OR \ f(v,u) $
3.$ f(u,v) \ XOR \ f(v,u) $
Here AND, OR and XOR mean AND, OR and exclusive OR operations, respectively. You are given an $ n $ by $ n $ matrix saying which one of the three statements holds for each pair of vertices. The entry in the $ u $ -th row and $ v $ -th column has a single character. 1. If the first statement holds, this is represented by the character ‘A’. 2. If the second holds, this is represented by the character ‘O’. 3. If the third holds, this is represented by the character ‘X’. 4. The diagonal of this matrix will only contain the character ‘-‘. Note that it is possible that a pair of nodes may satisfy multiple statements, in which case, the character given will represent one of the true statements for that pair. This matrix is also guaranteed to be symmetric. You would like to know if there is a directed graph that is consistent with this matrix. If it is impossible, print the integer -1. Otherwise, print the minimum number of edges that could be consistent with this information.

输入格式

The first line will contain an integer $ n $ ( $ 1<=n<=47 $ ), the number of nodes. The next $ n $ lines will contain $ n $ characters each: the matrix of what you know about the graph connectivity in the format described in the statement.

输出格式

Print the minimum number of edges that is consistent with the given information, or -1 if it is impossible.

输入输出样例

输入 #1

4
-AAA
A-AA
AA-A
AAA-

输出 #1

4

输入 #2

3
-XX
X-X
XX-

输出 #2

2

说明/提示

Sample 1: The hidden graph is a strongly connected graph. We can put all four nodes in a cycle.
Sample 2: One valid graph is $ 3→1→2 $ . For each distinct pair, exactly one of $ f(u,v),f(v,u) $ holds.

分析

发现如果存在两个点$u,v$之间不连通,三个条件都不可能为真,带入$f(u,v)=0$和$f(v,u)=0$就可以看出来这个结论。
也就是说这张图一定是一张弱连通图,以及$OR$条件可以忽略(因为$f(u,v)=1$和$f(v,u)=1$至少有一个为真)。
我们先考虑怎样花费最少的边使这张图是一张弱连通图,显然用$n-1$条边将它变为一棵树最优。
接着考虑$AND$和$XOR$,发现如果$AND$为真,那么$f(u,v)=1$且$f(v,u)=1$,那么$u,v$一定在一个强连通分量里(强连通分量的定义),反之,如果$XOR$为真,$u,v$一定不在一个强连通分量里。
而一个$n$个点的强连通分量至少有$n$条边(环),多花费了一条边,所以要使得强连通分量尽可能少。
发现考虑只有$1$个点的强连通分量没有意义(随便连,反正不造成额外贡献),所以只考虑大小$\ge 2$的强连通分量,这种强连通分量最多只有$\lfloor \frac{47}{2} \rfloor = 23$个,于是为状压提供了条件。
首先使用并查集维护所有只考虑$AND$关系形成的强连通分量。
如果其中一个强连通分量中存在两个点直接满足$XOR$,那么显然矛盾,无解。
接着尝试合并这些强连通分量(因为有$XOR$的关系,有些强连通分量直接不能合并)。
设$f_i$表示$i$这个子集中的强连通分量能否合并成一个新的强连通分量,具体的,就是做一遍子集变换。
枚举合并了几次,一直合并到所有的强连通分量都合并为一个。
设第$i$次合并结果为$g_i$。
$$
g_{i,j}= \sum_k g_{i-1,k} \times f_{j \oplus k}
$$
这样如果一个集合不为$0$,那么它就可以表示出来。
发现上面的式子等价于下面的式子
$$
g_{i,j}= \sum_{a,b} [a|b==j] g_{i-1,a} \times f_{b}
$$
为什么呢?因为如果$a,b$有交,那么它们之前就应该已经合并过了,这是因为如果它们能合并,那么之前在合并$a \oplus (a|b)$和$b$的时候也可以,那么应该在之前就退出了,所以不存在这种情况,如果$a,b$没交,那么和上面的式子就是一样的了。
这个式子长得就是一副子集变换的样,就直接上一遍子集变换就完事了。
但是每次做$FWT-IFWT$可能会$TLE$,所以提前预处理出每个位置的点值对全集的系数,就可以每次不做$IFWT$,直接得到全集的值。

一些对我而言的坑

  • 第一次做子集变换时不全是$0/1$,所以直接异或1是错的。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 50
#define maxl 8400000
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,cnt,a[maxl],f[maxl],g[maxl],fa[maxn],siz[maxn],idx[maxn];
char mp[maxn][maxn];
void FWT(int *A,int len)
{
    for(int i=1;i<len;i<<=1)
        for(int j=0;j<len;j+=(i<<1))
            for(int k=j;k<j+i;k++)
                f[k+i]+=f[k];
}
void init(int len)
{
    for(int i=0;i<len;i++)
        a[i]=1;
    for(int i=1;i<len;i<<=1)
        for(int j=0;j<len;j+=(i<<1))
            for(int k=j;k<j+i;k++)
                a[k]*=-1;
}
int find(int x)
{
    return fa[x]==x? x:fa[x]=find(fa[x]);
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",mp[i]+1);
        fa[i]=i;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(mp[i][j]=='A')
                fa[find(i)]=find(j);
    for(int i=1;i<=n;i++)
        siz[find(i)]+=1;
    for(int i=1;i<=n;i++)
        if(find(i)==i&&siz[i]>1)
            idx[i]=1<<(cnt++);
    if(!cnt)
    {
        printf("%d\n",n-1);
        return 0;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(mp[i][j]=='X')
            {
                int x=find(i),y=find(j);
                if(x==y)
                {
                    puts("-1");
                    return 0;
                }
                else if(idx[x]&&idx[y])
                    f[idx[x]|idx[y]]=true;
            }
    int len=1<<cnt;
    FWT(f,len);
    init(len);
    for(int i=0;i<len;i++)
    {
        f[i]=!f[i];
        g[i]=1;
    }
    FWT(f,len);
    for(int i=0;i<cnt;i++)
    {
        int res=0;
        for(int j=0;j<len;j++)
        {
            g[j]*=f[j];
            res+=a[j]*g[j];
        }
        if(res)
        {
            printf("%d\n",n+i);
            return 0;
        }
    }
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

CF908H New Year and Boolean Bridges
FWT优化状压DP
扫描二维码继续阅读
2020-01-10