A题： 题意：
实验室里原先有一台电脑(编号为1)，最近氪金带师咕咕东又为实验室购置了N-1台电脑，编号为2到N。每台电脑都用网线连接到一台先前安装的电脑上。但是咕咕东担心网速太慢，他希望知道第i台电脑到其他电脑的最大网线长度，但是可怜的咕咕东在不久前刚刚遭受了宇宙射线的降智打击，请你帮帮他。
文章图片
Input
输入文件包含多组测试数据。对于每组测试数据，第一行一个整数N (N<=10000)，接下来有N-1行，每一行两个数，对于第i行的两个数，它们表示与i号电脑连接的电脑编号以及它们之间网线的长度。网线的总长度不会超过10^9，每个数之间用一个空格隔开。
Output
对于每组测试数据输出N行，第i行表示i号电脑的答案 (1<=i<=N).
Sample Input
5
1 1
2 1
3 1
1 1
Sample Output
3
2
3
4
4
思路：
这个题，是涉及求树的直径问题。如何求树的直径问题，从一个点求它可以到达的最远的顶点，是先到达这个点可以到达的最远的顶点v1或v2,然后再从v1或者v2到达最远的顶点，那么最远距离是这二者之一。
所以，本题从用了一个领接数组用来记录一个顶点可以到达的节点有些什么，visit数组用来记录是否到达过这个顶点，distance1用来记录从1顶点开始可以到达的最远的顶点的距离，并把最远的顶点记录为v1，然后再从v1出发用distance2记录从v1可以到达最远的顶点的距离，并把最远的点记录为v2，再从v2出发用Distance3记录从v2可以到达最远的顶点距离，将distance3和distance2的每个顶点的距离作比较，最大值最远距离。
代码：
#include
#include
using namespace std;
struct edge
{
int v;
long long int z;
edge(int v1,long long int z1)
{
v = v1;
z = z1;
}
} ;
vector G[10001];
bool visit[10001];
long long int distance1[10001];
long long int distance2[10001];
long long int distance3[10001];
dfs(int v,long long int dis[],long long int distance)
{
dis[v] = distance;
visit[v] = 1;
for(int i=0;
i>n)
{
for(int i=0;
i<10001;
i++)
{
G[i].clear();
visit[i]=0;
distance1[i]=0;
distance2[i] = 0;
distance3[i] = 0;
}
for(int i = 2;
i<=n;
i++)
{
int v;
long long int z;
cin>>v>>z;
G[i].push_back(edge(v,z));
G[v].push_back(edge(i,z));
}
dfs(1,distance1,0);
int maxindex = 1;
int maxlength = 0;
for(int i=1;
i<=n;
i++)
{
if(distance1[i]>maxlength)
{
maxlength = distance1[i];
maxindex = i;
}
}
int v1 = maxindex;
for(int i=0;
i<=n;
i++)
visit[i ] = 0;
dfs(v1,distance2,0);
maxindex = 1;
maxlength = 0;
for(int i=1;
i<=n;
i++)
{
if(distance2[i]>maxlength)
{
maxlength = distance2[i];
maxindex = i;
}
}
int v2 = maxindex;
for(int i = 0;
i<=n;
i++)
visit[i]=0;
dfs(v2,distance3,0);
for(int i=1;
i<=n;
i++)
{
int ans = distance2[i];
if(distance2[i] < distance3[i])
ans = distance3[i];
cout< B题 题意：
新型冠状病毒肺炎（Corona Virus Disease 2019，COVID-19），简称“新冠肺炎”，是指2019新型冠状病毒感染导致的肺炎。
如果一个感染者走入一个群体，那么这个群体需要被隔离！
小A同学被确诊为新冠感染，并且没有戴口罩！！！！！！
危！！！
时间紧迫！！！！
需要尽快找到所有和小A同学直接或者间接接触过的同学，将他们隔离，防止更大范围的扩散。
众所周知，学生的交际可能是分小团体的，一位学生可能同时参与多个小团体内。
请你编写程序解决！戴口罩！！
Input
多组数据，对于每组测试数据：
第一行为两个整数n和m（n = m = 0表示输入结束，不需要处理），n是学生的数量，m是学生群体的数量。0 < n <= 3e4 ， 0 <= m <= 5e2
学生编号为0~n-1
小A编号为0
随后，m行，每行有一个整数num即小团体人员数量。随后有num个整数代表这个小团体的学生。
Output
输出要隔离的人数，每组数据的答案输出占一行
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
思路：
上个学期学习数据结构的时候也写过并查集，并查集的思想比较好理解，最关键的是路径压缩，以减少事假复杂度。
代码：
#include using namespace std;
int stu[30000];
int ank[30000];
void init(int n)
{
for (int i = 0;
i < n;
i++)
{
stu[i] = i;
ank[i] = 1;
}
}int find(int x)
{
return stu[x] == x ? x : stu[x] = find(stu[x]);
}bool unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return false;
if (ank[x] > ank[y])
{
stu[y] = x;
ank[x] = (ank[y] += ank[x]);
}
else
{
stu[x] = y;
ank[y] = (ank[x] += ank[y]);
}
return true;
}
int main()
{
int n, m;
while (1)
{
cin >> n >> m;
if (n == 0 && m == 0)
break;
init(n);
for (int i = 0;
i < m;
i++)
{
int num;
cin >> num;
int a[num];
for (int j = 0;
j < num;
j++)
cin >> a[j];
for (int j = 1;
j < num;
j++)
unite(a[j - 1], a[j]);
}
cout << ank[find(0)] << endl;
}
} C题 题意：
东东在老家农村无聊，想种田。农田有 n 块，编号从 1~n。种田要灌氵
众所周知东东是一个魔法师，他可以消耗一定的 MP 在一块田上施展魔法，使得黄河之水天上来。他也可以消耗一定的 MP 在两块田的渠上建立传送门，使得这块田引用那块有水的田的水。 (1<=n<=3e2)
黄河之水天上来的消耗是 Wi，i 是农田编号 (1<=Wi<=1e5)
建立传送门的消耗是 Pij，i、j 是农田编号 (1<= Pij <=1e5, Pij = Pji, Pii =0)
东东为所有的田灌氵的最小消耗
Input
第1行：一个数n
第2行到第n+1行：数wi
第n+2行到第2n+1行：矩阵即pij矩阵
Output
东东最小消耗的MP值
Example Input
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
Output
9
思路：
这道题，可以变为求n+1个节点的生成的最小生成树。加入0这个起始点，求以这个节点为根节点的最小生产树，用kruskal算法求解，运用了小根堆，小根堆的排序要重载，因为每次取的是剩下的所有边里权重最小的边值，用小根堆算法可以把时间复杂度降到O（nlogn),同时使用了并查集的思想解决问题，压缩路径。
代码：
#include
#include
using namespace std;
int n;
int tot;
int e[301][301];
int stu[301];
int ank[301];
void init(int n)
{
for (int i = 0;
i <= n;
i++)
{stu[i] = i;
nk[i] = 1;
}
}
int find(int x)
{
return stu[x] == x ? x : stu[x] = find(stu[x]);
}bool unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return false;
if (ank[x] > ank[y])
{
stu[y] = x;
ank[x] = (ank[y] += ank[x]);
}
else
{
stu[x] = y;
ank[y] = (ank[x] += ank[y]);
}
return true;
}struct edge
{
int v, w;
int z;
edge(int v1 = 0, int w1 = 0, int z1 = 0)
{
v = v1, w = w1, z = z1;
}
};
struct cmp
{
bool operator () (edge a, edge b)
{
return a.z > b.z;
}
};
priority_queue, cmp> p;
void kruskal()
{
tot = 0;
for (int i = 0;
i <= n;
i++)
for (int j = i + 1;
j <= n;
j++)
{
edge theEdge(i, j, e[i][j]);
p.push(theEdge);
} init(n);
for (int i = 0;
i < n;
i++) //共取n条边
{
edge theEdge = p.top();
p.pop();
int a = theEdge.v, b = theEdge.w;
if (find(a) != find(b)) //不构成环路
{
tot = tot + theEdge.z;
unite(a, b);
}
else i--;
}
cout << tot << endl;
}
int main()
{
cin >> n;
e[0][0] = 0;
for (int i = 1;
i <= n;
i++)
{
int w;
cin >> w;
e[i][0] = w, e[0][i] = w;
}
for (int i = 1;
i <= n;
i++)
for (int j = 1;
j <= n;
j++)
cin >> e[i][j];
kruskal();
} D题 题意：
文章图片
思路：
其实如果以前做这个题，我绝对懵逼不知道怎么下手，听了助教讲以后可以用最小生成树算法来解决，就好理解很多，其实这个题与C题很像，改几个参数就可以了。总结一下，其实很多题做起来要有思路以及巧思路来做。
【程序设计【Week6】作业】代码：
#include
#include
using namespace std;
int n, m, root;
int tot = 0;
int stu[60001];
int ank[60001];
void init(int n)
{
for (int i = 0;
i <= n;
i++)
{stu[i] = i;
ank[i] = 1;
}
}
int find(int x)
{
return stu[x] == x ? x : stu[x] = find(stu[x]);
}bool unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return false;
if (ank[x] > ank[y])
{
stu[y] = x;
ank[x] = (ank[y] += ank[x]);
}
else
{
stu[x] = y;
ank[y] = (ank[x] += ank[y]);
}
return true;
}struct edge
{
int v, w;
int z;
edge(int v1 = 0, int w1 = 0, int z1 = 0)
{
v = v1, w = w1, z = z1;
}
};
edge e[100001];
struct cmp
{
bool operator () (edge a, edge b)
{
return a.z > b.z;
}
};
priority_queue, cmp> p;
void kruskal()
{
//tot=0;
for (int i = 1;
i <= m;
i++)
p.push(e[i]);
init(n);
for (int i = 0;
i < n - 1;
i++) //共取n条边
{
edge theEdge = p.top();
p.pop();
int a = theEdge.v, b = theEdge.w;
if (find(a) != find(b)) //不构成环路
{
if (tot < theEdge.z)
tot = theEdge.z;
unite(a, b);
}
else i--;
}
cout << tot << endl;
}
int main()
{
cin >> n >> m >> root;
for (int i = 1;
i <= m;
i++)
{
int v, w, z;
cin >> v >> w >> z;
e[i].v = v;
e[i].w = w;
e[i].z = z;
}
kruskal();
} 
