4484: [Jsoi2015]最小表示(拓扑序+bitset维护连通性)
发布时间:2020-12-14 04:46:38 所属栏目:大数据 来源:网络整理
导读:4484: [Jsoi2015]最小表示 题目链接 题解: bitset的题感觉都好巧妙啊QAQ。 因为题目中给出的是一个DAG,如果 (u-v) 这条边可以删去,等价于还存在一个更长的路径可以使得 (u) 到 (v) 。 这里的“更长”我们可以用拓扑序来搞,拓扑序大的相对于起点也肯
4484: [Jsoi2015]最小表示题目链接 题解:bitset的题感觉都好巧妙啊QAQ。 #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cmath> #include <bitset> #include <queue> using namespace std; typedef long long ll; const int N = 30005,M = 100005; int n,m; int in[N]; bitset <N> s[N] ; struct Edge{ int v,next ; }e[M]; int head[N],tot; void adde(int u,int v) { e[tot].v = v; e[tot].next = head[u]; head[u] = tot++; } int vist[N],t[N],a[N],b[N]; int T; void Topsort() { queue <int> q; for(int i = 1; i <= n; i++) if(!in[i]) q.push(i) ; while(!q.empty()) { int u = q.front(); q.pop() ; vist[u] = ++T; t[T] = u; for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; if(--in[v] == 0) q.push(v) ; } } } bool cmp(int x,int y) { return vist[x] > vist[y] ; } int ans ; void work(int u) { int tot = 0; s[u].set(u) ; for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].v; b[++tot] = v; } sort(b + 1,b + tot + 1,cmp) ; for(int i = tot; i >= 1; i--) { if(s[u][b[i]]) ans++; else s[u] |= s[b[i]] ; } } int main() { ios::sync_with_stdio(false); cin.tie(0) ; cin >> n >> m; memset(head,-1,sizeof(head)) ; for(int i = 1; i <= m; i++) { int u,v; cin >> u >> v; adde(u,v) ;++in[v] ; } Topsort() ; for(int i = 1; i <= n; i++) a[i] = i; sort(a + 1,a + n + 1,cmp) ; for(int i = 1; i <= n; i++) work(a[i]) ; cout << ans ; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |