1 条题解

  • 0
    @ 2023-3-11 18:28:33

    首先对原图缩点,然后有一个显然的贪心:如果到达了一个强连通分量,一定会将其遍历完一遍后再离开。

    于是考虑在缩点后的图上拓扑排序,对于到达 uu 时按位与为 w0w_0,经过了 uw1vu \to^{w_1} v 这条边,就在 vv 的按位或集合中插入 w0orw1orSvw_0 \operatorname{or} w_1 \operatorname{or} S_v,其中 SvS_v 表示 vv 这个强连通分量内所有边的按位或,若不存在边则为 00

    最后对每个 ss 可以到达的点找出按位或集合中的最大值即可。时间复杂度为 O(2N(n+m))O(2^N(n + m)),其中 N=13N = 13,显然不能通过。

    考虑一个剪枝:对于同一个点的两个可能且不同的按位与集合中的元素 x,yx, y,如果 xy,xandy=xx \neq y, x \operatorname{and} y = xxx 一定不优于 yy

    现在考虑每个点剪枝后的最大按位与集合的大小。

    对于集合 S=[0,2N)S = [0, 2^N),求满足 TST \subseteq S 且 $\forall x, y \in T, x \neq y, x \operatorname{and} y \neq x$ 的 T|T| 的上限。

    为了让 T|T| 尽量大,我们贪心地考虑对于某个 ii,选择所有二进制中 11 的个数为 ii 的数,此时答案为 CNiC_N^i,且当 $i = \lfloor \frac{N}{2} \rfloor, \lceil \frac{N}{2} \rceil$ 时取得最大值为 M=1716M = 1716

    实现时,考虑一个点的最大按位或集合的大小,不难发现点 uu 在剪枝前的集合大小不大于 inuMin_u M,则拓扑排序部分的时间复杂度为 O(mM)O(mM)

    我们可以先预处理出 [0,2N)[0, 2^N) 中每个数的子集集合并将其存入 2N2^N 个 bitset,每次剪枝时新建一个 bitset SS,从大到小讨论未被剪枝的数,设当前讨论的数为 xx,如果 SxS_x11,不将 xx 加入集合;否则,加入集合并将 SS 按位或 xx 的子集集合,则剪枝操作的时间复杂度为 O(nM2Nω)O(\frac{nM 2^N}{\omega})

    综上,时间复杂度为 O(nM2Nω+mM+3N)O(\frac{nM 2^N}{\omega} + mM + 3^N)

    注意在拓扑排序时要先加入那些从 ss 出发无法到达的点。

    代码:

    #include <iostream>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    #include <bitset>
    #include <cstdio>
    
    using namespace std;
    
    typedef struct {
    	int nxt;
    	int end;
    	int dis;
    } Edge;
    
    const int N = 3e5 + 7, M = 2e4 + 7, K = 1 << 13;
    int cnt = 0;
    int u[N], v[N], w[N], head[M], dis[M], dfn[M], low[M], belong[M], or_val[M], deg[M];
    bool vis1[M], vis2[M];
    Edge edge[N];
    stack<int> s;
    queue<int> q;
    vector<int> v1, v2[M];
    bitset<K + 7> bs1, bs2[K + 7], bs3[M];
    
    inline void init1(){
    	for (register int i = 0; i < K; i++){
    		for (register int j = i; ; j = i & (j - 1)){
    			bs2[i][j] = true;
    			if (j == 0) break;
    		}
    	}
    }
    
    inline void init2(int n){
    	cnt = 0;
    	for (register int i = 1; i <= n; i++){
    		head[i] = 0;
    	}
    	for (register int i = 0; i <= n; i++){
    		dis[i] = -1;
    	}
    }
    
    inline void add_edge(int start, int end, int dis){
    	cnt++;
    	edge[cnt].nxt = head[start];
    	head[start] = cnt;
    	edge[cnt].end = end;
    	edge[cnt].dis = dis;
    }
    
    void tarjan(int u, int &id, int &scc_cnt){
    	dfn[u] = low[u] = ++id;
    	vis1[u] = vis2[u] = true;
    	s.push(u);
    	for (register int i = head[u]; i != 0; i = edge[i].nxt){
    		int x = edge[i].end;
    		if (!vis1[x]){
    			tarjan(x, id, scc_cnt);
    			low[u] = min(low[u], low[x]);
    		} else if (vis2[x]){
    			low[u] = min(low[u], dfn[x]);
    		}
    	}
    	if (dfn[u] == low[u]){
    		int cur;
    		scc_cnt++;
    		do {
    			cur = s.top();
    			s.pop();
    			vis2[cur] = false;
    			belong[cur] = scc_cnt;
    		} while (cur != u);
    	}
    }
    
    int main(){
    	int n, m, s, id = 0, scc_cnt = 0;
    	scanf("%d %d %d", &n, &m, &s);
    	init1();
    	for (register int i = 1; i <= m; i++){
    		scanf("%d %d %d", &u[i], &v[i], &w[i]);
    		add_edge(u[i], v[i], w[i]);
    	}
    	for (register int i = 1; i <= n; i++){
    		if (!vis1[i]) tarjan(i, id, scc_cnt);
    	}
    	init2(scc_cnt);
    	for (register int i = 1; i <= m; i++){
    		if (belong[u[i]] == belong[v[i]]){
    			or_val[belong[u[i]]] |= w[i];
    		} else {
    			deg[belong[v[i]]]++;
    			add_edge(belong[u[i]], belong[v[i]], w[i]);
    		}
    	}
    	v2[belong[s]].push_back(or_val[belong[s]]);
    	for (register int i = 1; i <= scc_cnt; i++){
    		if (deg[i] == 0) q.push(i);
    	}
    	while (!q.empty()){
    		int cur = q.front(), size = v2[cur].size();
    		q.pop();
    		v1.clear();
    		bs1.reset();
    		sort(v2[cur].begin(), v2[cur].end(), greater<int>());
    		for (register int i = 0; i < size; i++){
    			if (!bs1[v2[cur][i]]){
    				bs1 |= bs2[v2[cur][i]];
    				v1.push_back(v2[cur][i]);
    				if (dis[cur] == -1) dis[cur] = v2[cur][i];
    			}
    		}
    		v2[cur] = v1;
    		size = v2[cur].size();
    		for (register int i = head[cur]; i != 0; i = edge[i].nxt){
    			int x = edge[i].end;
    			for (register int j = 0; j < size; j++){
    				int y = v2[cur][j] | edge[i].dis | or_val[x];
    				if (!bs3[x][y]){
    					bs3[x][y] = true;
    					v2[x].push_back(y);
    				}
    			}
    			if (--deg[x] == 0) q.push(x);
    		}
    	}
    	for (register int i = 1; i <= n; i++){
    		cout << dis[belong[i]] << " ";
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    276
    时间
    8000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    84
    已通过
    10
    上传者