D:::::::::::::::::::::::::::::::::::合根植物（并查集）
题目描述
w 星球的一个种植园，被分成 m×n 个小格子（东西方向 m 行，南北方向 n 列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
输入描述
第一行，两个整数 m,n，用空格分开，表示格子的行数、列数（1≤m,n≤1000）。
接下来一行，一个整数 k (0≤k≤105 )，表示下面还有 k 行数据。
接下来 k 行，每行两个整数 a，b，表示编号为 a 的小格子和编号为 b 的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5×4 的小格子，编号：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
输出描述
输出植物数量。
输入输出样例
示例
输入
5 4 16 2 3 1 5 5 9 4 8 7 8 9 10 10 11 11 12 10 14 12 16 14 18 17 18 15 19 19 20 9 13 13 17
输出
5
样例说明
其合根情况参考下图：
运行限制
最大运行时间：2s
最大运行内存: 256M
#include <iostream> #include <algorithm> using namespace std; int m,n,k; int vis[1000005]; int fa[1000005]; int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } int ans; void jiaru(int x,int y){ int tx=find(x); int ty=find(y); if(tx!=ty){ fa[tx]=ty; } } int main(){ cin>>m>>n>>k; for(int i=0;i<=n*m;i++){ fa[i]=i; } for(int i=0;i<k;i++){ int a,b; cin>>a>>b; jiaru(a,b); } for(int i=1;i<=n*m;i++){ vis[find(i)]=1; } for(int i=1;i<=n*m;i++){ if(vis[i]){ ans+=1; } } cout<<ans; return 0; }
E:::::::::::::::::::::::::::::::::::修建公路(最小生成树，并查集)
题目描述
LL 城一共有 N 个小区。
小明是城市建设的规划者，他计划在城市修 M 条路，每修建一条路都要支付工人们相应的工钱（需要支付的工钱 = 路的长度）。
然而小明所拿到的经费并不够支付修建 M 条路的工钱，于是迫于无奈，他只能将计划改变为修建若干条路，使得 N 个小区之间两两联通。
小明希望尽量剩下更多的经费投入到别的项目中，因此请你通过程序帮他计算出完成计划所需的最低开销。
输入描述
输入第一行包含三个正整数N,M。
第 2 到 M+1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。
输出描述
输出占一行，包含一个整数，表示完成计划所需的最低开销。
若无法完成计划，则输出 -1−1。
输入输出样例
示例 1
输入
5 6 1 2 2 1 3 7 1 4 6 2 3 1 3 4 3 3 5 2
输出
8
运行限制
最大运行时间：3s
最大运行内存: 256M、
#include <iostream> #include <algorithm> using namespace std; int n,m; int fa[100005]; int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } struct node{ int qi,zhong; int juli; }; bool cmp(node x,node y){ return x.juli<y.juli; } long long ans; node g[300005]; int main(){ cin>>n>>m; //n个城市，m个规划 for(int i=1;i<=n;i++){ fa[i]=i; } for(int i=1;i<=m;i++){ cin>>g[i].qi>>g[i].zhong>>g[i].juli; } sort(g+1,g+m+1,cmp); for(int i=1;i<=m;i++){ int tx=find(g[i].qi); int ty=find(g[i].zhong); if(tx!=ty){ ans+=g[i].juli; fa[tx]=ty; } } int w=find(1); for(int i=1;i<=n;i++){ if(w!=find(i)){ cout<<-1; return 0; } } cout<<ans; return 0; }
F:::::::::::::::::::::::::::::::::::小明的背包2（完全背包）
题目描述
小明有一个容量为 V 的背包。
这天他去商场购物，商场一共有 N 种物品，第 ii 种物品的体积为 wi，价值为 vi，每种物品都有无限多个。
小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。
输入描述
输入第 1 行包含两个正整数 N,V，表示商场物品的数量和小明的背包容量。
第 2∼N+1 行包含 2 个正整数w,v，表示物品的体积和价值。
输出描述
输出一行整数表示小明所能获得的最大价值。
输入输出样例
示例 1
输入
5 20 1 6 2 5 3 8 5 15 3 3
输出
120
#include <iostream> #include <cmath> using namespace std; int n,v; int wi[1005]; int vi[1005]; int dp[1005][1005]; int main(){ cin>>n>>v; for(int i=1;i<=n;i++){ cin>>wi[i]>>vi[i]; //体积和价值 } for(int i=1;i<=n;i++){ for(int j=1;j<=v;j++){ dp[i][j]=dp[i-1][j]; if(j>=wi[i]){ dp[i][j]=max(dp[i-1][j],dp[i][j-wi[i]]+vi[i]); } } } cout<<dp[n][v]; return 0; }
G:::::::::::::::::::::::::::::::::::作物杂交（搜索）
题目描述
作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 1 至 N)，第 i 种作物从播种到成熟的时间为 Ti。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 N 种作物中的一种。
初始时，拥有其中 M 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。
如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，A × C → D。则最短的杂交过程为：
第 1 天到第 7 天 (作物 B 的时间)，A × B → C。
第 8 天到第 12 天 (作物 A 的时间)，A × C → D。
花费 12 天得到作物 D 的种子。
输入描述
输入的第 1 行包含 4 个整数 N,M,K,T，NN 表示作物种类总数 (编号 1 至 N)，MM 表示初始拥有的作物种子类型数量，KK 表示可以杂交的方案数，TT 表示目标种子的编号。
第 2 行包含 N 个整数，其中第 ii 个整数表示第 ii 种作物的种植时间 Ti (1≤Ti≤100)。
第 3 行包含 M 个整数，分别表示已拥有的种子类型 (1≤Kj≤M)，Kj 两两不同。
第 4 至 K + 3 行，每行包含 3 个整数 A,B,C，表示第 A 类作物和第 B 类作物杂交可以获得第 C 类作物的种子。
其中，1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤N, 保证目标种子一定可以通过杂交得到。
输出描述
输出一个整数，表示得到目标种子的最短杂交时间。
输入输出样例
示例
输入
6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6
输出
16
样例说明
第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。
第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。
第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。
第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。
总共花费 16 天。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
| C++ | 2s | 256M |
| C | 2s | 256M |
| Java | 3s | 256M |
| Python3 | 10s | 256M |
#include <iostream> #include <vector> using namespace std; const int maxn=0x3f3f3f3f; int tim[2010]; int dp[2010]; vector<pair<int, int> > zajiao[2010]; int f(int n){ if (dp[n]!=maxn) return dp[n]; for (int i=0;i<zajiao[n].size();++i){ int a=zajiao[n][i].first,b=zajiao[n][i].second; int tmp = max(f(a), f(b))+max(tim[a],tim[b]); dp[n]=min(dp[n],tmp); } return dp[n]; } int main(){ for (int i=0;i<2010;i++){ dp[i]=maxn; } int n,m,k,t; cin>>n>>m>>k>>t; for (int i=1;i<=n;++i){ cin>>tim[i]; } for (int i=1;i<=m;++i){ int j; cin>>j; dp[j]=0; } for (int i=1;i<=k;++i){ int a,b,c; cin>>a>>b>>c; zajiao[c].push_back(make_pair(a, b)); } f(t); cout<<dp[t]<<endl; return 0; }
