if(!visit[j]&&lowcost[j] u = j; temp = lowcost[j]; } } if(temp==INF) break; sum+=temp; visit[u]=true; for(j=1;j<=n;j++) { if(!visit[j]&&lowcost[j]>length[u][j]) lowcost[j]=length[u][j]; } } } int main() { int i,j,t; char buf[2001][7] ; while(scanf(\{ if(n==0)break; memset(length,INF,sizeof(length)); for(i=1;i<=n;i++) { scanf(\ } for(i=1;i<=n;i++) for(j=1;j int t,count=0; for(t=0;t<7;t++) if(buf[i][t]!=buf[j][t]) count++; length[i][j]=length[j][i]=count; } sum=0; prim(); printf(\ } return 0; } 思考题4 POJ2485 要求用Kruskal算法实现 Highways(公路) Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 18145 Accepted: 8433 Description The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. 的岛国Flatopia的是完全平坦的。不幸的是，Flatopia有没有公共道路。因此，交通困难在Flatopia。 ，Flatopian政府意识到了这个问题。他们打算建立一些高速公路，所以，这将是可以驱动任何对城镇之间没有离开公路系统。 Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. Flatopian城镇编号从1到N，正是每个公路连接两镇。所有公路遵循直线。所有高速公路可用于在两个方向上。公路可以自由相互交叉，但驱动程序只能在一个小镇，位于两个高速公路的末端公路之间切换。 The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town. Flatopian政府要尽量减少要建最长的公路长度。然而，他们要保证每一个镇是从每一个其他城市的高速公路可达。 Input The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case. 输入的第一行是一个整数T，告诉多少测试用例跟着。每种情况下的第一行是一个整数N（3 <= N<=500），这是许多村庄。然后来N行，第i个包含N个整数，这些N个整数的第j i村和J村之间的距离（距离应该是一个整数，65536内[1]）。各测试用例之后有一个空行。 Output For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum. Sample Input 1 3 0 990 692 990 0 179 692 179 0 Sample Output 692 #include int x; int y; int dis; }; Edge highway[250001]; bool flag[501]; int nodeSet[501]; bool compare(Edge a, Edge b) { return (a.dis < b.dis); } int main() { int tcase, n; cin>>tcase; while(tcase--){ cin >> n; int tag = 1; for(int i = 1; i <= n; i++){ nodeSet[i] = i; for(int j = 1; j <= n; j++){ highway[tag].x = i; highway[tag].y = j; cin >> highway[tag].dis; tag++; } } sort(highway+1, highway+tag, compare); memset(flag, 0, sizeof(flag)); tag = n+1; int edgeNum = 0; while(edgeNum < n-1){ if((!flag[highway[tag].x]) && (!flag[highway[tag].y])){ flag[highway[tag].x] = true; flag[highway[tag].y] = true; edgeNum++; nodeSet[highway[tag].x] = nodeSet[highway[tag].y]; } else if((!flag[highway[tag].x]) && (flag[highway[tag].y])){ flag[highway[tag].x] = true; edgeNum++; nodeSet[highway[tag].x] = nodeSet[highway[tag].y]; } else if((!flag[highway[tag].y]) && (flag[highway[tag].x])){ flag[highway[tag].y] = true; edgeNum++; nodeSet[highway[tag].y] = nodeSet[highway[tag].x]; } else{ if(nodeSet[highway[tag].x] != nodeSet[highway[tag].y]){ edgeNum++; int tmp = nodeSet[highway[tag].x]; for(int i = 1; i <= n; i++) if(nodeSet[i] == tmp) nodeSet[i] = nodeSet[highway[tag].y]; } } tag++; } cout< 思考题5 POJ1094 拓扑排序 Sorting It All Out(排序) Time Limit: 1000MS Memory Limit: 10000K Description An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 不同值的升序排序序列是在使用某种形式的小于运算从最小到最大的元素进行排序。例如，排序顺序A，B，C，d暗示，A Input Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character \range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 输入包括多个问题的实例。每个实例开始用线包含两个正整数n和m。第一个值表示的对象的数目来排序，其中2 <= N <=26。对象进行排序，将前n个字符大写字母。第二个值m表示的形式关系A Output For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined after xxx relations: yyy...y. Sorted sequence cannot be determined. Inconsistency found after xxx relations. where xxx is the number of relations processed at the time either a sorted sequence is