3题目分析：全部值减去权值最大的一条从根到叶子的路径值即可#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 1e5 + 5;int re[MAX], fa[MAX];int n;int get_num(int v){int cnt = 0;for(; v; v = fa[v])cnt += re[v];return cnt;}int main(){while(scanf("%d", &n) != EOF){memset(re, 0, sizeof(re));memset(fa, 0, sizeof(fa));int sum = 0;for(int i = 0; i < n – 1; i++){int u, v, w;scanf("%d %d %d", &u, &v, &w);fa[v] = u;re[v] = w;sum += w;}int ma = 0;for(int i = 2; i <= n; i++)ma = max(ma, get_num(i));printf("%d\n", sum – ma);}}</span>
Problem G Escape
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
小明进入地下迷宫寻找宝藏，，找到宝藏后却发生地震，迷宫各处产生岩浆，小明急忙向出口处逃跑。如果丢下宝藏，小明就能迅速离开迷宫，但小明并不想轻易放弃自己的辛苦所得。所以他急忙联系当程序员的朋友你（当然是用手机联系），并告诉你他所面临的情况，希望你能告诉他是否能成功带着宝藏逃脱。
Input
有多组测试数据。
每组测试数据第一行是一个整数T,代表接下去的例子数。（0<=T<=10）
接下来是T组例子。
每组例子第一行是两个整数N和M。代表迷宫的大小有N行M列（0<=N,M<=1000）。
接下来是一个N*M的迷宫描述。
S代表小明的所在地。
E代表出口,出口只有一个。
.代表可以行走的地方。
！代表岩浆的产生地。（这样的地方会有多个,其个数小于等于10000）
#代表迷宫中的墙，其不仅能阻挡小明前进也能阻挡岩浆的蔓延。
小明携带者宝藏每秒只能向周围移动一格，小明不能碰触到岩浆（小明不能和岩浆处在同一格）。
岩浆每秒会向四周不是墙的地方蔓延一格。
小明先移动完成后，岩浆才会蔓延到对应的格子里。
小明能移动到出口，则小明顺利逃脱。
Output
每组测试数据输出只有一行“Yes”或者“No”。“Yes”代表小明可以成功逃脱。否则输出“No”。
Sample Input
35 5….!S….#….!#…#E…2 2S.!E2 2SE!.
Sample Output
YesNoYes题目分析：BFS1预处理各个点岩浆到达的最短时间，BFS2搜人是否能出去，要注意的一点是如果人和岩浆同时到E，则人算成功逃脱#include <cstdio>#include <cstring>#include <queue>using namespace std;int const MAX = 1005;int const INF = 0x7fffffff;char map[MAX][MAX];int tim[MAX][MAX];bool vis[MAX][MAX];int n, m;int sx, sy, ex, ey;int dx[4] = {1, 0, -1, 0};int dy[4] = {0, -1, 0, 1};struct NODE{int x, y;int step;};bool ok(int i, int j){if(i >= 0 && j >= 0 && i < n && j < m)return true;return false;}void BFS1(){NODE yj;queue <NODE> q;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(map[i][j] == '!'){yj.x = i;yj.y = j;yj.step = 0;tim[i][j] = 0;q.push(yj);}}}while(!q.empty()){NODE now = q.front(), t;q.pop();//printf("now.x = %d now.y = %d now.step = %d\n", now.x, now.y, now.step);for(int i = 0; i < 4; i ++){t.x = now.x + dx[i];t.y = now.y + dy[i];t.step = now.step + 1;if(ok(t.x, t.y) && t.step < tim[t.x][t.y]){tim[t.x][t.y] = t.step;q.push(t);}}}return;}bool BFS2(){memset(vis, false, sizeof(vis));NODE st;st.x = sx;st.y = sy;vis[sx][sy] = true;st.step = 0;queue <NODE> qq;qq.push(st);while(!qq.empty()){NODE now = qq.front(), t;qq.pop();if(now.x == ex && now.y == ey && t.step <= tim[t.x][t.y])return true;for(int i = 0; i < 4; i++){t.x = now.x + dx[i];t.y = now.y + dy[i];t.step = now.step + 1;if(t.x == ex && t.y == ey && t.step <= tim[t.x][t.y])return true;if(ok(t.x, t.y) && !vis[t.x][t.y] && t.step < tim[t.x][t.y]){vis[t.x][t.y] = true;qq.push(t);}}}return false;}int main(){int T;while(scanf("%d", &T) != EOF){while(T–){scanf("%d %d", &n, &m);if(n == 0 || m == 0){printf("No\n");continue;}for(int i = 0; i < n; i++){scanf("%s", map[i]);for(int j = 0; j < m; j++){tim[i][j] = INF;if(map[i][j] == 'S'){sx = i;sy = j;}if(map[i][j] == 'E'){ex = i;ey = j;}if(map[i][j] == '#')tim[i][j] = 0;}}BFS1();printf("%s\n", BFS2() ? "Yes" : "No");}}}
Problem 2197 最小花费
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description只有不快的斧，没有劈不开的柴。
