164. 可达性统计 - AcWing题库
- 求解拓扑序
- 按照拓扑序求解状态(状态定义为
bitset<N>
)
AcWing 164. 可达性统计(2种简单写法) - AcWing
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <queue>
using namespace std;
const int N = 30010;
const int M = N;
int n, m;
int h[N], e[M], ne[M], idx;
bitset<N> f[N];
int le[N], cnt = 0, ind[N];
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i <= m; i ++ )
{
int a, b;
cin >> a >> b;//a--->b
add(a, b);
ind[b] ++;
}
queue<int> q;
for(int i = 1; i <= n; i ++ )
if(!ind[i]) q.push(i);
while(q.size())
{
int u = q.front();
q.pop();
le[++ cnt] = u;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
ind[j] --;
if(!ind[j]) q.push(j);
}
}
for(int i = cnt; i >= 1; i -- )
{
int u = le[i];
f[u][u] = 1;//自己可达
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];// u--->j
f[u] |= f[j];
}
}
for(int i = 1; i <= n; i ++) cout << f[i].count() << endl;
}
456. 车站分级 - AcWing题库
虚拟源点的应用
AcWing 456. 车站分级 - AcWing
//不停靠说明 a < b
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
const int N = 3100;
const int M = 5000100;
int n, m;
int ind[N], dist[N], a[N];
int h[N], e[M], ne[M], idx, w[M];
int cnt1, cnt2;
bool g[N][N];
bool vis[N];
void add(int a, int b, int c) // 添加一条边a->b
{
w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int main()
{
ios::sync_with_stdio(false);
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i <= m; i ++ )
{
cin >> cnt1;
memset(vis, 0, sizeof vis);
cnt2 = 0 ;
for(int j = 1; j <= cnt1; j ++ )
{
cin >> a[j];
vis[a[j]] = true;
}
// j --- > n + 1 ---- > k
for(int j = a[1]; j <= a[cnt1]; j ++ )
{
if(vis[j]) add(n + i, j, 1), ind[j] ++;
else add(j, n + i, 0), ind[n + i] ++;
}
}
queue<int> q;
for(int i = 1; i <= n; i ++ ) dist[i] = 1;
for(int i = 1; i <= n + m; i ++ )
{
if(!ind[i])
{
q.push(i);
}
}
while(q.size())
{
int u = q.front();
q.pop();
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dist[j] = max(dist[j], dist[u] + w[i]);
ind[j] --;
if(!ind[j]) q.push(j);
}
}
int ans = 0;
for(int i = 1; i <= n; i ++ ) ans = max(ans, dist[i]);
cout << ans;
}