AOV工程网络图的计算
下面是计算AOV工程网络图的C代码，符合ANSI标准，可用于大部分的编译器。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_V_NUM 1024 // 最大顶点数
#define WORD32 unsigned long
#define WORD32_BLEN 4
#define MAX_WORD32 0xffffffffL
#define INIT_AOV memset( (void *)&g_aov, (char)0xff, (size_t)MAX_V_NUM * MAX_V_NUM * WORD32_BLEN )
#define IN_FILE_NAME "aov.in"
#define ERR_FILE_NOT_FOUND 1
#define TRUE 1
WORD32 g_aov[MAX_V_NUM][MAX_V_NUM];
WORD32 g_e[MAX_V_NUM], g_l[MAX_V_NUM];
int g_n;
// 函数预定义 -- 开始
void input_init();
void calc_el();
void print_result();
// 函数预定义 -- 结束
void input_init()
{
WORD32 i, j, k;
FILE *fp_in;
INIT_AOV;
fp_in = fopen( IN_FILE_NAME, "r" );
if ( fp_in == NULL )
{
printf("File not found!\n");
exit(ERR_FILE_NOT_FOUND);
}
fscanf( fp_in, "%d\n", &g_n );
while (TRUE)
{
fscanf( fp_in, "%lu %lu %lu", &i, &j, &k );
if ( ( i == 0 ) && ( j == 0 ) && ( k == 0 ) ) break;
g_aov[i - 1][j - 1] = k;
fscanf( fp_in, "\n" );
}
fclose(fp_in);
g_e[0] = 0;
}
void calc_el()
{
WORD32 ext;
int i, j;
for ( i = 1; i < g_n; i++ )
{
ext = 0;
for ( j = 0; j < g_n; j++ )
if ( ( g_aov[j][i] != MAX_WORD32 ) && ( g_e[j] + g_aov[j][i] > ext ) )
ext = g_e[j] + g_aov[j][i];
g_e[i] = ext;
}
g_l[g_n - 1] = g_e[g_n - 1];
for ( i = g_n - 2; i >= 0; i-- )
{
ext = MAX_WORD32;
for ( j = 0; j < g_n; j++ )
if ( ( g_aov[i][j] != MAX_WORD32 ) && ( g_l[j] - g_aov[i][j] < ext ) )
ext = g_l[j] - g_aov[i][j];
g_l[i] = ext;
}
}
void print_result()
{
int i, j;
printf(" #\tE\t\tL\n");
for ( i = 0; i < g_n; i++ )
{
if ( g_e[i] == g_l[i] )
printf("*");
else
printf(" ");
printf( " %d\t%lu\t\t%lu\n", i + 1, g_e[i], g_l[i] );
}
printf("\n关键路径：\n");
j = 0;
while ( j != g_n - 1 )
{
printf( "%d - ", j + 1 );
for ( i = 0; i < g_n; i++ )
{
if ( ( g_aov[j][i] != MAX_WORD32 ) && ( g_e[i] == g_l[i] ) )
{
j = i;
break;
}
}
}
printf( "%d\n", j + 1 );
}
int main(int argc,char *argv[])
{
input_init();
calc_el();
print_result();
return 0;
}
输入文件aov.in的格式是这样的：
第一行：n，表示顶点数
后面每行表示一道工序
最后用0 0 0结束
事项1为起始事项，事项n为末事项。
输出中，有*的是关键路径上的点。