JLU数据结构荣誉课——第四次上机实验
7-1 连通分量 (100 分)
无向图 G 有 n 个顶点和 m 条边。求 G 的连通分量的数目。
输入格式:
第1行，2个整数n和m，用空格分隔，分别表示顶点数和边数， 1≤n≤50000， 1≤m≤100000.
第2到m+1行，每行两个整数u和v，用空格分隔，表示顶点u到顶点v有一条边，u和v是顶点编号，1≤u,v≤n.
输出格式:
1行，1个整数，表示所求连通分量的数目。
输入样例:
在这里给出一组输入。例如：
6 5
1 3
1 2
2 3
4 5
5 6
输出样例:
在这里给出相应的输出。例如：
2
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 10 MB
思路：利用并查集，最后统计并查集个数，及father数组中存的值依旧为零的元素，得到答案。
#include<cstdio>
using namespace std;
int father[100001];
int find(int v)
{
if (father[v] == 0)
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, n;
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++)
{
int pre, aft;
scanf("%d%d", &pre, &aft);
Union(pre, aft);
}
int count1 = 0;
for (int i = 1; i <= m; i++)
{
if (father[i] == 0)
count1++;
}
printf("%d\n", count1);
return 0;
}
7-2 整数拆分 (100 分)
整数拆分是一个古老又有趣的问题。请给出将正整数 n 拆分成 k 个正整数的所有不重复方案。例如，将 5 拆分成 2 个正整数的不重复方案，有如下2组：(1，4)和(2，3)。注意(1，4) 和(4，1)被视为同一方案。每种方案按递增序输出，所有方案按方案递增序输出。
输入格式:
1行，2个整数n和k，用空格分隔， 1≤k≤n≤50.
输出格式:
若干行，每行一个拆分方案，方案中的数用空格分隔。
最后一行，给出不同拆分方案的总数。
输入样例:
在这里给出一组输入。例如：
5 2
输出样例:
在这里给出相应的输出。例如：
1 4
2 3
2
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 100 ms 内存限制 1 MB
思路：利用回溯算法，在calulate函数中，传入当前限定最大值Max，传入当前计算深度， 传入在减掉分解完成的数字，当深度达到所给k值时输出一组数据，然后回溯进行再次输出。
#include<cstdio>
using namespace std;
int n, k, sum = 0;
int numway[51]; int top = 1;
void output()
{
for (int i = 1; i <= k - 1; i++)
printf("%d ", numway[i]);
printf("%d\n", numway[k]);
}
void calulate(int deep, int Max, int number)
{
int t = number / (k - deep + 1);
if (deep == k)
{
numway[deep] = number;
output();
sum++;
}
else
for (int i = Max; i <= t; i++)
{
numway[top] = i;
top++;
calulate(deep + 1, i, number - i);
}
top--;
}
int main()
{
//cin >> n >> k;
scanf("%d%d", &n, &k);
calulate(1, 1, n);
printf("%d\n", sum);
}
7-3 数字变换 (100 分)
利用变换规则，一个数可以变换成另一个数。变换规则如下：（1）x 变为x+1；（2）x 变为2x；（3）x 变为 x-1。给定两个数x 和 y，至少经过几步变换能让 x 变换成 y.
输入格式:
1行，2个整数x和y，用空格分隔， 1≤x,y≤100000.
输出格式:
第1行，1个整数s，表示变换的最小步数。
第2行，s个数，用空格分隔，表示最少变换时每步变换的结果。规则使用优先级顺序: （1），（2），（3）。
输入样例:
在这里给出一组输入。例如：
2 14
输出样例:
在这里给出相应的输出。例如：
4
3 6 7 14
作者` `谷方明` `单位` `吉林大学` `代码长度限制` `16 KB` `时间限制` `100 ms` `内存限制` `5 MB
思路：bfs的应用，比较抽象，也是每个数值出队入队一次，每次循环弹出头接结点，对 三种情况进行计算，在判断该元素是否入过队后，进行入队操作。 注意：入队元素定义为数对（当前元素值，计算出当前值的前一个值）方便寻找路径。
代码如下：
#include<cstdio>
#include<queue>
using namespace std;
int mark[200005];//标记数组，标记是否已经被计算出来，放入过队列中
int mark1[100001];//存取该下表值第一次被计算出来的值
int stand[100001];//倒序存储每一步计算值的结果
int main()
{
int m, n;
scanf_s("%d%d", &m, &n);
queue<pair<int,int> >a;//建立队列。
a.push(make_pair(m,m));
mark[m] = 1;
while (a.front().first != n)
{
int step = a.front().second;
int num = a.front().first;
mark1[num] = step;
a.pop();
if (mark[num + 1] != 1&&num+1<100001)
{
a.push(make_pair(num + 1,num));
mark[num + 1] = 1;
}
if (mark[num * 2] != 1&&num*2<100001)
{
a.push(make_pair(num * 2,num));
mark[num * 2] = 1;
}
if (mark[num-1] != 1&&num-1>=0)
{
a.push(make_pair(num - 1, num));
mark[num - 1] = 1;
}
}
int step = a.front().second;
int num = a.front().first;
mark1[num] = step;
mark[num] = 1;
int N = n;
int j = 1;
while (N != m)
{
stand[j++] = N;
N = mark1[N];
}
printf("%d\n", j - 1);
for (int i = j - 1; i >= 1; i--)
{
printf("%d%c", stand[i],i==1?'\n':' ');
}
return 0;
}
7-4 旅行 I (100 分)
五一要到了,来一场说走就走的旅行吧。当然，要关注旅行费用。由于从事计算机专业，你很容易就收集到一些城市之间的交通方式及相关费用。将所有城市编号为1到n，你出发的城市编号是s。你想知道，到其它城市的最小费用分别是多少。如果可能，你想途中多旅行一些城市，在最小费用情况下，到各个城市的途中最多能经过多少城市。
输入格式:
第1行，3个整数n、m、s，用空格分隔，分别表示城市数、交通方式总数、出发城市编号， 1≤s≤n≤10000, 1≤m≤100000 。
第2到m+1行，每行三个整数u、v和w，用空格分隔，表示城市u和城市v的一种双向交通方式费用为w ， 1≤w≤10000。
输出格式:
第1行，若干个整数Pi，用空格分隔，Pi表示s能到达的城市i的最小费用，1≤i≤n，按城市号递增顺序。
第2行，若干个整数Ci，Ci表示在最小费用情况下，s到城市i的最多经过的城市数，1≤i≤n，按城市号递增顺序。
输入样例:
在这里给出一组输入。例如：
5 5 1
1 2 2
1 4 5
2 3 4
3 5 7
4 5 8
输出样例:
在这里给出相应的输出。例如：
0 2 6 5 13
0 1 2 1 3
作者 谷方明 单位 吉林大学 代码长度限制 16 KB 时间限制 1000 ms 内存限制 10 MB
思路：利用Dijstra算法来跑最短路，采用普通堆优化，经过的城市在松弛处更新。
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const long long MAX = 1000000000;
int start;
struct Edge
{
int VerAdj;
int money;
int cost;
Edge*link;
};
struct Vertex
{
int VerName;
Edge* adjacement;
};
class Graph_list
{
private:
Vertex *head;
int graphsize;
int begin;
int after;
public:
Graph_list();
~Graph_list();
void Djistra();
};
Graph_list::Graph_list()//建图
{
head = new Vertex[100001];
int from, to;
int e, dist1, money;
cin >> graphsize;
for (int i = 1; i <= graphsize; i++)
{
head[i].VerName = i;
head[i].adjacement = NULL;
}
cin >> e;
//cin >> start;
cin >> begin ;
for (int i = 1; i <= e; i++)
{
cin >> from >> to >> dist1;
Edge*p = new Edge;
p->link = NULL;
p->cost = dist1;
p->VerAdj = to;
Edge*p1 = new Edge;
p1->link = NULL;
p1->cost = dist1;
p1->VerAdj = from;
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 = 1; 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::Djistra()//算法核心
{
long long dist[10001];
int visited[10001] = { 0 };
int count1[10001] = { 0 };
for (int i = 1; i <=graphsize; i++)
{
dist[i] = MAX;
}
dist[begin] = 0;
int midest = 0;
int u = 0;
Edge*p = NULL;
int k = 0;
priority_queue<pair<int, int> >q;
q.push(make_pair(0,begin));
while (!q.empty())
{
u = q.top().second;
q.pop();
if (visited[u])
continue;
visited[u] = 1;
for (p = head[u].adjacement; p; p = p->link)
{
k = p->VerAdj;
if (dist[k] > dist[u] + p->cost)
{
dist[k] = dist[u] + p->cost;
//money_all[k] = money_all[u] + p->money;
q.push(make_pair(-dist[k],k));
if (count1[k] == 0)
count1[k]++;
//(count1[k]<=count1[u]+1)
count1[k]=count1[u]+1;
}
else if(dist[k] == dist[u] + p->cost)
{
if(count1[k]<count1[u]+1)
count1[k]=count1[u]+1;
}
}
}
for (int i = 1; i <= graphsize-1; i++)
{
printf("%lld ", dist[i]);
}
printf("%lld\n", dist[graphsize]);
for (int i = 1; i <= graphsize-1; i++)
{
printf("%d ", count1[i]);
}
printf("%d\n", count1[graphsize]);
}
int main()
{
Graph_list G;
G.Djistra();
return 0;
}