题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5324
题意：有n个人m个关系，每个关系(a,b)表示a表现的比b好，现在要评优，分别求出选出A个优秀时一定能评上的人数，选出B个优秀时一定能评上的人数，选出B个优秀也评不上的人数。
思路：对于所有的人来说，如果他最晚出现的位置还在评优名额内，那么他一定就可以评上；如果最早出现的位置也不在评优名额内，那么一定就评不上。求出一个节点位置的前驱个数，就是他最早出现的位置，求出一个节点的后继个数，n-后继个数就是最晚出现的位置。通过每次比较计数即可。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <sstream> #include <bitset> #include <queue> #include <utility> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;i++) #define Rrep(i,j,k) for (int i=j;i>=k;i--) #define Clean(x,y) memset(x,y,sizeof(x)) #define LL long long #define ULL unsigned long long #define inf 0x7fffffff #define mod 100000007 const int maxn = 5009; int A,B,n,m; vector<int> edge[maxn],Redge[maxn]; bitset<maxn> pre[maxn],Next[maxn]; bool flag[2][maxn]; void init() { int tx,ty; rep(i,1,n) { edge[i].clear(); Redge[i].clear(); } rep(i,1,m) { scanf("%d%d",&tx,&ty); edge[tx].push_back(ty); Redge[ty].push_back(tx); } Clean(flag,false); } void dfs( int now ) { if ( flag[0][now] ) return; flag[0][now] = true; Next[now].reset(); Next[now][now] = 1; int uplim = edge[now].size()-1; rep(i,0,uplim) { dfs( edge[now][i] ); Next[now] |= Next[edge[now][i]]; } } void Rdfs( int now ) { if ( flag[1][now] ) return; flag[1][now] = true; pre[now].reset(); pre[now][now] = 1; int uplim = Redge[now].size()-1; rep(i,0,uplim) { Rdfs( Redge[now][i] ); pre[now] |= pre[Redge[now][i]]; } } void solve() { int ans1 = 0 , ans2 = 0 , ans3 = 0; rep(i,0,n-1) { dfs( i ); Rdfs( i ); int cnt = n + 1 - Next[i].count(); if ( cnt <= A ) ans1++; if ( cnt <= B ) ans2++; cnt = pre[i].count(); if ( cnt > B ) ans3++; } printf("%d\n%d\n%d\n",ans1,ans2,ans3); } int main() { while( scanf("%d%d%d%d",&A,&B,&n,&m) == 4 ) { init(); solve(); } return 0; }
