PS: 该题目正解应该是DP, 本人没想太多写了深搜, TLE, 总共4982个点, 只能过4974个
一. 题目描述(详见)
二. 算法
DFS + 剪枝
三. 分析
模拟即可
四. C++ 代码
typedef pair<int, int> PII;
const int N = 3e4 + 10;
#define x first
#define y second
class Solution {
public:
int h[N], e[N << 1], ne[N << 1], idx, sum;
bool st[N];
int ans;
bool check(int d, int cnt) // 检查是否满足条件, 如果满足则提前退出DFS
{
if(d >= ans) return true; // 最优性剪枝, 当前已知答案不比当前枚举的方案差
if(cnt == sum) return true; // 可行性剪枝, 找到的金币已是金币总数
return false;
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
PII DFS(int u, int fa, vector<int>& coins, int dist, int cnt)
{
int get = 0, d = 0;
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
if(son == fa) continue;
if(!st[son]) get += coins[son], st[son] = true;
if(check(d + dist * 2, get + cnt)) return {get, d}; // 剪枝
for(int j = h[son]; ~j; j = ne[j])
{
int sson = e[j];
if(sson == son) continue;
if(!st[sson]) get += coins[sson], st[sson] = true;
if(check(d + dist * 2, get + cnt)) return {get, d}; // 剪枝
}
}
for(int i = h[u]; ~i; i = ne[i])
{
int son = e[i];
if(son == fa) continue;
auto t = DFS(son, u, coins, dist + 1, get);
if(t.x)
{
get += t.x, d += 1 * 2 + t.y;
if(check(d + dist * 2, get + cnt)) return {get, d}; // 剪枝
}
}
return {get, d};
}
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
int n = coins.size();
memset(h, -1, sizeof h);
sum = 0; ans = 0x3f3f3f3f;
for(int i : coins) sum += i;
for(int i = 0; i < edges.size(); i ++ )
{
int a = edges[i][0], b = edges[i][1];
add(a, b); add(b, a);
}
for(int i = 0; i < n; i ++ )
{
memset(st, 0, sizeof st); st[i] = true;
auto t = DFS(i, -1, coins, 0, coins[i]);
if(coins[i]) t.x ++ ;
if(t.x == sum) ans = min(t.y, ans);
}
return ans;
}
};
