游游拿到了一棵树,其中每个节点被染成了红色(r)、绿色(g)或蓝色(b)。 游游想删掉一条边,使得剩下的两个连通块各恰好有三种颜色。 游游想知道,有多少合法的边可以删除? 注:树指不含重边和自环的无向连通图。
区块链毕设网qklbishe.com为您提供问题的解答
游游拿到了一棵树,其中每个节点被染成了红色(r)、绿色(g)或蓝色(b)。
游游想删掉一条边,使得剩下的两个连通块各恰好有三种颜色。
游游想知道,有多少合法的边可以删除?
注:树指不含重边和自环的无向连通图。
为啥过6/11?,预期21565,实际输出21566
#include <iostream> #include <bits/stdc++.h> using namespace std; bool track(unordered_map<int, vector<int>>& tree, string& color, int n1, int n2, int& r, int& g, int& b){ if(color[n1 - 1] == 'r') r++; else if(color[n1 - 1] == 'g') g++; else b++; if(r&&g&&b) return true; bool rgb = false; for(int i = 0; i < tree[n1].size(); i++){ if(tree[n1][i] == n2) continue; else{ if(color[tree[n1][i] - 1] == 'r') r++; else if(color[tree[n1][i] - 1] == 'g') g++; else b++; } rgb |= track(tree, color, tree[n1][i], n1, r, g, b); } return rgb; } bool check(unordered_map<int, vector<int>>& tree, string& color,int n1, int n2){ int r=0, g=0, b=0; return track(tree, color, n1, n2, r, g, b); } int main() { int n; while (cin >> n) { // 注意 while 处理多个 case string color; cin >> color; unordered_map<int, vector<int>> tree; int f, c; vector<vector<int>> edge; for(int i = 0; i < n; i++){ cin >> f >> c; edge.push_back({f, c}); tree[f].push_back(c); tree[c].push_back(f); } int res = 0; for(int i = 0; i < edge.size(); i++){ if(check(tree, color, edge[i][0], edge[i][1]) && check(tree, color, edge[i][1], edge[i][0])){ res++; } } cout << res << endl; } } // 64 位输出请用 printf("%lld")
39:30
以上就是关于问题游游拿到了一棵树,其中每个节点被染成了红色(r)、绿色(g)或蓝色(b)。
游游想删掉一条边,使得剩下的两个连通块各恰好有三种颜色。
游游想知道,有多少合法的边可以删除?
注:树指不含重边和自环的无向连通图。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码,定制。
区块链NFT链游项目方科学家脚本开发培训