Fence Loops

题意：给定图，求最短环路

解题思路：

1. 将题目中给出的输入转换为邻接矩阵
2. 对一条边，在图中将其去掉，修改邻接矩阵。然后用SPFA求这条边两个顶点的最短路径，加上这条边的长度就是包含这条边的最短环路
3. 对每条边进行2中的操作，保存最短环路的最小值，就是最后的答案

代码：

/*
ID: zc.rene1
LANG: C
PROG: fence6
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 25501
int N;
int seg_seg[101][101];
int point_num = 1;
int segment_point[101][2];
int segment_length[101];
int table[202][202];
int distance[202];
int queue[202];
int in_queue[202];
void GetInput(FILE *fin)
{
int s, l, n1, n2, seg;
int i, j, k, has_new_node, index;
int temp[9];
fscanf(fin, "%d", &N);
memset(seg_seg, 0, 101 * 101 * sizeof(int));
memset(segment_point, 0, 202 * sizeof(int));
for (i=1; i<=N; i++)
{
fscanf(fin, "%d %d %d %d", &s, &l, &n1, &n2);
segment_length[s] = l;
has_new_node = 1;
for (j=1; j<=n1; j++)
{
fscanf(fin, "%d", &temp[j]);
if (seg_seg[s][temp[j]] != 0)
{
has_new_node = 0;
k = seg_seg[s][temp[j]];
}
}
for (j=1; j<=n1; j++)
{
if (has_new_node)
{
seg_seg[s][temp[j]] = point_num;
seg_seg[temp[j]][s] = point_num;
}
else
{
seg_seg[s][temp[j]] = k;
seg_seg[temp[j]][s] = k;
}
}
if (has_new_node)
{
point_num++;
}
has_new_node = 1;
for (j=1; j<=n2; j++)
{
fscanf(fin, "%d", &temp[j]);
if (seg_seg[s][temp[j]] != 0)
{
has_new_node = 0;
k = seg_seg[s][temp[j]];
}
}
for (j=1; j<=n2; j++)
{
if (has_new_node)
{
seg_seg[s][temp[j]] = point_num;
seg_seg[temp[j]][s] = point_num;
}
else
{
seg_seg[s][temp[j]] = k;
seg_seg[temp[j]][s] = k;
}
}
if (has_new_node)
{
point_num++;
}
}
for (i=1; i<=N; i++)
{
k = 0;
index = 0;
for (j=1; j<=N; j++)
{
if ((seg_seg[i][j] != 0) && (seg_seg[i][j] != k))
{
k = seg_seg[i][j];
segment_point[i][index++] = k;
}
}
}
}
void GenerateTable(void)
{
int i;
int p1, p2;
memset(table, 0, 202 * 202 * sizeof(int));
for (i=1; i<=N; i++)
{
p1 = segment_point[i][0];
p2 = segment_point[i][1];
table[p1][p2] = segment_length[i];
table[p2][p1] = segment_length[i];
}
}
int SPFA(int source, int destination)
{
int i, j, k, head, tail;
/*initialize*/
memset(in_queue, 0, 202 * sizeof(int));
memset(queue, 0, 202 * sizeof(int));
for (i=1; i<point_num; i++)
{
distance[i] = MAX;
}
distance[source] = 0;
head = 0;
tail = 0;
queue[tail++] = source;
in_queue[source] = 1;
while (head < tail)
{
i = queue[head++];
in_queue[i] = 0;
for (j=1; j<point_num; j++)
{
k = table[i][j];
if (k != 0)
{
if ((distance[i] + k) < distance[j])
{
distance[j] = distance[i] + k;
queue[tail++] = j;
in_queue[j] = 1;
}
}
}
}
return distance[destination];
}
int main(void)
{
FILE *fin, *fout;
int i, j, k, temp;
int min = MAX;
fin = fopen("fence6.in", "r");
fout = fopen("fence6.out", "w");
GetInput(fin);
GenerateTable();
for (i=1; i<point_num; i++)
{
for (j=i+1; j<point_num; j++)
{
if(table[i][j] != 0)
{
temp = table[i][j];
table[i][j] = 0;
table[j][i] = 0;
k = temp + SPFA(i, j);
if (k < min)
{
min = k;
}
table[i][j] = temp;
table[j][i] = temp;
}
}
}
fprintf(fout, "%dn", min);
return 0;
}

最后

以上就是雪白滑板为你收集整理的Fence Loops的全部内容，希望文章能够帮你解决Fence Loops所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。