第1题Stockbroker Grapevine要求最长路径的最小值所以要遍历比较多个两点间的距离所以用floyd具体代码如下#includeiostream #includevector using namespace std; int main() { int n; cin n; while (n) { vectorvectorintg(n1,vectorint(n1,1001)); int m; for (int i 1; i n; i) { g[i][i] 0; cin m; int to2,w2; for (int j 1; j m; j) { cin to2 w2; g[i][to2]w2; } } for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { g[i][j] min(g[i][j], g[i][k] g[k][j]); } } } int min1001; int s-1; for (int i 1; i n; i) { int max0; for (int j 1; j n; j) { if (g[i][j] max) max g[i][j]; } if (max min) { min max; s i; } } if (s -1)cout disjoint endl; else cout s min endl; cin n; } return 0; }第2题 树的直径我们知道从1个结点出发能达到的最远地方肯定是叶并且它是除了出发外最远的分支所以只需要遍历两次第1次找到相对最远的叶第2次从该叶遍历就能找到直径。这里用bfs,具体代码如下#includeiostream #includevector #includequeue using namespace std; vectorintarr[100001]; int sign[100001] { 0 }; int ans 0; int bfs(int a) { ans 0; int num0; for (int i 1; i 100001; i) sign[i] 0; sign[a] 1; queueintq; queueintturn; q.push(a); turn.push(0); while (!q.empty()) { int k q.front(); int t turn.front(); turn.pop(); q.pop(); for (int p : arr[k]) { if (!sign[p]) { sign[p] 1; num p; ans t 1; q.push(p); turn.push(t 1); } } } return num; } int main() { int n; cin n; int u, v; for (int i 1; i n; i) { cin u v; arr[u].push_back(v); arr[v].push_back(u); } int y bfs(1); bfs(y); cout ans; return 0; }第3题 Invitation Cards要求来回的最短路径和而且是单源的所以用dijkstra去的时候直接利用已知有向图就能得到起点到所有其它点的最短路径。而算回来的时候总不可能一个点一个点地去算这些点到起点的最短路径吧我们考虑是否可以转化成起点到其它点这直接构造反向图就可以了。具体看以下代码#includeiostream #includevector #includequeue using namespace std; struct node { int pos; int dis; }; struct cmp { bool operator()(node nod, node nod2) { return nod.dis nod2.dis; } }; int main() { int n; cin n; int p, q1; for (int t 0; t n; t) { cin p q1; int sum 0; int cnt 1; vectorinthead(1000001,-1); vectorintto(1000001, -1); vectorintcost(1000001, -1); vectorintnext(1000001, - 1); vectorinthead1(1000001, -1); vectorintto1(1000001, -1); vectorintcost1(1000001, -1); vectorintnext1(1000001, - 1); int from,to2, cost2; for (int i 1; i q1; i) { scanf(%d%d%d, from,to2, cost2); to[cnt] to2; cost[cnt] cost2; next[cnt] head[from]; head[from] cnt; to1[cnt] from; cost1[cnt] cost2; next1[cnt] head1[to2]; head1[to2] cnt; cnt; } priority_queuenode,vectornode,cmpq; vectorintdis(1000001, 1000000000); dis[1] 0; node nd; nd.pos 1; nd.dis 0; q.push(nd); while (!q.empty()) { nd q.top(); q.pop(); if (nd.dis dis[nd.pos])continue; for (int k head[nd.pos]; k ! -1; k next[k]) { if (dis[to[k]] dis[nd.pos] cost[k]) { dis[to[k]] dis[nd.pos] cost[k]; q.push({ to[k], dis[to[k]] }); } } } priority_queuenode, vectornode, cmpqq; vectorintdis2(1000001, 1000000000); dis2[1] 0; node nd2; nd2.pos 1; nd2.dis 0; qq.push(nd2); while (!qq.empty()) { nd2 qq.top(); qq.pop(); if (nd2.dis dis2[nd2.pos])continue; for (int k head1[nd2.pos]; k ! -1; k next1[k]) { if (dis2[to1[k]] dis2[nd2.pos] cost1[k]) { dis2[to1[k]] dis2[nd2.pos] cost1[k]; qq.push({ to1[k], dis2[to1[k]] }); } } } for (int i 1; i p; i) { sum dis[i]dis2[i]; } cout sum endl; } return 0; }第4题 战略游戏洛谷p2016)树形dp,根据一条边的两个顶点至少有1个士兵驻守来进行状态转移 具体代码如下#includeiostream #includevector #includequeue using namespace std; vectorintg[1500]; int dp[1500][2] { 0 }; void dfs(int a,int k) { dp[a][0] 0; dp[a][1] 1; for (int j : g[a]) { if (j k)continue; dfs(j, a); dp[a][0] dp[j][1]; dp[a][1] min(dp[j][0], dp[j][1]); } } int main() { int n; cin n; int fr, num,to; for (int i 0; i n; i) { cin fr num; for (int j 0; j num; j) { cin to; g[fr].push_back(to); g[to].push_back(fr); } } dfs(0, -1); cout min(dp[0][0],dp[0][1]); return 0; }第5题飞行路线洛谷P4568分层图思想将免费的乘坐机会表示为向上一层路径为0且为单向这样间接记录了已经使用了的免费次数。这里要注意一下我们主观地肯定认为免费次数用完最好但有种可能就是用不完。具体代码如下#includeiostream #includevector #includequeue using namespace std; struct node { int to; int w; friend bool operator (const node a, const node b) { return a.w b.w; } }; vectornodeg[120000]; vectorintdis(120000,1e7); void dij(int n,int s, int t,int k) { priority_queuenodeq; q.push({ s,0 }); dis[s] 0; while (!q.empty()) { node nd q.top(); q.pop(); for (node k : g[nd.to]) { if (dis[k.to] dis[nd.to] k.w) { dis[k.to] dis[nd.to] k.w; q.push({ k.to,dis[k.to] }); } } } int ans 1e7; for (int i 0; i k; i) { ans min(ans, dis[t i * n]); } cout ans endl; } int main() { int n, m, k; cin n m k; int s, t; cin s t; int fr, to, w; for (int i 0; i m; i) { cin fr to w; for (int j 0; j k; j) { g[frj*n].push_back({ toj*n,w }); g[toj*n].push_back({ frj*n,w }); g[fr j * n].push_back({ to (j1)* n,0 }); g[to j * n].push_back({ fr (j1)* n,0 }); } } dij(n,s, t,k); return 0; }第6题二叉苹果树洛谷P2015对于每个结点它如果还有子树对于每个子树它都有机会保留0到q个边所以遍历这所有可能得到最佳状态。具体代码如下#includeiostream #includevector using namespace std; int n, q; int d[101][101]; struct node{ int to; int w; }; vectornode g[101]; void dfs(int u, int fa){ for (node v:g[u]){ if (v.to fa) continue; dfs(v.to, u); for (int i q; i 0; i--) { for (int j 0; j i; j) { d[u][i] max(d[u][i], d[u][j] d[v.to][i - j - 1] v.w); } } } } int main() { scanf(%d%d, n, q); for (int i 1; i n; i){ int u, v, w; scanf(%d%d%d, u, v, w); g[u].push_back({v,w}); g[v].push_back({u,w}); } dfs(1, -1); printf(%d\n, d[1][q]); return 0; }