吉林大学23级数据结构上机实验（第7周）

A 去火车站

寒假到了，小明准备坐火车回老家，现在他从学校出发去火车站，CC市去火车站有两种方式：轻轨和公交车。小明为了省钱，准备主要以乘坐公交为主。CC市还有一项优惠政策，持学生证可以免费乘坐一站轻轨（但只能乘坐一站）。小明想尽快到达火车站，请编写程序为小明找到一条从学校到火车站最快的路线及换乘轻轨的方案。

假设换乘时间忽略不计，公交车与轻轨站点相同，但线路和速度不一定相同，所有线路都是双向的。可以第一站就乘坐轻轨，也可以最后一站乘坐轻轨，也可以在中间某站坐轻轨。如果乘坐轻轨和不乘坐轻轨到达火车站的时间相同，则无需换乘轻轨。最多坐一站轻轨。

输入格式:

输入包含多组数据。每组数据第一行为3个整数n、s和t，分别表示车站数（编号为1至n），小明学校所在的站和火车站所在的站。下一行为一个整数m，表示公交车的线路信息，接下来m行，每行为3个正整数a、b、c，表示公交车从a站到b站需要c分钟。下一行为一个整数k，表示轻轨的线路信息，接下来k行，每行为3个正整数x、y、z，表示轻轨从x站到y站需要z分钟。所有整数均不超过20000。

输出格式:

对每组数据输出2行。第1行为1个整数T，表示从学校到达火车站的最短时间；第2行为一个整数K，表示在站点K换乘轻轨，若有多个可能的换乘点，则输出编号最小者，如果无需换乘轻轨，则第二行输出“no metro”。

输入样例:

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

输出样例:

5
2
5
2

 思路：

这里给出两种做法，第一种就是老师题解的思路，正反跑一遍，然后一一比较大小差异。。

我们可以思考一下假设不是走1条轻轨，而是k条轻轨，这道题该怎么做。写题稍微多一点的朋友肯定知道k条边限制的题一般都是用分层图最短路去写，感兴趣的朋友可以去看看我写的另一篇博文分层图最短路，感觉有点像拆点，也有点像dp。。

法一：

#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
typedef pair<int, int>PII;
int h[2*N], e[2*N], w[2*N], ne[2*N], idx;
int dis1[N], dis2[N];
bool st1[N], st2[N];
bool flag;
int ans, cnt;
int n, m, k, s, t;
void init()
{ans = 0x3f3f3f3f;cnt = 0x3f3f3f3f;flag = 1;idx = 0;memset(st1, false, sizeof st1);memset(dis1, 0x3f, sizeof dis1);memset(dis2, 0x3f, sizeof dis2);memset(st2, false, sizeof st2);memset(h, -1, sizeof h);memset(e, 0, sizeof e);memset(w, 0, sizeof w);memset(ne, 0, sizeof ne);
}
void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstral(int u,int dis[],bool st[]) {priority_queue<PII, vector<PII>, greater<PII>>q;q.push({ 0,u });dis[u] = 0;while (q.size()) {auto p = q.top();q.pop();int v = p.second;if (st[v]) {continue;}st[v] = true;for (int i = h[v];~i;i = ne[i]) {int j = e[i];if (st[j]) {continue;}if (dis[j] > dis[v] + w[i]) {dis[j] = dis[v] + w[i];q.push({ dis[j],j});}}}
}
void solve()
{while (cin >> n >> s >> t) {init();cin >> m;for (int i = 1;i <= m;i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}dijkstral(s,dis1,st1);dijkstral(t, dis2, st2);ans = dis1[t];cin >> k;for (int i = 1;i <= k;i++) {int a, b, c;cin >> a >> b >> c;if (dis1[a] + c + dis2[b] < ans) {flag = 0;ans =  dis1[a] + c + dis2[b];cnt = a;}else if (dis1[a] + c + dis2[b] == ans) {cnt = min(a, cnt);}if (dis1[b] + c + dis2[a] < ans) {flag = 0;ans = dis1[b] + c + dis2[a];cnt = b;}else if (dis1[b] + c + dis2[a] == ans) {cnt = min(cnt, b);}}if (flag) {cout << dis1[t] << endl;cout << "no metro" << endl;}else {cout << ans << endl;cout << cnt << endl;}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
}

法二：

#include<bits/stdc++.h>
using namespace std;
const int N = 20010, M = 40010;
typedef pair<int, pair<int, int>>PII;
int h[N], e[M], ne[M], w[M], idx;
int h2[N], e2[M], ne2[M], w2[M], idx2;
int dis[N][2];
bool st[N][2];
int cnt[N];
int n, m, k, s, t;
int ans;
int f;
void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void add2(int a, int b, int c) {e2[idx2] = b, w2[idx2] = c, ne2[idx2] = h2[a], h2[a] = idx2++;
}
void dij()
{memset(dis, 0x3f, sizeof dis);memset(st, false, sizeof st);priority_queue<PII, vector<PII>, greater<PII>>q;q.push({ 0,{s,0} });dis[s][0] = 0;while (q.size()) {auto p = q.top();q.pop();int v = p.second.first;int u = p.second.second;if (st[v][u]) {continue;}st[v][u] = true;for (int i = h[v];~i;i = ne[i]) {int j = e[i];if (st[j][u]) {continue;}if (dis[j][u] > dis[v][u] + w[i]) {if (u == 1) {cnt[j] = cnt[v];}dis[j][u] = dis[v][u] + w[i];q.push({ dis[j][u],{j,u} });}}if (u + 1 <= 1) {for (int i = h2[v];~i;i = ne2[i]) {int j = e2[i];if (st[j][u + 1]) {continue;}if (dis[j][u + 1] > dis[v][u] + w2[i]) {dis[j][u + 1] = dis[v][u] + w2[i];cnt[j] = v;q.push({ dis[j][u + 1],{j,u + 1} });}else if (dis[j][u + 1] == dis[v][u] + w2[i]) {cnt[j] = min(cnt[j], v);//q.push({ dis[j][u + 1],{j,u + 1} });}}}}
}
void solve()
{while (cin >> n >> s >> t) {idx = 0;idx2 = 0;f = 0x3f3f3f3f;ans = 0x3f3f3f3f;memset(cnt, 0x3f, sizeof cnt);memset(e, 0, sizeof e);memset(ne, 0, sizeof ne);memset(w, 0, sizeof w);memset(h, -1, sizeof h);memset(e2, 0, sizeof e2);memset(ne2, 0, sizeof ne2);memset(w2, 0, sizeof w2);memset(h2, -1, sizeof h2);cin >> m;for (int i = 1;i <= m;i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}cin >> k;for (int i = 1;i <= k;i++) {int a, b, c;cin >> a >> b >> c;add2(a, b, c);}dij();if (dis[t][0] <= dis[t][1]) {cout << dis[t][0] << endl;cout << "no metro" << endl;}else {cout << dis[t][1] << endl;cout << cnt[t] << endl;}}}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
}

 

 B 联盟数目

艾迪是一家集团公司的老板，该集团包含n家公司，为了管理公司，艾迪会时常通过网络向各公司发送消息。各公司间的网络是单向的，每个公司都有一个分发列表，表示其能向哪些公司直接传达消息。例如A公司的分发列表为B、C，表示A可将消息直接传送给B和C（由于网络是单向的，B或C不一定能向A传送消息），这样艾迪若想向A、B、C公司发送消息，则只需向A发送消息即可，随后A可将消息传送到B和C。

为了便于管理各公司，艾迪打算将n家公司分成若干组，每组称为一个区域联盟，每组满足如下条件：组内的任意公司消息互相可达。即对于组内任意公司u和v，u可将消息传送到v（可由u直接传送到v，也可通过组内其他公司中转传送到v），v也可将消息传送到u。可以认为一个公司可以将消息传送给自己，即一个公司可以自成一组。

艾迪希望组的数量尽可能少，即在满足上述条件的情况下，每组包含的公司数目尽可能多。

现给定每个公司的分发列表，请编写程序告知艾迪，他的集团最少能分成多少组。

输入格式:

第一行包含一个整数T (1≤T≤100)表示数据组数。对于每组数据，第一行为一个整数n (2≤n≤100)，表示公司数目，公司编号为1到n。随后n行，第i行包含若干整数，表示第i个公司的分发列表，每行以0结尾。

输出格式:

对于每组数据，输出一行，为一个整数，表示组数。

输入样例:

3
5
2 4 3 0
4 5 0
0
0
1 0
3
2 0
0
2 1 0
3
2 0
3 0
0

输出样例:

3
3
3

 思路：

这题我们依旧提供两种方法，一个是Floyd，一个是tarjan。

讲真的我以前真不知道Floyd可以求强连通分量。。

可能是n3次方太可拍了。。

Floyd

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int dis[N][N];
bool st[N];
int n;
int ans;
void init()
{memset(dis, 0x3f, sizeof dis);memset(st, false, sizeof st);ans = 0;for (int i = 1;i <= n;i++) {dis[i][i] = 0;}
}
void solve()
{cin >> n;init();for (int i = 1;i <= n;i++) {int k;while (cin >> k && k != 0) {dis[i][k] = 1;}}for (int k = 1;k <= n;k++) {for (int i = 1;i <= n;i++) {for (int j = 1;j <= n;j++) {if (dis[i][j] > dis[i][k] + dis[k][j]) {dis[i][j] = dis[i][k] + dis[k][j];}}}}for (int i = 1;i <= n;i++) {if (st[i]) {continue;}st[i] = true;for (int j = i + 1;j <= n;j++) {if (st[j]) {continue;}if (dis[i][j] != 0x3f3f3f3f && dis[j][i] != 0x3f3f3f3f) {st[j] = true;}}ans++;}cout << ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {solve();}return 0;
}

tarjan：

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = N * N;
int h[N], e[M], ne[M], idx;
int scc_cnt, id[N], _size[N];
int dfn[N], low[N];
int stk[N], top;
bool in_stk[N];
int timestamp;
int n;
void init()
{timestamp = 0;scc_cnt = 0;top = 0;idx = 0;memset(h, -1, sizeof h);memset(e, 0, sizeof e);memset(ne, 0, sizeof ne);memset(id, 0 ,sizeof id);memset(_size, 0, sizeof _size);memset(dfn, 0, sizeof dfn);memset(stk, 0, sizeof stk);memset(low, 0, sizeof low);memset(in_stk, false, sizeof in_stk);
}
void add(int a, int b) {e[idx] = b, ne[idx] = h[a];h[a] = idx++;
}void tarjan(int u)
{dfn[u] = low[u] = ++timestamp;stk[++top] = u, in_stk[u] = true;for (int i = h[u];i != -1;i = ne[i]){int j = e[i];if (!dfn[j]) {tarjan(j);low[u] = min(low[u], low[j]);}else if (in_stk[j]) {low[u] = min(low[u], low[j]);}}if (dfn[u] == low[u]) {int y;scc_cnt++;do {y = stk[top--];in_stk[y] = false;id[y] = scc_cnt;_size[scc_cnt]++;} while (u != y);}
}void solve()
{init();cin >> n;for (int i = 1;i <= n;i++) {int k =-1;while (cin >> k && k != 0) {add(i, k);}}for (int i = 1;i <= n;i++) {if (dfn[i]) {continue;}else {tarjan(i);}}cout << scc_cnt << endl;}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {solve();}return 0;
}

这里的tarjan不需要这么麻烦，我只是写一个模板写多了。。

 C 社交网络

可以将n个QQ用户间的好友关系建模为一个包含n个顶点的无向图，顶点编号为1至n，每个顶点对应一个用户，若2个用户i和j是QQ好友，则在顶点i和j之间连接一条边，并根据用户间的亲密度对该边附以一个权值cij​。在该图中，可以利用两个顶点间的最短路径长度衡量两个用户的关系密切程度，也可以利用经过一个顶点的最短路径数目来衡量一个用户在关系网络中的影响力，具体地，我们定义用户k在QQ关系网络中的“影响力”为：

 

其中Nij​为顶点i到j的最短路径数目，Nijk​为顶点i到j的所有最短路径中经过顶点k的最短路径数目（上述二值可能超出int型范围，请使用long long类型）。Dij​表示i到j的最短路径长度。

现给定一个如上描述的无向图，请编写程序，计算每个顶点的“影响力”，假定给定的图是连通的。

输入格式:

输入第一行为两个正整数n和e，分别表示图的顶点数和边数，接下来e行表示每条边的信息，每行为3个正整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

n≤100，e≤5000，c≤1000，任意两点间的最短路径数目≤1010

输出格式:

输出为n行，每行一个实数，精确到小数点后3位，第i行为顶点i的影响力。

输入样例:

4 4
3 2 6
4 3 1
1 3 9
4 1 1

输出样例:

0.000
0.000
30.000
20.000

解释:

对于顶点1：边2-3、3-4、2-4的最短路径均不经过顶点1，故顶点1的影响力为0.

对于顶点3：
顶点1到2的最短路径共1条，长度为8，经过点3，顶点2到4的最短路径共1条，长度为7，经过点3，顶点1到4的最短路径共1条，但不经过点3。
故f(3)=D12​∗1+D24​∗1+D14​∗0+D21​∗1+D42​∗1+D41​∗0=8+7+0+8+7+0=30.000

提示:

若顶点a到顶点b有x条路径，点b到点c有y条路径，则a经过b到达c的路径有x*y条。

 思路：

这题是最简单的有没有人同感。。

就是简单的dijktra。。

只是一定要小心longlong相乘会越界，改成double就好了。

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
typedef long long LL;
typedef pair<LL, int>PII;
LL dis[N][N];
bool st[N][N];
int h[N], e[M], ne[M], w[M], idx;
LL cnt[N][N];
int n, m;
double ans[N];
void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstral(int u) {priority_queue<PII, vector<PII>, greater<PII>>q;q.push({ 0,u });dis[u][u] = 0;cnt[u][u] = 1;while (q.size()) {auto t = q.top();q.pop();int v = t.second;if (st[u][v]) {continue;}st[u][v] = true;for (int i = h[v];~i;i = ne[i]) {int j = e[i];if (st[u][j]) {continue;}if (dis[u][j] > dis[u][v] + w[i]) {dis[u][j] = dis[u][v] + w[i];cnt[u][j] = cnt[u][v];q.push({ dis[u][j],j});}else if (dis[u][j] == dis[u][v]+w[i]) {cnt[u][j] += cnt[u][v];q.push({ dis[u][j],j});}}}
}
void solve()
{cin >> n >> m;memset(st, false, sizeof st);memset(h, -1, sizeof h);memset(dis, 0x3f, sizeof dis);for (int i = 1;i <= m;i++) {int a, b, c;cin >> a >> b >> c;add(a, b, c);add(b, a, c);}for (int i = 1;i <= n;i++) {dijkstral(i);}for (int i = 1;i <= n;i++) {for (int j = 1;j <= n;j++) {for (int k = 1;k <= n;k++) {//cout << dis[j][k] << endl;//cout << cnt[j][k] << endl;if (j == i || k == i) {continue;}if (dis[j][k] == 0x3f3f3f3f||dis[j][i]==0x3f3f3f3f||dis[i][k]==0x3f3f3f3f) {continue;}if (cnt[j][i] == 0 || cnt[i][k]==0) {continue;}if (dis[j][k] != dis[j][i] + dis[i][k]) {continue;}//cout << i << " " << j << " " << k << endl;double x = cnt[j][i] * cnt[i][k];double y = x / cnt[j][k];ans[i] += y * dis[j][k];}}}for (int i = 1;i <= n;i++) {cout << fixed << setprecision(3) << ans[i] << endl;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);solve();return 0;
}