题目链接
http://codeforces.com/problemset/problem/580/C
题意
根节点是 1
然后所有的叶子结点都是饭店
从根节点到叶子结点的路径上 如果存在 大于m 个 连续的结点都有猫 那么这条路径就是不可行的
求 最后能到达几个饭店
思路
BFS 就可以了 一层一层往下搜
但是要注意
这个输入的时候 xi yi 没有说 那个是父节点 哪个是儿子结点
那就都给它进去
也就是说 每个结点存的结点里面 有一个结点是自己的父亲结点 用visit[] 访问标记一下就可以了
AC代码
//#include <cstdio> //#include <cstring> //#include <ctype.h> //#include <cstdlib> //#include <cmath> //#include <climits> //#include <ctime> //#include <iostream> //#include <algorithm> //#include <deque> //#include <vector> //#include <queue> //#include <string> //#include <map> //#include <stack> //#include <set> //#include <list> //#include <numeric> //#include <sstream> //#include <iomanip> //#include <limits> // //#define CLR(a, b) memset(a, (b), sizeof(a)) //#define pb push_back //#define bug puts("***bug***"); //#define fi first //#define se second //#define stack_expand #pragma comment(linker, "/STACK:102400000,102400000") #define bug #define gets gets_s // //using namespace std; //typedef long long ll; //typedef long double ld; //typedef unsigned long long ull; //typedef pair <int, int> pii; //typedef pair <ll, ll> pll; //typedef pair <string, int> psi; //typedef pair <string, string> pss; //typedef pair <double, int> pdi; // //const double PI = acos(-1.0); //const double E = exp(1.0); //const double eps = 1e-8; // //const int INF = 0x3f3f3f3f; //const int maxn = 4e4 + 1e3 + 10; //const int MOD = 142857; // //int index[8] = { 4, 5, 6, 7, 3, 2, 1, 0 }; // //int visit[maxn]; // //const int FAC[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 }; // //int cantor(int b[8]) //{ // int ans = 0; // for (int i = 0; i < 8; i++) // { // int smaller = 0; // for (int j = i + 1; j < 8; j++) // { // if (b[i] > b[j]) // smaller++; // } // ans += FAC[7 - i] * smaller; // } // return ans; //} // //struct node //{ // int num[8]; // vector <int> ans; //}; // //node st; // //int End; // //vector <int> ans; // //void bfs() //{ // queue <node> q; // st.ans.clear(); // q.push(st); // int flag = cantor(st.num); // if (flag == End) // return; // visit[flag] = 1; // while (!q.empty()) // { // node u = q.front(), v; // q.pop(); // // // A // int i, j; // v.num[0] = u.num[7]; // v.num[1] = u.num[6]; // v.num[2] = u.num[5]; // v.num[3] = u.num[4]; // v.num[4] = u.num[3]; // v.num[5] = u.num[2]; // v.num[6] = u.num[1]; // v.num[7] = u.num[0]; // v.ans = u.ans; // flag = cantor(v.num); // if (visit[flag] == 0) // { // visit[flag] = 1; // v.ans.pb(1); // q.push(v); // if (flag == End) // { // ans = v.ans; // return; // } // } // // // B // v.num[0] = u.num[3]; // v.num[1] = u.num[0]; // v.num[2] = u.num[1]; // v.num[3] = u.num[2]; // v.num[4] = u.num[5]; // v.num[5] = u.num[6]; // v.num[6] = u.num[7]; // v.num[7] = u.num[4]; // v.ans = u.ans; // flag = cantor(v.num); // if (visit[flag] == 0) // { // visit[flag] = 1; // v.ans.pb(2); // q.push(v); // if (flag == End) // { // ans = v.ans; // return; // } // } // // // C // // v.num[0] = u.num[0]; // v.num[1] = u.num[6]; // v.num[2] = u.num[1]; // v.num[3] = u.num[3]; // v.num[4] = u.num[4]; // v.num[5] = u.num[2]; // v.num[6] = u.num[5]; // v.num[7] = u.num[7]; // //for (int i = 0; i < 8; i++) // // cout << v.num[i]; // //cout << endl; // //getchar(); // //getchar(); // v.ans = u.ans; // flag = cantor(v.num); // if (visit[flag] == 0) // { // visit[flag] = 1; // v.ans.pb(3); // q.push(v); // if (flag == End) // { // ans = v.ans; // return; // } // } // } //} // //void clear() //{ // for (int i = 0; i < maxn; i++) // visit[i] = 0; // ans.clear(); //} // //int main() //{ // int a, b; // ios::sync_with_stdio(false); // cin.tie(0); // while (cin >> a >> b) // { // clear(); // int num = 1; // for (int i = 0, j = 7; i < 8; i++, j--, num *= 10) // st.num[j] = (a / num) % 10; // //for (int i = 0; i < 8; i++) // // printf("%d", st.num[i]); // //cout << endl; // int temp[8] = { 0 }; // num = 1; // for (int i = 0, j = 7; i < 8; i++, j--, num *= 10) // temp[j] = (b / num) % 10; // //for (int i = 0; i < 8; i++) // // printf("%d", temp[i]); // //cout << endl; // End = cantor(temp); // bfs(); // int len = ans.size(); // if (len == 0) // cout << 1 << endl; // for (int i = 0; i < len; i++) // printf("%c", 'A' + ans[i] - 1); // printf("\n"); // } //} #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define stack_expand #pragma comment(linker, "/STACK:102400000,102400000") //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 142857; int n, m; int vis[maxn]; int visit[maxn]; vector <int> edge[maxn]; int root; struct node { int root, temp, tot; node() {} node(int root, int temp, int tot) : root(root), temp(temp), tot(tot) {} }; int bfs() { queue <node> q; node u; u.root = root; u.temp = u.tot = vis[root]; if (u.tot <= m) q.push(u); int ans = 0; visit[1] = 1; while (!q.empty()) { node u = q.front(), v; q.pop(); int len = edge[u.root].size(); if (len == 1 && u.root != 1) ans++; for (int i = 0; i < len; i++) { v.root = edge[u.root][i]; if (visit[v.root] == 0) { v.temp = u.temp; v.tot = u.tot; if (vis[v.root] == 0) v.temp = 0; else { if (vis[u.root]) v.temp++; else v.temp = 1; v.tot = max(v.tot, v.temp); } if (v.tot <= m) q.push(v); visit[v.root] = 1; } } } return ans; } void clear() { for (int i = 1; i <= n; i++) edge[i].clear(); } int main() { scanf("%d%d", &n, &m); clear(); for (int i = 1; i <= n; i++) scanf("%d", &vis[i]); int x, y; for (int i = 1; i <= n - 1; i++) { scanf("%d%d", &x, &y); edge[x].pb(y); edge[y].pb(x); } root = 1; printf("%d\n", bfs()); }转载于:https://www.cnblogs.com/Dup4/p/9433075.html
