A：开局就开了这题，一直以为一开始想的有问题。
其实并没有错。对于起点和终点，肯定是某个终点和起点的这段距离只需要走一次。
其中重叠也应该看成不同的路线。（仔细想想就明白了）
那么，就是找和每个点最远的点了。
这里就用到了树的直径。
根据树的直径的性质，距离每个点最远的点肯定是直径中的一点。（可以画图理解，也就是链的几种情况）
那么，我们先求出和1最远的点，那个点显然就是直径的一个点，然后可以从这个点出发找到另一个点，然后就可以贪心排了。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5+5; const int M = 1e4; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("date1.out","w",stdout);*/} struct Node{int to;LL dis;}; vector<Node> G[N]; int n; LL m,ans[N],sum = 0,dis[N],dis1[N],dis2[N],mx = -1,pt1,pt2; void dfs(int u,int fa) { for(auto v : G[u]) { if(v.to == fa) continue; dis[v.to] = dis[u]+v.dis; dfs(v.to,u); } if(dis[u] > mx) mx = dis[u],pt1 = u; } void dfs1(int u,int fa) { for(auto v : G[u]) { if(v.to == fa) continue; dis1[v.to] = dis1[u]+v.dis; dfs1(v.to,u); } if(dis1[u] > mx) mx = dis1[u],pt2 = u; } void dfs2(int u,int fa) { for(auto v : G[u]) { if(v.to == fa) continue; dis2[v.to] = dis2[u]+v.dis; dfs2(v.to,u); } } int main() { n = read(),m = read(); for(rg int i = 1;i < n;++i) { int u,v,w;u = read(),v = read(),w = read(); G[u].push_back(Node{v,w}); G[v].push_back(Node{u,w}); sum += 2LL*w; } dfs(1,0);//找到第一个直径点 mx = -1; dfs1(pt1,0); dfs2(pt2,0); for(int i = 1;i <= n;++i) ans[i] = sum-max(dis1[i],dis2[i]); sort(ans+1,ans+n+1); int tmp = 0; for(int i = 1;i <= n;++i) { if(m >= ans[i]) m -= ans[i],tmp++; else break; } printf("%d ",tmp); // system("pause"); return 0; }
C：如果n再小一点，那么就是一个比较简单的题了。
只需要处理出每个点，然后dfs全排列即可。
但是这里数据大了点，dfs会T。所以需要用到状压DP。
用dp[i][j]表示在i状态时最后一个修复的点是j。
那么我们从当前状态往后推。即从j点再去修复k点。
那么就在i的基础上再修复了一个点，只需要加上dis[j][k]即可。
这里有个误区，j->k的最短距离是需要从j去找到所有点的最短距离的。
而不是和同一个点的距离差。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5+5; const int M = 1e4; const LL Mod = 1e9+7; #define rg register #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar('-');} if(x > 9) print(x/10); putchar(x%10+'0'); } } using namespace FASTIO; void FRE(){ /*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} map<pii,int> mp; string s[205]; int dis[20][20],n,m,t,vis[205][205],b[4][2] = {1,0,-1,0,0,1,0,-1},cnt = 0; LL dp[33005][20];//dp[i][j]表示i状态时，最后一个修复的位置是j号电线杆。 /* 向后dp，去更新后面的状态。 即对于没修复的位置去更新。 */ struct Node{int x,y,step;}p[20]; void bfs(int st) { memset(vis,0,sizeof(vis)); queue<Node> Q; Q.push(Node{p[st].x,p[st].y,0}); vis[p[st].x][p[st].y] = 1; dis[st][st] = 0; while(!Q.empty()) { Node q = Q.front(); Q.pop(); for(int i = 0;i < 4;++i) { int px = q.x+b[i][0]; int py = q.y+b[i][1]; if(px >= 0 && px < n && py >= 0 && py < m && !vis[px][py] && s[px][py] != '#') { vis[px][py] = 1; if(s[px][py] == 'T') dis[st][mp[pii{px,py}]] = q.step+1; Q.push(Node{px,py,q.step+1}); } } } } int main() { n = read(),m = read(),t = read(); for(rg int i = 0;i < n;++i) cin >> s[i]; for(rg int i = 0;i < n;++i) { for(rg int j = 0;j < m;++j) { if(s[i][j] == 'S') { p[0] = {i,j}; mp[pii{i,j}] = 0; } if(s[i][j] == 'T') { p[++cnt] = {i,j}; mp[pii{i,j}] = cnt; } } } for(rg int i = 0;i <= cnt;++i) bfs(i); int f = 0; for(rg int i = 1;i <= cnt;++i) if(dis[0][i] == 0) f = 1; if(f) printf("-1 "); else { memset(dp,0x3f,sizeof(dp)); for(rg int i = 0;i < cnt;++i) dp[1<<i][i] = dis[0][i+1]+t;//边界 for(rg int i = 0;i < (1<<cnt);++i)//枚举状态 { for(rg int j = 0;j < cnt;++j)//枚举最后一个修复的位置 { if(((i>>j)&1) == 0) continue;//如果当前状态j位置还没被修复，说明无法转移。 for(rg int k = 0;k < cnt;++k)//枚举新修复的位置。即当前状态下一个修复的位置 { if((i>>k)&1) continue;//显然i状态时必须要这个k位置还没被修复 dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k],dp[i][j]+dis[j+1][k+1]+t);//从j到k } } } LL ans = INF; for(rg int i = 0;i < cnt;++i) ans = min(ans,dp[(1<<cnt)-1][i]+dis[0][i+1]); printf("%lld ",ans); } system("pause"); return 0; }