bfs没过求助
查看原帖
bfs没过求助
108881
松毛虫楼主2021/12/26 17:03
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1005
#define smc 0
using namespace std;
vector <int> G[MAXN]; 
queue<int> q;
bool b[MAXN], f[MAXN];
int k, n, m, ans, cnt[MAXN];
int main(){
	cin >> k >> n >> m;
	int c, x, y;
	for(int i = 0; i < k; i++){
		cin >> c; b[c] = 1;		
	}
	for(int i = 1; i <= m; i++){
		cin >> x >> y;
		G[x].push_back(y);
	}
	for(int i = 1; i <= n; i++){
		if(b[i] == 1){
			q.push(i);
			while(!q.empty()){
				x = q.front(); q.pop(); if(!f[x]) cnt[x]++, f[x] = 1;
				for(int i = 0, sz = G[x].size(); i < sz; i++){
					if(!f[G[x][i]]){
						q.push(G[x][i]);
						f[G[x][i]] = 1, cnt[G[x][i]]++;
					}
				}
			}
		}
		memset(f, 0, sizeof(f));
	}
	for(int i = 1; i <= n; i++){
		if(cnt[i] == k) ans++;
	}
	cout << ans;
	return 0;
}

思路是bfs每一个奶牛能走的点,然后如果这个点能到达的奶牛和奶牛的数目相同,就是吃饭的点。

我找了一篇题解:题解 P2853 【[USACO06DEC]牛的野餐Cow Picnic】 感觉思路上没有什么区别(((

2021/12/26 17:03
加载中...