经典算法普及——基础篇

kon3155 · 发表于 2009-2-25 12:28:54

接上贴：

1。根据算法1计算24点的代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int NUMBER_TO_CAL = 24;
double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];
bool Search(int n)
{
if (n == 1) {
if ( fabs(number[0] - NUMBER_TO_CAL) < PRECISION ) {
cout << expression[0] << endl;
return true;
} else {
return false;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double a, b;
string expa, expb;
a = number[i];
b = number[j];
number[j] = number[n - 1];
expa = expression[i];
expb = expression[j];
expression[j] = expression[n - 1];
expression[i] = '(' + expa + '+' + expb + ')';
number[i] = a + b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '-' + expb + ')';
number[i] = a - b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expb + '-' + expa + ')';
number[i] = b - a;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '*' + expb + ')';
number[i] = a * b;
if ( Search(n - 1) ) return true;
if (b != 0) {
expression[i] = '(' + expa + '/' + expb + ')';
number[i] = a / b;
if ( Search(n - 1) ) return true;
}
if (a != 0) {
expression[i] = '(' + expb + '/' + expa + ')';
number[i] = b / a;
if ( Search(n - 1) ) return true;
}
number[i] = a;
number[j] = b;
expression[i] = expa;
expression[j] = expb;
}
}
return false;
}
void main()
{
for (int i = 0; i < COUNT_OF_NUMBER; i++) {
char buffer[20];
int x;
cin >> x;
number[i] = x;
itoa(x, buffer, 10);
expression[i] = buffer;
}
if ( Search(COUNT_OF_NUMBER) ) {
cout << "Success." << endl;
} else {
cout << "Fail." << endl;
}
}

复制代码

2。根据算法2计算解决题目的程序代码：

#include <fstream>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
#include <cmath>
#include <climits>
#include <bitset>
using namespace std;
const char* INPUT_FILE = "game.in";
const char* OUTPUT_FILE = "game.out";
const int NUMBER_COUNT = 6;
const int STATE_COUNT = (1 << NUMBER_COUNT);
const int MAX_NUMBER = 100;
const int MAX_EXPECTION = 1000;
const int MAX_VALUE = MAX_EXPECTION * MAX_NUMBER;
struct Node {
int value;
int left, right;
int leftvalue, rightvalue;
char opr;
};
typedef list<Node> NodeList;
struct State {
bitset<MAX_VALUE+10> exist;
NodeList nodelist;
};
int number[NUMBER_COUNT], expection;
State state[STATE_COUNT];
void ReadData()
{
ifstream fin(INPUT_FILE);
for (int i = 0; i < NUMBER_COUNT; i++) {
fin >> number[i];
}
fin >> expection;
}
void Init()
{
Node node ;
for (int i = 0; i < NUMBER_COUNT; i++) {
node.value = number[i];
node.left = node.right = -1;
state[(1 << i)].nodelist.push_back(node);
state[(1 << i)].exist[node.value] = true;
}
}
void Merge(int a, int b, int x)
{
Node node;
NodeList::const_iterator i, j;
for (i = state[a].nodelist.begin(); i != state[a].nodelist.end();
i++) {
for (j = state[b].nodelist.begin(); j != state[b].nodelist.en
d(); j++)
{
node.value = (*i).value + (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '+';
if ( (node.value <= MAX_VALUE) && (!state[x].exist[no
de.value]) ) {
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////
double tmp = double((*i).value) * double((*j).value);
if (tmp < INT_MAX) {
node.value = (*i).value * (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '*';
if ( (node.value <= MAX_VALUE) && (!state[x].
exist[node.value]) )
{
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
}
/////////////////////////////////////////////////////
if ((*i).value >= (*j).value) {
node.value = (*i).value - (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '-';
} else {
node.value = (*j).value - (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '-';
}
if ( (node.value <= MAX_VALUE) && (!state[x].exist[no
de.value]) ) {
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////
if ( ((*j).value != 0) && ((*i).value >= (*j).value) &
&
((*i).value % (*j).value == 0) )
{
node.value = (*i).value / (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '/';
} else if ( ((*i).value != 0) && ((*j).value >= (*i).
value) &&
((*j).value % (*i).value == 0) )
{
node.value = (*j).value / (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '/';
}
if ( (node.value <= MAX_VALUE) && (!state[x].exist[no
de.value]) )
{
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////
}
}
}
void Solve()
{
Init();
for (int x = 2; x < STATE_COUNT; x++) {
for (int i = 1; i < x; i++) {
if ( (x & i) == i ) {
int j = x - i;
if (i <= j) {
Merge(i, j, x);
}
}
}
}
}
void PrintExpression(ostream& out, Node node)
{
if (node.left == -1) {
out << node.value;
} else {
NodeList::const_iterator iter;
out << "(";
for (iter = state[node.left].nodelist.begin();
iter != state[node.left].nodelist.end();
iter++)
{
if ((*iter).value == node.leftvalue) {
PrintExpression(out, *iter);
break;
}
}
out << node.opr;
for (iter = state[node.right].nodelist.begin();
iter != state[node.right].nodelist.end();
iter++)
{
if ((*iter).value == node.rightvalue) {
PrintExpression(out, *iter);
break;
}
}
out << ")";
}
}
void Output()
{
ofstream fout(OUTPUT_FILE);
int bestValue = -INT_MAX;
NodeList::const_iterator iter, bestIter;
NodeList& nodelist = state[STATE_COUNT-1].nodelist;
for (iter = nodelist.begin(); iter != nodelist.end(); iter++)
{
if ( ((*iter).value <= expection) && (bestValue < (*iter).val
ue) ) {
bestValue = (*iter).value;
bestIter = iter;
}
}
fout << bestValue << endl;
PrintExpression(fout, *bestIter );
fout << endl;
}
int main()
{
ReadData();
Solve();
Output();
return 0;
}

复制代码

kon3155 · 发表于 2009-2-25 12:38:12

无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。
【Prim算法思想】
任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。
【最小生成树算法实例】
现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？
【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。
【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。
　【输入样例】
6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33
　
【输出样例】
1 2 10
2 3 5
2 4 6
2 6 11
4 5 18
　
原图

最小生成树

program prim_example;
Const
vmax=200
var
w:array[1..vmax,1..vmax]of integer;
i,j,k,v,e:integer;
procedure prim(v0:integer); {v0是开始结点}
var
flag:array[1..vmax] of boolean;
min,prevk,nextk:integer;
begin
fillchar(flag,sizeof(flag),false);
flag[v0]:=true; {先选出v0}
for i:=1 to v-1 do {一共寻找v-1条边}
begin
min:=maxint;
for k:=1 to v do
if flag[k] then {找已在集合中的顶点}
for j:=1 to v do {求满足条件的边的最小值}
if (not(flag[j])) and (w[k,j]<min) and (w[k,j]<>0)
then begin
min:=w[k,j]; {记下最小值}
nextk:=j;
prevk:=k;
end;
if min<>maxint
then begin
flag[nextk]:=true; {最小值对应顶点进入集合}
writeln(prevk,' ',nextk,‘ ',min);
end;
end;{for}
end;{prim}
begin
assign(input,'prim.in');
reset(input);
assign(output,'prim.out');
rewrite(output);
fillchar(w,sizeof(w),0);
readln(v,e);
for k:=1 to e do
begin
read(i,j);
readln(w[i,j]);
w[j,i]:=w[i,j];
end;
prim(1);
close(input);
close(output);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:40:11

设图G=(V,E)是一个有向图,它的每一条边(U,V)都有一个非负权W(U,V)，在G中指定一个结点V0，要求从V0到G的每一个结点Vj的最短路径找出来（或指出不存在）。
由于源结点V0是给定的，所谓称为单源最短路径。
【Dijkstra算法思想】
把所有结点分为两组。
第一组：包含已确定最短路径的结点。
第二组：包含尚未确定最短路径的结点。
按最短路径长度递增的顺序把第二组的结点加到第一组中去，直到V0可达的所有结点都包含于第一组中。在这个过程中，总保持从V0到第一组各结点的最短路径长度都不大于从V0到第二组任何结点的路径长度。
【单源最短路径算法实例】
现有一张县城的城镇地图，图中的顶点为城镇，无向边代表两个城镇间的连通关系，边上的权为公路造价，县城所在的城镇为v0。由于该县经济比较落后，因此公路建设只能从县城开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路，该线路的工程总造价必须最少。
【输入】第一行一个整数v，代表城镇数，县城编号为1。第二行是一个整数e，表示有向边数。以下e行，每行为两个城镇编号和它们之间的公路造价。
【输出】 v-1行，每行为两个城市的序号，表明这两个城市间建一条公路。
　【输入样例】
6
10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33
　
【输出样例】
1 2
2 3
2 4
1 5
1 6

原图

从第1点出发的最短路径

【参考程序】

program dijkstra_example;
const
vmax=100;
type
path=record {此记录类型用于记录每一个结点与v0的距离和其父结点}
length:integer;
pre:0..vmax;
end;
var
w:array[1..vmax,1..vmax] of integer;
dist:array[1..vmax] of path;
v,e,u,i,j,x,y:integer;
procedure init;
begin
assign(input,'dijkstra.in');
reset(input);
assign(output,'dijkstra.out');
rewrite(output);
readln(v);
readln(e);
for i:=1 to v do
for j:=1 to v do
if i<>j
then w[i,j]:=30000
{30000只是一个较大的数的意思，实际应用于应该根据题目中给出的取值范围赋予一个充分大的数}
else w[i,j]:=0;
for i:=1 to e do
begin
read(x,y);
readln(w[x,y]);
w[y,x]:=w[x,y];
end;
end;
procedure dijkstra(v0:integer);
var
min:integer;
begin
w[v0,v0]:=1; {v0首先进入第一组}
for i:=1 to v do
begin
dist[i].length:=w[v0,i]; {计算每个结点的距离值}
if dist[i].length<>30000
then dist[i].pre:=v0 {如和v0直接有路，则置前驱结点为v0}
else dist[i].pre:=0;
end;
repeat
min:=30000;
u:=0;
for i:=1 to v do {找最短距离}
if (w[i,i]=0) and (dist[i].length<min)
then begin
u:=i;
min:=dist[i].length;
end;
if u<>0
then begin
w[u,u]:=1;
for i:=1 to v do {重新计算其他结点的距离值}
if (w[i,i]=0) and (dist[i].length>dist[u].length+w[u,i])
then begin
dist[i].length:=dist[u].length+w[u,i];
dist[i].pre:=u;
end;
end;
until u=0;
end;
begin
init;
v0:=1;
dijkstra(v0);
for i:=1 to v do
begin
if (i<>v0) and (dist[i].length<>30000)
then write(dist[i].pre,' ',i);
end;
close(input);
close(output);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:41:34

设图G=(V,E)是一个有向图,对于每对结点(U,V),找出从U到V的最短路径。
【Floyd算法思想】
利用一个三重循环产生一个存储每个结点最短距离的矩阵.
【Floyd算法实例】
现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表城市之间的距离。求每个城市的最短距离
【输入】第一行两个数v,e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权。
【输出】所有可能连接的城市的最短距离。
　【输入样例】
6 10
1 2 10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 6
4 5 18
4 6 14
5 6 33

【输出样例】
1 2 10
1 3 15
1 4 16
1 5 19
1 6 21
2 3 5
2 4 6
2 5 24
2 6 11
3 4 6
3 5 24
3 6 16
4 5 18
4 6 14
5 6 32

【参考程序】

program floyd_example;
const
maxn=10;
var
n,s,t,i,j:integer;
dist:array[1..maxn,1..maxn] of real;
prev:array[1..maxn,1..maxn] of 0..maxn;
procedure init;
var
m,i,u,v:integer;
begin
assign(input,'floyd.in');
reset(input);
assign(output,'floyd.out');
rewrite(output);
readln(n,m);
fillchar(prev,sizeof(prev),0);
for u:=1 to n do
for v:=1 to n do
dist[u,v]:=1e10;
for i:=1 to m do
begin
readln(u,v,dist[u,v]);
dist[v,u]:=dist[u,v];
prev[u,v]:=u;
prev[v,u]:=v;
end;
end;{init}
procedure floyd;
var
i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]<dist[i,j])
then begin
dist[i,j]:=dist[i,k]+dist[k,j];
prev[i,j]:=prev[k,j];
end;
end;{floyd}
procedure print(i,j:integer);
begin
if i=j
then write(i)
else if prev[i,j]=0
then write('No Solution!')
else begin
print(i,prev[i,j]);
write('->',j);
end;
end;{print}
begin
init;
floyd;
for i:=1 to n do
for j:=i+1 to n do
begin
write(i,' ',j,' ');
write(dist[i,j]:0:0,' ');
print(i,j);
writeln;
end;
close(input);
close(output);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:43:27

求有向图的所有环,此问题包括了求最大环或者最小环。
【输入】
第一行两个数v,e，分别代表图的顶点数和边数，以下e行，每行为有连接的两个顶点和权。
【输出】
顶点编号和环的长度以及包含该顶点的环的路径。
　【输入样例】 huan.in
5 7
1 2 2
2 1 1
2 5 4
3 2 5
3 4 7
4 1 3
5 4 6
　

【输出样例】 huan.out
1 3 1->2
2 3 2->1
4 15 4->1->2->5
5 15 5->4->1->2

【参考程序】

program huan;
const
maxn=90;
var
n,s,t,i,j:integer;
dist:array[1..maxn,1..maxn] of real;
prev:array[1..maxn,1..maxn] of 0..maxn;
procedure init;
var
m,i,u,v:integer;
begin
assign(input,'huan.in');
reset(input);
assign(output,'huan.out');
rewrite(output);
readln(n,m);
fillchar(prev,sizeof(prev),0);
for u:=1 to n do
for v:=1 to n do
dist[u,v]:=1e10;
for i:=1 to m do
begin
readln(u,v,dist[u,v]);
prev[u,v]:=u;
end;
end;
procedure floyd;
var
i,j,k:integer;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (dist[i,k]+dist[k,j]<dist[i,j])
then begin
dist[i,j]:=dist[i,k]+dist[k,j];
prev[i,j]:=prev[k,j];
end;
end;{floyd}
procedure print(i,j:integer);
begin
if i=j
then write(i)
else if prev[i,j]=0
then write('No Circle!')
else begin
print(i,prev[i,j]);
write('->',j);
end;
end;{print}
begin
init;
floyd;
for i:=1 to n do
begin
if dist[i,i]<>1e10
then
begin
write(i,' ');
write(dist[i,i]:0:0,' ');
print(i,prev[i,i]);
writeln;
end;
end;
close(input);
close(output);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:44:34

Dijkstra算法中要求边的权非负，如果遇到负权，则可以采用Bellman-Ford算法。
【Bellman-Ford算法思想】

【Bellman-Ford算法实例】
　【输入样例】
6
10
1 2 -10
1 5 19
1 6 21
2 3 5
2 4 6
2 6 11
3 4 -6
4 5 18
4 6 14
5 6 -33
1 4　

【输出样例】
length=-11
1->2->3->4

【参考程序】

program bellman_ford;
const
maxn=30;
var
n,s,t:integer;
dist:array[1..maxn] of real;
w:array[1..maxn,1..maxn] of real;
pre:array[1..maxn] of integer;
vis:array[1..maxn] of boolean;
procedure init;
var
m,i,u,v:integer;
begin
assign(input,'bellford.in');
reset(input);
assign(output,'bellford.out');
rewrite(output);
readln(n,m);
for u:=1 to n do
for v:=1 to n do
w[u,v]:=1e38;
for i:=1 to m do
readln(u,v,w[u,v]);
readln(s,t); {求结点s和结点t的最短距离和路径}
end;{init}
procedure bellford;
var
i,j:integer;
change:boolean;
begin
for i:=1 to n do
dist[i]:=1e38;
dist[s]:=0;
repeat
change:=false; {记录递推序列是否改变}
for i:=1 to n do
for j:=1 to n do
if dist[i]+w[i,j]<dist[j]
then begin
dist[j]:=dist[i]+w[i,j];
pre[j]:=i;
change:=true;
end;
until not change;
end;{bellford}
procedure out(s,t:integer);
var
k,length,i:integer;
path:array[1..maxn] of integer;
begin
if (dist[t])>1e38
then writeln('No solutin.')
else begin
length:=0;
k:=t;
while (k<>s) do
begin
inc(length);
path[length]:=k;
k:=pre[k];
end;
writeln('length=',dist[t]:0:0);
write(s);
for i:=length downto 1 do
write('->',path[i]);
writeln;
end;
end;{out}
begin
init;
bellford;
out(s,t);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:45:33

输入一张无向图，指出该图中哪些结点对之间有路。该问题通常采用传递闭包的计算方法。
【输入】
n(顶点数，1≤n≤20)
e(边数，1≤e≤210)
以下e行，每行为有边连接的一对顶点
【输出】
k行，每行两个数，为存在通路的顶点对序号i,j(i<j)
　【输入样例】
6
5
1 5
1 6
2 3
4 6
5 6
　

【输出样例】
1 4
1 5
1 6
2 3
4 5
4 6
5 6

program bibao_example;
const
maxv=20;
var
link,longlink:array[1..maxv,1..maxv] of boolean;
v,e,k,i,j:integer;
procedure init;
begin
assign(input,'bibao.in');
reset(input);
assign(output,'bibao.out');
rewrite(output);
fillchar(longlink,sizeof(longlink),0);
fillchar(link,sizeof(link),0);
readln(v);
readln(e);
for k:=1 to e do
begin
readln(i,j);
link[i,j]:=true; {因为没有权，所以有布尔型表示连通关系，能提高运算速度}
link[j,i]:=true;
end;
end;{init}
procedure bibao;
begin
longlink:=link;
for k:=1 to v do {枚举中间顶点}
for i:=1 to v do {枚举所有顶点对}
for j:=1 to v do {计算顶点i和顶点j的连通情况}
longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]);
end;{bibao}
procedure out;
begin
for i:=1 to v-1 do
for j:=i+1 to v do
if longlink[i,j]
then writeln(i,' ',j);
end;{out}
begin{main}
init;
bibao;
out;
close(input);
close(output);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:46:41

在一张顶点带权的无向图中，计算含顶点数最多的一个连通分支和顶点权和最大的连通分支。
【输入】
n(顶点数，1≤n≤20)
以下n行，其中第i行是顶点i的权
e(边数，1≤e≤210)
以下e行，每行为有边连接的一对顶点
【输出】
含顶点数最多的一个连通分支
顶点权和最大的一个连通分支
　【输入样例】
6
2
10
20
8
5
7
5
1 5
1 6
2 3
4 6
5 6
　

【输出样例】
1->5->6->4->
2->3->

program liantong_example;
const
maxv=20;
var
link,longlink:array[1..maxv,1..maxv] of boolean;
f:array[1..maxv] of boolean;
w:array[1..maxv] of integer;
v,e,k,i,j,s,best,besti,max,maxk:integer;
procedure init;
begin
assign(input,'liantong.in');
reset(input);
assign(output,'liantong.out');
rewrite(output);
fillchar(longlink,sizeof(longlink),0);
fillchar(link,sizeof(link),0);
readln(v);
for i:=1 to v do
readln(w[i]);
readln(e);
for k:=1 to e do
begin
readln(i,j);
link[i,j]:=true;
link[j,i]:=true;
end;
end;{init}
procedure bibao;
begin
longlink:=link;
for k:=1 to v do
for i:=1 to v do
for j:=1 to v do
longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]);
end;{bibao}
procedure dfs(i:integer); {深度优先搜索，用于输出路径}
begin
write(i,'->');
f[i]:=true;
for j:=1 to v do
if (not f[j]) and longlink[i,j]
then dfs(j);
end;{dfs}
begin{main}
init;
bibao;
for i:=1 to v do
begin
k:=0;s:=0;
for j:=1 to v do {计算顶点i所在连通分支中的顶点总数和顶点的权和}
if longlink[i,j]
then begin
k:=k+1;
s:=s+w[j];
end;
if k>best {求出顶点数的最大值}
then begin
best:=k;
besti:=i;
end;
if s>max {求出顶点权和的最大值}
then begin
max:=s;
maxk:=i;
end;
if k=v then break;
end;
fillchar(f,sizeof(f),false); {结点是否访问数组初始化}
dfs(besti);
writeln;
fillchar(f,sizeof(f),false);
dfs(maxk);
close(input);
close(output);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:47:37

所谓拓扑序列，就是有向图的最长路径问题，如果图中存在环，则最长路径是无法求得的，所以有拓扑序列的有向图不可以存在环。具体定义如下：
给出有向图G=（V，E），若结点的线形序列V1,V2,...Vn满足条件：对于i,j(1≤j<i≤n)，Vi和Vj之间没有边。求线形序列V1,V2,...Vn的过程就称为拓扑排序，这个线形序列就称为拓扑序列。
【拓扑排序主要思想】
有向图可以拓扑排序的条件是：图中没有环。
具体方法：
⑴ 从图中选择一个入度为0的点加入拓扑序列。
⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。
反复执行这两个步骤，直到所有结点都已经进入拓扑序列。

【实例：士兵排队问题】
有n个士兵(1≤n≤26)，依次编号为A,B,C,...，队列训练时，指挥官要把一些士兵从高到矮排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果，记作（p1>p2）。例如A>B，B>D，F>D，对应的排队方案有三个：AFBD，FABD，ABFD
【输入】
k行，每行a b，表示a>b
【输出】
一个可行的排队方案
【输入样例】
A B
B D
F D　

【输出样例】
ABFD
　

program soldier_sort;
var
w:array['A'..'Z','A'..'Z'] of 0..1;
d:array['A'..'Z'] of integer; {记录顶点入度的数组}
s:set of 'A'..'Z';
a,b,ch:char;
m,n:string;
i,j,k:integer;
begin
assign(input,'tuopu.in');
reset(input);
assign(output,'tuopu.out');
rewrite(output);
s:=[];
while not eof(input) do
begin
readln(a,ch,b);
s:=s+[a,b]; {计算士兵名集合}
w[a,b]:=1;
d[b]:=d[b]+1; {累计顶点b的入度}
end;
m:='';
for a:='A' to 'Z' do
if a in s
then m:=m+a; {产生士兵名字符集}
k:=length(m); {求得士兵人数}
n:=''; {拓扑序列初始为空}
for i:=1 to k do
begin
j:=1;
while (d[m[j]]>0) and (j<=k) do {搜索第i个入度为0的士兵的顶点序号j}
j:=j+1;
if j>k {若不存在入度为0的顶点，则无法拓扑排序失败}
then begin
writeln('Fault!');
break;
end;
n:=n+m[j]; {入度为0的顶点进入拓扑序列n}
a:=m[j]; {删去顶点j}
d[a]:=maxint;
for j:=1 to k do {与a相连的顶点入度减1}
if w[a,m[j]]>0
then d[m[j]]:=d[m[j]]-1;
end;{for}
writeln(n);
close(input);
close(output);
end.

复制代码

kon3155 · 发表于 2009-2-25 12:48:42

某大学准备在校园网中构建校园网络，已知在校园网中选好了N（N<1000）个点，并准备在这些点安装网络设备和电脑。若要将N个点互相连接起来，问怎样布线才能使得总距离最短，两点间的布线长度等于这两个点的几何距离。
【输入】network.in
输入文件的第一行为一个正整数N(1≤N≤100)。
接下来N行，每行2个数U,V ，表示坐标。
【输出】network.out
输出最短路径距离（保留两位小数）

【样例数据】
【输入】
5
0 0
0 1
0 -1
1 0
-1 0
【输出】
4.00

【参考程序查看】

账号		自动登录	找回密码
密码			欢迎注册

[分享] 经典算法普及——基础篇