题意：给你一个SAG，你可以选一个点，但拓扑序在其后的点也要选，让你选a和b个点，问有哪些点必须被选中，最后还问了选b个点哪些一定不被选中。
分析：比赛时写了n^2的暴力跑过了，正解是BITSET压缩一下一个点的前驱集合和后驱集合。
#include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> #include<bitset> #define INF 0x3f3f3f3f #define eps 1e-9 #define MAXN 5005 using namespace std; int a,b,n,m,tot,rd1[MAXN],rd2[MAXN],vis1[MAXN],vis2[MAXN]; bitset<MAXN> up[MAXN],down[MAXN]; vector <int> G[MAXN],G2[MAXN]; void dfs1(int u) { if(vis1[u]) return; vis1[u] = true; up[u][u-1] = 1; for(int v : G[u]) { dfs1(v); up[u] |= up[v]; } } void dfs2(int u) { if(vis2[u]) return; vis2[u] = true; down[u][u-1] = 1; for(int v : G2[u]) { dfs2(v); down[u] |= down[v]; } } int main() { while(~scanf("%d%d%d%d",&a,&b,&n,&m)) { memset(rd1,0,sizeof(rd1)); memset(rd2,0,sizeof(rd2)); memset(vis1,0,sizeof(vis1)); memset(vis2,0,sizeof(vis2)); for(int i = 1;i <= n;i++) { G[i].clear(); G2[i].clear(); up[i].reset(); down[i].reset(); } for(int i = 1;i <= m;i++) { int x,y; scanf("%d%d",&x,&y); x++,y++; G[x].push_back(y); G2[y].push_back(x); rd1[y]++; rd2[x]++; } for(int i = 1;i <= n;i++) { if(rd1[i] == 0) dfs1(i); if(rd2[i] == 0) dfs2(i); } int ans = 0; for(int i = 1;i <= n;i++) if(n - up[i].count() < a) ans++; cout<<ans<<endl; ans = 0; for(int i = 1;i <= n;i++) if(n - up[i].count() < b) ans++; cout<<ans<<endl; ans = 0; for(int i = 1;i <= n;i++) if(down[i].count() > b) ans++; cout<<ans<<endl; } }
