4484: [Jsoi2015]最小表示
题解:
bitset的题感觉都好巧妙啊QAQ。
因为题目中给出的是一个DAG，如果(u->v)这条边可以删去，等价于还存在一个更长的路径可以使得(u)到(v)。
这里的“更长”我们可以用拓扑序来搞，拓扑序大的相对于起点也肯定更长。那么思路就是对于每个点考虑删掉其出边，并且枚举边的时候拓扑序是从小到大的，然后来检验连通性。
但如果我们按照拓扑序来搞的话，很显然是错的。我们其实可以直接按着拓扑序反着来。这样的话后面点的连通性很容易知道，并且当前点与后面点的连通性也容易维护。
感觉拓扑序这种东西有点神奇，反着来经常能消除一些东西的影响，但具体什么我也不清楚QWQ。可能这样阶段划分清晰一点？反着来已处理过的与正在处理的关系是明确的，正着来正在处理的与后面的关系就不是很明确，就不是很容易维护信息。
如果有大佬知道可以给我明确一下。
代码如下：
#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;
}