集訓隊分組

Time Limit:?2 Sec??Memory Limit:?128 MB

Description

中南大學ACM的暑期集訓馬上就要開始了，這次集訓會將全體N名集訓隊員（編號分別為1, 2, …, N）按集訓選拔賽的排名分成兩組，前K名隊員分入A組，其余隊員分入B組。

但現在助理教練CSGrandeur一不小心把集訓選拔賽的排名弄丟了，而之前又沒將A組和B組的人員確定出來，于是CSGrandeur打算問一下集訓人員他們的名次各是怎樣的，以此來確定一下A組的隊員。

然而集訓隊員們都視名次如糞土，只是隱約記得某些人排在了自己的后面，最終反饋到CSGrandeur這里的一共有M條信息，每條信息都可以用一個二元組(x, y) (x!=y)表示，含義為第x名隊員記得第y名隊員的排名比自己的要靠后。

現在CSGrandeur想知道，根據這M條信息，是否可以確定出A組的隊員呢？（默認所有集訓隊員反映的信息都是符合事實的。）

Input

輸入包含多組測試數據。

對于每組測試數據，第一行包含三個正整數N (2<=N<=1000)、K (1<=K<=N)、M (1<=M<=10000)，含義同上。接下來M行每行有兩個正整數x、y (1<=x, y<=N且x!=y)，分別描述了M條信息，對于每對x、y，均表示第x名隊員記得第y名隊員的排名比自己的要靠后。

Output

對于每組測試數據，如果可以確定出A組的隊員，輸出“YES”（不包括引號），否則輸出“NO”（不包括引號）。

Sample Input

3 1 2 1 2 1 3 3 2 2 1 2 1 3

Sample Output

YES NO

解法：從點x開始廣搜，如果從x可以到達的點有v個，說明有v個點在x后面，如果v大于N-K，說明x在前k名中。

#include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std;const int MaxN = 1005; int vis[MaxN]; vector <int> Map[MaxN];//廣搜，返回從x出發可以到達多少個點，即有多少個點在它后面 int BFS(int x) {queue <int> q;q.push(x);memset(vis, 0, sizeof(vis));vis[x] = 1;int cnt = 0;while(!q.empty()) {int nx = q.front(); q.pop();for(int i = 0; i < Map[nx].size(); ++i) {int xx = Map[nx][i];if(!vis[xx]) {q.push(xx);vis[xx] = 1;++cnt;}}}return cnt; }int main() {int N, K, M, x, y;while(~scanf("%d%d%d", &N, &K, &M)) {memset(Map, 0, sizeof(Map));for(int i = 0; i < M; ++i) {scanf("%d%d", &x, &y);Map[x].push_back(y);}int cnt = 0;for(int i = 1; i <= N; ++i) {if(BFS(i) >= N - K) ++cnt; //如果至少有N-K個結點在它之后，說明它就是前K個if(cnt == K) break;}if(cnt == K) puts("YES");else puts("NO");}return 0; }

總結

以上是生活随笔為你收集整理的CSU 1081集训队分组（搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。