兔子与星空（10分）
题目内容：
很久很久以前，森林里住着一群兔子。兔子们无聊的时候就喜欢研究星座。如图所示，天空中已经有了n颗星星，其中有些星星有边相连。兔子们希望删除掉一些边，然后使得保留下的边仍能是n颗星星连通。他们希望计算，保留的边的权值之和最小是多少？
输入格式:
第一行只包含一个表示星星个数的数n，n不大于26，并且这n个星星是由大写字母表里的前n个字母表示。接下来的n-1行是由字母表的前n-1个字母开头。最后一个星星表示的字母不用输入。对于每一行，以每个星星表示的字母开头，然后后面跟着一个数字，表示有多少条边可以从这个星星到后面字母表中的星星。如果k是大于0，表示该行后面会表示k条边的k个数据。每条边的数据是由表示连接到另一端星星的字母和该边的权值组成。权值是正整数的并且小于100。该行的所有数据字段分隔单一空白。该星星网络将始终连接所有的星星。该星星网络将永远不会超过75条边。没有任何一个星星会有超过15条的边连接到其他星星（之前或之后的字母）。在下面的示例输入，数据是与上面的图相一致的。
输出格式：
输出是一个整数，表示最小的权值和
输入样例：
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
输出样例：
216
1 #include <iostream> 2 #include <string.h> 3 #include <algorithm> 4 #include <stack> 5 #include <string> 6 #include <math.h> 7 #include <queue> 8 #include <stdio.h> 9 #include <string.h> 10 #include <vector> 11 #include <fstream> 12 #include <set> 13 #define inf 999999; 14 15 using namespace std; 16 int n, classp[27]; 17 struct edge { 18 int x, y; 19 int val; 20 }all[500]; 21 22 struct finder { 23 bool operator()(edge a, edge b) { return a.val < b.val; } 24 }myfinder; 25 26 void uni(int x, int y) {//classp[x]<classp[y] 27 int val = classp[y]; 28 for (int i = 0; i < 26; i++) 29 if (classp[i] == val) 30 classp[i] = classp[x]; 31 } 32 33 void init() { 34 scanf("%d", &n); 35 for (int i = 0; i < 26; i++) 36 classp[i] = i; 37 int edgen = 0; 38 for (int i = 1; i <= n - 1; i++) { 39 char ch; 40 cin.ignore(); 41 scanf("%c", &ch); 42 int j; 43 scanf("%d", &j); 44 for (int k = 1; k <= j; k++) { 45 char p; int val; 46 cin.ignore(); 47 scanf("%c%d", &p, &val); 48 all[++edgen].x = ch - 'A'; 49 all[edgen].y = p - 'A'; 50 all[edgen].val = val; 51 } 52 } 53 sort(all + 1, all + edgen + 1,myfinder); 54 int sum = 0; 55 for(int i=1;i<=edgen;i++) 56 if (classp[all[i].x] != classp[all[i].y]) { 57 if (all[i].x < all[i].y) 58 uni(all[i].x, all[i].y); 59 else 60 uni(all[i].y, all[i].x); 61 sum += all[i].val; 62 } 63 printf("%d\n", sum); 64 } 65 66 int main() 67 { 68 init(); 69 return 0; 70 }
大概是裸MST？
兔子与樱花（10分）
题目内容：
很久很久之前，森林里住着一群兔子。有一天，兔子们希望去赏樱花，但当他们到了上野公园门口却忘记了带地图。现在兔子们想求助于你来帮他们找到公园里的最短路。
输入格式:
输入分为三个部分。
第一个部分有P+1行（P<30），第一行为一个整数P，之后的P行表示上野公园的地点。
第二个部分有Q+1行（Q<50），第一行为一个整数Q，之后的Q行每行分别为两个字符串与一个整数，表示这两点有直线的道路，并显示二者之间的矩离（单位为米）。
第三个部分有R+1行（R<20），第一行为一个整数R，之后的R行每行为两个字符串，表示需要求的路线。
输出格式：
输出有R行，分别表示每个路线最短的走法。其中两个点之间，用->(矩离)->相隔。
输入样例：
6
Ginza
Sensouji
Shinjukugyoen
Uenokouen
Yoyogikouen
Meijishinguu
6
Ginza Sensouji 80
Shinjukugyoen Sensouji 40
Ginza Uenokouen 35
Uenokouen Shinjukugyoen 85
Sensouji Meijishinguu 60
Meijishinguu Yoyogikouen 35
2
Uenokouen Yoyogikouen
Meijishinguu Meijishinguu
输出样例：
Uenokouen->(35)->Ginza->(80)->Sensouji->(60)->Meijishinguu->(35)->Yoyogikouen
Meijishinguu
1 #include <iostream> 2 #include <string.h> 3 #include <algorithm> 4 #include <stack> 5 #include <string> 6 #include <math.h> 7 #include <queue> 8 #include <stdio.h> 9 #include <string.h> 10 #include <vector> 11 #include <fstream> 12 #include <set> 13 #define inf 999999; 14 15 using namespace std; 16 int adj[31][31], path[31][31]; 17 int p, q, r; 18 string spot[31]; 19 int dis[31][31]; 20 21 int find(string a) { 22 for (int i = 1; i <= p; i++) 23 if (a == spot[i]) 24 return i; 25 } 26 27 void getrout(int s1, int s2) { 28 if (s1 != s2) 29 { 30 while (1) { 31 cout << spot[s1] << "->(" << dis[s1][path[s1][s2]] << ")->"; 32 if (path[s1][s2] == s2)break; 33 s1 = path[s1][s2]; 34 } 35 } 36 cout << spot[s2] << endl; 37 } 38 39 void dp() { 40 for(int l=0;l<p;l++) 41 for (int i = 1; i <= p; i++) 42 for(int j=1;j<=p;j++) 43 for (int k = 1; k <= p; k++) { 44 if (adj[i][k] + adj[k][j] < adj[i][j]) { 45 adj[i][j] = adj[i][k] + adj[k][j]; 46 path[i][j] = path[i][k]; 47 } 48 } 49 } 50 51 void init() { 52 scanf("%d", &p); 53 for(int i=1;i<=p;i++) 54 for (int j = 1; j <= p; j++) { 55 if (i == j) { 56 adj[i][j] = 0; 57 path[i][j] = i; 58 } 59 else 60 { 61 adj[i][j] = inf; 62 path[i][j] = -1; 63 } 64 } 65 for (int i = 1; i <= p; i++) 66 cin >> spot[i]; 67 scanf("%d", &q); 68 for (int i = 1; i <= q; i++) 69 { 70 string a, b; 71 cin >> a >> b; 72 int s1 = find(a), s2 = find(b); 73 scanf("%d", &dis[s1][s2]); 74 dis[s2][s1] = dis[s1][s2]; 75 adj[s1][s2] = dis[s1][s2]; 76 adj[s2][s1] = dis[s1][s2]; 77 path[s1][s2] = s2; 78 path[s2][s1] = s1; 79 } 80 dp(); 81 scanf("%d", &r); 82 for (int i = 1; i <= r; i++) { 83 string a, b; 84 cin >> a >> b; 85 getrout(find(a), find(b)); 86 } 87 } 88 89 int main() 90 { 91 init(); 92 return 0; 93 }
模糊记得难点在输出？
这道考点好像是Floyd，也是裸的
吐槽一下上面两道题的机翻
也许还是日文题……？风格也很清新……
有点想去日本玩呜呜呜
地震之后（10分）
题目内容：
2008年地震之后,坚强县受灾严重，该县通信线路也收到了致命的打击，县总部为了能够及时的向各村的发送消息，命令小强去解决一下这个问题。
小强经过调查发现，为了能够快速的实现通信，当务之急是能够建立起一条从总部可以向各个村单向发送信息的通信系统。由于灾后情况紧急，不是每一个村之间都能够快速的建立起通信线路，只有有限的村比如村A和村B间可以建立单向的从A向B发送信息的通信线路，小强现在的问题就是要找出一个合适的方案，使从总部发送出的信息能够通到各村，而用的总的通信线路是最短的（毕竟情况危急，物质短缺）。
输入格式:
输入包括多组的测试数据。
对于每一组测试数据:
1、第一行包括两个整数N(1<=N<=100),M(M<<=10000),N表示通信网络中村子的数量，M表示在这些村子中，可以有M条通信线路建起来。
2、接下来N行，每行两个整数xi,yi,代表着这个村子的X轴，Y轴的坐标(xi,yi)
3、接下来M行，每行两个整数c1（1<=c1<=N),c2(1<=c2<=N),代表着从村c1到村c2可以建一个单向线路。
注：两村之间的直线段距离（通信线路长度），即为两点间的欧式距离。
县总部所在的村假设都在编号为1的村。
输入以文件终止为结束。
输出格式：
对于每一组的测试数据，输出完全的一行，值为最短的总长度，结果保留两位小数。
如果不能建立一个单向的临时网络，输出"NO".
输入样例：
4 6
3 6
4 6
3 4
7 20
1 2
1 3
2 3
3 4
3 1
3 2
4 3
0 0
1 0
1 1
1 2
1 3
4 1
2 3
输出样例：
19.49
NO
1 #include <iostream> 2 #include <string.h> 3 #include <algorithm> 4 #include <stack> 5 #include <string> 6 #include <math.h> 7 #include <queue> 8 #include <stdio.h> 9 #include <string.h> 10 #include <vector> 11 #include <fstream> 12 #include <set> 13 #define maxn 101 14 #define inf 0x7fffffff 15 16 using namespace std; 17 struct edge { 18 int from, to; 19 double val; 20 }; 21 edge all[maxn * 100]; 22 int n, m; 23 double in[maxn]; 24 int pre[maxn]; 25 int id[maxn]; 26 int vis[maxn]; 27 double px[maxn], py[maxn]; 28 int root; 29 30 void zhuliu() { 31 double ans = 0; 32 while (1) { 33 for (int i = 1; i <= n; i++) 34 in[i] = inf; 35 for (int i = 1; i <= m; i++) { 36 int from = all[i].from, to = all[i].to; 37 if (all[i].val < in[to] && from != to) { 38 in[to] = all[i].val; 39 pre[to] = from; 40 } 41 } 42 for (int i = 1; i <= n; i++) { 43 if (i == root)continue; 44 if (in[i] == inf) { 45 printf("NO\n"); 46 return; 47 } 48 } 49 /*寻找环*/ 50 int cnt = 1;//缩点数目 51 memset(id, -1, sizeof(id)); 52 memset(vis, -1, sizeof(vis)); 53 in[root] = 0; 54 for (int i = 1; i <= n; i++) { 55 ans += in[i]; 56 int v = i; 57 while (vis[v] != i && id[v] == -1 && v != root) { 58 vis[v] = i; 59 v = pre[v]; 60 } 61 if (v != root && id[v] == -1) { 62 for (int u = pre[v]; u != v; u = pre[u]) 63 id[u] = cnt; 64 id[v] = cnt++; 65 } 66 } 67 /*没有找到自环*/ 68 if (cnt == 1) { 69 printf("%.2lf\n", ans); 70 return; 71 } 72 /*找到不是自环的，重新给那些点标记*/ 73 for (int i = 1; i <= n; i++) 74 if (id[i] == -1)id[i] = cnt++; 75 for (int i = 1; i <= m; i++) { 76 int to = all[i].to; 77 all[i].from = id[all[i].from]; 78 all[i].to = id[all[i].to]; 79 if (all[i].from != all[i].to) 80 all[i].val -= in[to]; 81 } 82 n = cnt-1; 83 root = id[root]; 84 } 85 } 86 87 void init() { 88 while (cin >> n >> m) { 89 root = 1; 90 for (int i = 1; i <= n; i++) 91 scanf("%lf%lf", &px[i], &py[i]); 92 for (int i = 1; i <= m; i++) { 93 int x, y; 94 scanf("%d%d", &x, &y); 95 double l1 = px[x] - px[y], l2 = py[x] - py[y]; 96 all[i].from = x, all[i].to = y; 97 all[i].val = sqrt(l1*l1 + l2 * l2); 98 } 99 zhuliu(); 100 } 101 } 102 103 int main() 104 { 105 init(); 106 return 0; 107 }
是裸的朱刘算法（最小树形图）
暂时的理解（有点怕理解错在这里写一下）是：每次择出每个点作为入点时的最小边，并在将这些边算入答案后查看由这些边组成的图中有无环，如果有就缩点（因为他们可以相互连通），将缩点后的图重新进行上述操作，一遍一遍筛下来，图中不存在环的时候就能算出答案。算是有点贪心思想……？我其实也没有理解透彻-^-因为不考，非常功利地套了下模板随便糊弄完事。我来打脸了，考了，真是低估出卷人了
wa点：
太弱鸡导致连改模板都漏掉了一些地方。因为我是以编号1为第一个元素的，所以cnt起始应该是1，第一遍写的时候没有把模板中的改掉。
当时做的时候就比较懒，算法很多都写得很不好，前两道完全没有考虑复杂度
第三题发现在课程内容之外就没有及时做（第一次十分天真地用了无向图MST算法……我真是个傻子……然后就没心思改了），现在po的时候发现前两道都忘了……以后还是做一道po一道吧
希望我的标题没写错（。
