【作业向】程序设计思维与实践 Week7 作业

发表于 | 分类于 ，
字数统计: 2.8k | 阅读时长 ≈ 13

【作业向】程序设计思维与实践 Week7作业

♔A TT 的魔法猫

♔Problem

众所周知，TT 有一只魔法猫。

这一天，TT 正在专心致志地玩《猫和老鼠》游戏，然而比赛还没开始，聪明的魔法猫便告诉了 TT 比赛的最终结果。TT 非常诧异，不仅诧异于他的小猫咪居然会说话，更诧异于这可爱的小不点为何有如此魔力？

魔法猫告诉 TT，它其实拥有一张游戏胜负表，上面有 N 个人以及 M 个胜负关系，每个胜负关系为 A B，表示 A 能胜过 B，且胜负关系具有传递性。即 A 胜过 B，B 胜过 C，则 A 也能胜过 C。

TT 不相信他的小猫咪什么比赛都能预测，因此他想知道有多少对选手的胜负无法预先得知，你能帮帮他吗？

♔Input

第一行给出数据组数。

每组数据第一行给出 N 和 M（N , M <= 500）。

接下来 M 行，每行给出 A B，表示 A 可以胜过 B。

♔Output

对于每一组数据，判断有多少场比赛的胜负不能预先得知。注意 (a, b) 与 (b, a) 等价，即每一个二元组只被计算一次。

♔Example

♔Input

1
2
3
4
5
6
7
8
9
10
11
3
3 3
1 2
1 3
2 3
3 2
1 2
2 3
4 2
1 2
3 4

♔Output

1
2
3
0
0
4

♔解题思路

由题意可知，这一题中的胜负关系具有传递性，故我们可以使用Floyd算法求出任意两点的胜负关系，我们可以设tu[a] [b]=1表示a比b强，tu[a] [b]=0表示a和b胜负关系不明，当tu[a] [b]=dis[b] [a]=0时表示a和b的胜负关系无法判断。这样我们在读入已知的胜负关系之后，在跑Floyd的时候将更新条件设置为tu[i] [j]=max(tu[i] [j],tu[i] [k]&tu[k] [j])即可得到答案。但裸的Floyd会超时，我们需要做一下剪枝，即当tu[i] [k]=1时才将k作为中间点进行更新。

♔代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int T,m,n; 
int tu[5005][5005];

int main()
{
	int i,j,k;
	int a,b;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++) tu[i][j]=0;
		}
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			tu[a][b]=1;
		}
		for(k=1;k<=n;k++)
		{
			for(i=1;i<=n;i++)
			{
				if(tu[i][k])
				{
					for(j=1;j<=n;j++)
					{
						tu[i][j]=max(tu[i][j],tu[i][k]&tu[k][j]);
					}
				}
			}
		}
		b=0;
		for(i=1;i<n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				if(tu[i][j]==0 && tu[j][i]==0) b++;
			}
		}
		printf("%d\n",b);
	}
	return 0;
}

♔B TT 的旅行日记

♔Problem

众所周知，TT 有一只魔法猫。

今天他在 B 站上开启了一次旅行直播，记录他与魔法猫在喵星旅游时的奇遇。 TT 从家里出发，准备乘坐猫猫快线前往喵星机场。猫猫快线分为经济线和商业线两种，它们的速度与价钱都不同。当然啦，商业线要比经济线贵，TT 平常只能坐经济线，但是今天 TT 的魔法猫变出了一张商业线车票，可以坐一站商业线。假设 TT 换乘的时间忽略不计，请你帮 TT 找到一条去喵星机场最快的线路，不然就要误机了！

♔Input

输入包含多组数据。每组数据第一行为 3 个整数 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100)，即猫猫快线中的车站总数，起点和终点（即喵星机场所在站）编号。

下一行包含一个整数 M (1 ≤ M ≤ 1000)，即经济线的路段条数。

接下来有 M 行，每行 3 个整数 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐经济线在车站 X 和车站 Y 之间往返，其中单程需要 Z 分钟。

下一行为商业线的路段条数 K (1 ≤ K ≤ 1000)。

接下来 K 行是商业线路段的描述，格式同经济线。

所有路段都是双向的，但有可能必须使用商业车票才能到达机场。保证最优解唯一。

♔Output

对于每组数据，输出3行。第一行按访问顺序给出 TT 经过的各个车站（包括起点和终点），第二行是 TT 换乘商业线的车站编号（如果没有使用商业线车票，输出"Ticket Not Used"，不含引号），第三行是 TT 前往喵星机场花费的总时间。

本题不忽略多余的空格和制表符，且每一组答案间要输出一个换行

♔Examples

♔Input

1
2
3
4
5
6
7
8
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3

♔Output

1
2
3
1 2 4
2
5

♔解题思路

由题意得，商业线至多可以使用一次，因此我们可以从起点和终点开始各跑一次堆优化的Dijkstra算法求最短路。起点到各点的最短路记为dis[i] [0]，使用pre[i] [0]记录各点被哪个节点松弛；终点到各点的最短路记为dis[i] [1]，使用pre[i] [1]记录各点被哪个节点松弛。然后读入各条商业线的信息端点u、v，花费w，然后进行比较不使用商业线和正反使用商业线这三种情况哪种消耗时间少并记录，最后根据结果输出即可。

♔代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int n,m,s,e,k,mind,l,r;
int adj[1010],nxt[20020],too[20020],w[20020],ecnt;
int dis[1010][2],visit[1010],pre[1010][2];

priority_queue< pair<int,int> > q;

void dij(int x,int f)
{
	while(q.size()) q.pop();
	memset(visit,0,sizeof(visit));
	dis[x][f]=0;
	q.push(make_pair(0,x));
	int u,v;
	while(q.size())
	{
		u=q.top().second;
		q.pop();
		//if(visit[u]) continue;
		visit[u]=1;
		for(int i=adj[u];i;i=nxt[i])
		{
			v=too[i];
			if(dis[v][f]>dis[u][f]+w[i])
			{
				dis[v][f]=dis[u][f]+w[i];
				pre[v][f]=u;
				q.push(make_pair(-dis[v][f],v));
			}
		}
	}
}

void makeout1(int x)
{
	if(x==s)
	{
		printf("%d",x);
		return;
	}
	makeout1(pre[x][0]);
	printf(" %d",x);
}

void makeout2(int x)
{
	printf(" %d",x);
	if(x==e) return;
	makeout2(pre[x][1]);
}

int main()
{
	int i,j;
	int a,b,c;
	int flag=0;
	while(scanf("%d%d%d",&n,&s,&e)!=EOF)
	{
		if(flag) printf("\n");
		for(i=1;i<=n;i++)
		{
			adj[i]=0;dis[i][0]=0x3f3f3f3f;
			dis[i][1]=0x3f3f3f3f;
			pre[i][0]=0;pre[i][1]=0;
		}
		ecnt=0;l=0;r=0;
		//memset(nxt,0,sizeof(nxt));
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			nxt[++ecnt]=adj[a],adj[a]=ecnt,too[ecnt]=b,w[ecnt]=c;
			nxt[++ecnt]=adj[b],adj[b]=ecnt,too[ecnt]=a,w[ecnt]=c;
		}
		dij(s,0);
		dij(e,1);
		mind=dis[e][0];
		scanf("%d",&k);
		for(i=1;i<=k;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			if(mind>dis[a][0]+dis[b][1]+c)
			{
				mind=dis[a][0]+dis[b][1]+c;
				l=a,r=b;
			}
			if(mind>dis[b][0]+dis[a][1]+c)
			{
				mind=dis[b][0]+dis[a][1]+c;
				l=b,r=a;
			}
		}
		if(l==0)
		{
			makeout1(e);
			printf("\nTicket Not Used\n%d\n",mind);
		}
		else
		{
			makeout1(l);
			makeout2(r);
			printf("\n%d\n%d\n",l,mind);
		}
		flag=1;
	}
	return 0;
}

♔C TT的美梦

♔Problem

这一晚，TT 做了个美梦！

在梦中，TT 的愿望成真了，他成为了喵星的统领！喵星上有 N 个商业城市，编号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。

喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣，有些道路变得非常拥挤。正在 TT 为之苦恼之时，他的魔法小猫咪提出了一个解决方案！TT 欣然接受并针对该方案颁布了一项新的政策。

具体政策如下：对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地繁荣程度 - 出发地繁荣程度）^ 3 的税。

TT 打算测试一下这项政策是否合理，因此他想知道从首都出发，走到其他城市至少要交多少的税，如果总金额小于 3 或者无法到达请悄咪咪地打出 ‘?’。

♔Input

第一行输入 T，表明共有 T 组数据。（1 <= T <= 50）

对于每一组数据，第一行输入 N，表示点的个数。（1 <= N <= 200）

第二行输入 N 个整数，表示 1 ～ N 点的权值 a[i]。（0 <= a[i] <= 20）

第三行输入 M，表示有向道路的条数。（0 <= M <= 100000）

接下来 M 行，每行有两个整数 A B，表示存在一条 A 到 B 的有向道路。

接下来给出一个整数 Q，表示询问个数。（0 <= Q <= 100000）

每一次询问给出一个 P，表示求 1 号点到 P 号点的最少税费。

♔Output

每个询问输出一行，如果不可达或税费小于 3 则输出 ‘?’。

♔Examples

♔Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
5
6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
10
1 2 4 4 5 6 7 8 9 10
10
1 2
2 3
3 1
1 4
4 5
5 6
6 7
7 8
8 9
9 10
2
3 10

♔Output

1
2
3
4
5
6
Case 1:
3
4
Case 2:
?
?

♔解题思路

这一题在用spfa求最短路的同时要注意负环的处理，找到负环后应将负环上的点及能够到达负环的点打上标记，最后对于询问的点，若距离小于3或不可到达或被打上了标记则输出？，否则输出最短路的长度。

♔代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
int T,m,n,q;
int h[205],dis[205],flag[205],visit[205],ti[205];
int adj[205],nxt[200005],too[200005],w[200005],ecnt;

void dfs(int x)
{
	flag[x]=1;
	for(int i=adj[x];i;i=nxt[i]) 
		if(!flag[too[i]]) dfs(too[i]);
}

void spfa()
{
	memset(visit,0,sizeof(visit));
	memset(ti,0,sizeof(ti));
	memset(flag,0,sizeof(flag));
	dis[1]=0;
	queue<int> q;
	q.push(1);
	int u,v;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		visit[u]=0;
		if(flag[u]) continue;
		for(int i=adj[u];i;i=nxt[i])
		{
			v=too[i];
			if(dis[v]>dis[u]+w[i])
			{
				dis[v]=dis[u]+w[i];
				if(!visit[v])
				{
					visit[v]=1;
					q.push(v);
					ti[v]++;
					if(ti[v]>=n) dfs(v);
				}
			}
		}
	}
}

int main()
{
	int i,j,t;
	int a,b;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
		ecnt=0;
		memset(adj,0,sizeof(adj));
		memset(nxt,0,sizeof(nxt));
		scanf("%d",&n);
		for(i=1;i<=n;i++) scanf("%d",&h[i]),dis[i]=0x7fffffff;
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			nxt[++ecnt]=adj[a],adj[a]=ecnt,too[ecnt]=b,w[ecnt]=(h[b]-h[a])*(h[b]-h[a])*(h[b]-h[a]);
		}
		spfa();
		scanf("%d",&q);
		printf("Case %d:\n",t);
		for(i=1;i<=q;i++)
		{
			scanf("%d",&j);
			if(dis[j]<3 || dis[j]==0x7fffffff || flag[j]) printf("?\n");
			else printf("%d\n",dis[j]);
		}
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！