JLU数据结构荣誉课——第五次上机实验
7-1 图的深度优先搜索I (100 分)
无向图 G 有 n 个顶点和 m 条边。求图G的深度优先搜索树(森林)以及每个顶点的发现时间和完成时间。每个连通分量从编号最小的结点开始搜索，邻接顶点选择顺序遵循边的输入顺序。
在搜索过程中，第一次遇到一个结点，称该结点被发现；一个结点的所有邻接结点都搜索完，该结点的搜索被完成。深度优先搜索维护一个时钟，时钟从0开始计数，结点被搜索发现或完成时，时钟计数增1，然后为当前结点盖上时间戳。一个结点被搜索发现和完成的时间戳分别称为该结点的发现时间和完成时间。
输入格式:
第1行，2个整数n和m，用空格分隔，分别表示顶点数和边数， 1≤n≤50000， 1≤m≤100000.
第2到m+1行，每行两个整数u和v，用空格分隔，表示顶点u到顶点v有一条边，u和v是顶点编号，1≤u,v≤n.
输出格式:
第1到n行，每行两个整数di和fi，用空格分隔，表示第i个顶点的发现时间和完成时间1≤i≤n 。
第n+1行，1个整数 k ，表示图的深度优先搜索树(森林)的边数。
第n+2到n+k+1行，每行两个整数u和v,表示深度优先搜索树(森林)的一条边<u,v>，边的输出顺序按 v 结点编号从小到大。
作者 : 谷方明
单位: 吉林大学
代码长度限制:16 KB
时间限制:200 ms
内存限制:10 MB
输入样例:
在这里给出一组输入。例如：
6 5
1 3
1 2
2 3
4 5
5 6
输出样例:
在这里给出相应的输出。例如：
1 6
3 4
2 5
7 12
8 11
9 10
4
3 2
1 3
4 5
5 6
思路：==题目要看懂==。 1.每个连通分量要从最小的边开始：开循环从i=1开始DFS; 2.在搜索过程中，第一次遇到一个结点，称该结点被发现；一个结点的所有邻接结点都搜索完，该结点的搜索被完成：就是在进入DFS后另开始时间戳dfn[v]为++top，在该点DFS完全结束后令Last[v]=++top，最后统一输出就行。 3.第n+2到n+k+1行，每行两个整数u和v,表示深度优先搜索树(森林)的一条边<u,v>，边的输出顺序按 v 结点编号从小到大：利用sort函数将结构体数组排序，重载比较符号。
代码如下：
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
vector<int>mp[100001];
int visited[100001];
int dfn[100001];//开始时间戳
int Last[100001];//结束时间戳
int top = 0;//时间戳计数器
int top1 = 0;//边数计数器，与e数组配套
struct edge
{
int u;
int v;
bool operator<(const struct edge&a)const
{
return v < a.v;
}
}e[100001];
void DFS(int v)
{
if (visited[v])return;
else
{
visited[v] = 1;
dfn[v] = ++top;//开始时间戳
for (int i = 0; i < mp[v].size(); i++)
{
int k = mp[v][i];
if (!visited[k])
{
e[++top1].u = v;
e[top1].v = k;//存到边数组以供最后边的输出
DFS(k);
}
}
Last[v] = ++top;//结束时间戳
}
}
int main()
{
int m, n;
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++)
{
int from, to;
scanf("%d%d", &from, &to);
mp[from].push_back(to);
mp[to].push_back(from);
}//建图
for (int i = 1; i <= m; i++)
DFS(i);//循环DFS
for (int i = 1; i <= m; i++)
{
printf("%d %d\n", dfn[i], Last[i]);
}//打印时间戳
printf("%d\n", top1);
sort(e + 1, e + 1 + top1);//后边排序
for (int i = 1; i <= top1; i++)
{
printf("%d %d\n", e[i].u, e[i].v);
}
return 0;
}
反思：我觉得这题难点在读题。
7-2 圆 (100 分)
二维平面上有n 个圆。请统计：这些圆形成的不同的块的数目。
圆形成的块定义如下： （1）一个圆是一个块； （2）若两个块有公共部分（含相切），则这两个块形成一个新的块，否则还是两个不同的块。
输入格式:
第1行包括一个整数n，表示圆的数目，n<=8000。
第2到n+1行，每行3 个用空格隔开的数x，y，r。（x，y）是圆心坐标，r 是半径。所有的坐标及半径都是不大于30000 的非负整数。
输出格式:
1个整数，表示形成的块的数目。
输入样例:
在这里给出一组输入。例如：
2
0 0 1
1 0 2
输出样例:
在这里给出相应的输出。例如：
1
作者：谷方明 单位：吉林大学 代码长度限制：16 KB 时间限制：500 ms 内存限制：5 MB
思路：并查集为最优解，每输入一个⚪就和前面的⚪判断是否相交或者相切，如果father不同，就Union两者，这时不能break，因为每个⚪可以和多个⚪相交，而将多个块连成一个块。
代码如下：
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
struct circle
{
int x;
int y;
int r;
}c[10000];
vector<int>mp[10000];
int father[10000];
int find(int v)
{
if (father[v] == v)
return v;
else
return find(father[v]);
}//找代表元
void Union(int x,int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
{
father[fx] = fy;
}
}//合并算法
int main()
{
int m;
scanf("%d", &m);
scanf("%d%d%d", &c[1].x, &c[1].y, &c[1].r);
father[1] = 1;
for (int i = 2; i <= m; i++)
{
scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].r);
father[i] = i;
for (int j = i-1; j >= 1; j--)
{
if ((long long)(c[i].r + c[j].r)*(c[i].r + c[j].r) >=
(long long)((c[i].x - c[j].x)*(c[i].x - c[j].x) +
(c[i].y - c[j].y)*(c[i].y - c[j].y)))//这里要强制类型转换要不然某个10的样例点过不去。
{
Union(j, i);
}
}
}//一边循环一边插入判断。
int count1 = 0;
for (int i = 1; i <= m; i++)
{
if (father[i] == i)count1++;
}
printf("%d", count1);
return 0;
}
反思：注意long long。
7-3 供电 (100 分)
要给N个地区供电。每个地区或者建一个供电站，或者修一条线道连接到其它有电的地区。试确定给N个地区都供上电的最小费用。
输入格式:
第1行，两个个整数 N 和 M , 用空格分隔，分别表示地区数和修线路的方案数，1≤N≤10000，0≤M≤50000。
第2行，包含N个用空格分隔的整数P[i]，表示在第i个地区建一个供电站的代价，1 ≤P[i]≤ 100,000，1≤i≤N 。
接下来M行，每行3个整数a、b和c，用空格分隔，表示在地区a和b之间修一条线路的代价为c，1 ≤ c ≤ 100,000，1≤a,b≤N 。
输出格式:
一行，包含一个整数， 表示所求最小代价。
输入样例: 在这里给出一组输入。例如：
4 6
5 4 4 3
1 2 2
1 3 2
1 4 2
2 3 3
2 4 3
3 4 4
输出样例:
在这里给出相应的输出。例如：
9
作者：谷方明 单位：吉林大学 代码长度限制：16 KB 时间限制：500 ms 内存限制：10 MB
思路：本题很显然是一道最小生成树问题，但是即存在边权又存在点权，所以我们要将n个点的点权都转换成边权，然后再采用最小生成树的算法来得到支撑子树，然后将每条边权相加(仅需要遍历)，得到结果。建议使用prim的堆优化或者是kruskal算法，反正我的非堆优化Prim算法O(n^2^)没有过。🙃
代码如下：
//用的是kruskal算法，建立边表。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct Edge
{
int from;
int to;
int value;
bool operator < (const struct Edge &a)const
{
return value < a.value;
}//重载比较函数，因为要对边进行排序。
}edge;
edge Vertex[100001];
int father[100001];//用到并查集
edge TE[100001];//存最小生成树的边，其实可以开成数组，
//我写的模板原本是这样写的
int top = 0;//TE配套的计数器
int find1(int v)
{
if (father[v] == v)
return v;
return find1(father[v]);
}//寻找代表元
void Union(int x, int y)
{
int fx = find1(x);
int fy = find1(y);
if (fx != fy)
father[fy] = fx;
}//合并
int main()
{
int m, n;
scanf("%d%d", &m, &n);
//建表
for (int i = 1; i <= m; i++)
{
scanf("%d", &Vertex[i].value);
Vertex[i].from = 0;
Vertex[i].to = i;
}//将虚结点的边放到边表里面
for (int i = m+1; i <= n+m; i++)
{
scanf("%d%d%d", &Vertex[i].from,
&Vertex[i].to, &Vertex[i].value);
}//将正常边放到边表里面
for (int i = 1; i <= m; i++)
{
father[i] = i;
}
//kruskal核心算法
sort(Vertex + 1, Vertex+n+1+m);
for (int i = 1; i <= n+m; i++)
{
int from = Vertex[i].from;
int to = Vertex[i].to;
if (find1(from) != find1(to))
{
TE[++top] = Vertex[i];//找到合适的边，然后记到TE边表中
Union(from, to);//合并
}
}//就这么一点点
int sum = 0;
for (int i = 1; i <= top; i++)
{
sum += TE[i].value;
}
printf("%d", sum);
return 0;
}
下面是Prim算法非堆优化(70分的)，也是书上二维码的模板的改编:
代码如下：
#include<iostream>
#include<stack>
#include<queue>
#include<cstdio>
using namespace std;
struct Edge
{
int VerAdj;
Edge* link;
int value;
};
struct Vertex
{
int VerName;
Edge *adjacement;
};
class Graph_list
{
private:
Vertex* head;
int graphsize;
public:
Graph_list();
~Graph_list();
void Prim();
int visited[100001];
int vex[100001];
int Lowcost[100001];
const int MAX = 2100000000;
};
Graph_list G;//创建对象
Graph_list::Graph_list()//图为有向图邻接表示法，无向图就把注释去掉
{
head = new Vertex[10001];
int from, to, weight;
int e;
scanf("%d", &graphsize);
for (int i = 0; i <= graphsize; i++)
{
head[i].VerName = i;
head[i].adjacement = NULL;
}
cin >> e;
for (int i = 1; i <= graphsize; i++)
{
scanf("%d",&weight);
to = i;
from = 0;
Edge*p = new Edge;
p->link = NULL;
p->VerAdj = to;
p->value = weight;
Edge*p1 = new Edge;
p1->link = NULL;
p1->VerAdj = from;
p1->value = weight;
Edge*q1 = head[from].adjacement;
Edge*q2 = head[to].adjacement;
if (q1 == NULL)
{
head[from].adjacement = p;
}
else
{
while (q1->link != NULL)
{
q1 = q1->link;
}
q1->link = p;
}
if (q2 == NULL)
head[to].adjacement = p1;
else
{
while (q2->link != NULL)
q2 = q2->link;
q2->link = p1;
}
}//这是虚结点的录入
for (int i = 1; i <= e; i++)
{
scanf("%d%d%d", &from, &to,&weight);
Edge*p = new Edge;
p->link = NULL;
p->VerAdj = to;
p->value = weight;
Edge*p1 = new Edge;
p1->link = NULL;
p1->VerAdj = from;
p1->value = weight;
Edge*q1 = head[from].adjacement;
Edge*q2 = head[to].adjacement;
if (q1 == NULL)
{
head[from].adjacement = p;
}
else
{
while (q1->link != NULL)
{
q1 = q1->link;
}
q1->link = p;
}
if (q2 == NULL)
head[to].adjacement = p1;
else
{
while (q2->link != NULL)
q2 = q2->link;
q2->link = p1;
}
}//这是实结点的录入
}
Graph_list::~Graph_list()
{
for (int i = 0; i <= graphsize; i++)
{
Edge*p = head[i].adjacement;
while (p != NULL)
{
head[i].adjacement = p->link;
delete p;
p = head[i].adjacement;
}
}
delete[] head;
}//析构~
void Graph_list::Prim()
{
for (int i = 0; i <= graphsize; i++)
{
Lowcost[i] = MAX;
vex[i] = -1;
visited[i] = 0;
}
visited[0] = 1; Lowcost[0] = 0;
Edge*p = head[0].adjacement;
for (; p; p = p->link)
{
Lowcost[p->VerAdj] = p->value;
vex[p->VerAdj] = 1;
}
for (int j = 0; j < graphsize; j++)
{
int MIN = MAX; int u = 0;
for (int i = 0; i <= graphsize; i++)
{
if (Lowcost[i] < MIN&&visited[i] == 0)
{ MIN = Lowcost[i]; u = i; }
}
visited[u] = 1;
p = head[u].adjacement;
for (; p; p = p->link)
{
int k = p->VerAdj;
if (Lowcost[k] > p->value&&visited[k] == 0)
{
vex[k] = u; Lowcost[k] = p->value;
}
}
}
int sum = 0;
for (int i = 0; i <= graphsize; i++)
{
sum += Lowcost[i];
}
printf("%d", sum);
}//prim算法
int main()
{
G.Prim();
return 0;
}
反思：kruskal太香了😋。
7-4 发红包 (100 分)
新年到了，公司要给员工发红包。员工们会比较获得的红包，有些员工会有钱数的要求，例如，c1的红包钱数要比c2的多。每个员工的红包钱数至少要发888元，这是一个幸运数字。
公司想满足所有员工的要求，同时也要花钱最少，请你帮助计算。
输入格式:
第1行，两个整数n和m(n<=10000,m<=20000)，用空格分隔，分别代表员工数和要求数。
接下来m行，每行两个整数c1和c2，用空格分隔，表示员工c1的红包钱数要比c2多，员工的编号1~n 。
输出格式:
一个整数，表示公司发的最少钱数。如果公司不能满足所有员工的需求，输出-1.
输入样例:
在这里给出一组输入。例如：
2 1
1 2
输出样例:
在这里给出相应的输出。例如：
1777
思路：本题为典型拓扑排序题目，按照奖金大小来建立AOE网，然后不用管出度，在有环的条件下输出-1。 方法： 1.判断有环：可以在遍历过程中判断点的入队次数，如果没有都入队，那么就是有环。 2.更新员工的红包金额：在每一次更新中要确保取当原金额和规定比某人多的金额+1哪个数字大，将红包钱数赋予该最大值。
代码如下：
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int Red_Envelope[100001];//红包钱数
int ru[100001];//入度记录数
vector<int>mp[100001];//邻接链表
queue<int>Q;//TopOrder使用的队列
int sum = 0;//钱数总和
void TopOrder(int N)
{
int n = 0;
while (!Q.empty())
{
int k = Q.front();
Q.pop();
n++;
for (int i = 0; i < mp[k].size(); i++)
{
int q = mp[k][i];
Red_Envelope[q] =
max(Red_Envelope[q],Red_Envelope[k] + 1);
//容易出错
if (--ru[q] == 0)
{
Q.push(q);
sum += Red_Envelope[q];
}
}
}
if (n == N)
printf("%d", sum);
else printf("-1");
}//拓扑排序
int main()
{
int m, n;
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++)
{
int from, to;
scanf("%d%d", &from, &to);
mp[from].push_back(to);
ru[to]++;
}//建图，有向图
for (int i = 1; i <= m; i++)
{
if (ru[i] == 0)
{ Q.push(i); Red_Envelope[i] = 888; sum += 888; }
//拓扑排序预备
}
if (Q.size() == 0)
{
printf("-1"); return 0;
}//如果直接遇到环
else
TopOrder(m);//拓扑排序
return 0;
}
反思：要注意更新红包钱数时的操作。(已经标注)