題意描述：求出多米諾骨牌中從開始到最后那一塊骨牌倒下所花費的時間。
解題思路：先用Dijkstra算法求出每一個關鍵點倒下時花的時間，然后判斷最后一塊骨牌倒下的位置，以確定其倒下的時間。我們知道最后一塊骨牌要么就是關鍵點，要么在兩個關鍵點之間。如果是在關鍵點之間的情況，假設這兩個關鍵點的時間為t1和題t2，兩點之間的邊長為t3，則最后一塊骨牌倒下所花時間為(t1+t2+t3)/2。
以下是本題代碼：
（漸漸發現，做題不僅僅是比著書上已有的代碼抄一遍那么簡單）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define LEN 510
#define MAX INT_MAX
int mp[LEN][LEN];
int main()
{
int i, j;
int n, m;
int a, b, l;
int count = 1;
scanf("%d%d", &n, &m);
while(m + n != 0)
{
memset(mp, 0, sizeof(mp));
for(i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &l);
mp[a][b] = mp[b][a] = l;
}
int s[LEN] = {0};
int cost[LEN];
int cost1[LEN];
s[1] = 1;
for(i = 1; i <= n; i++)
if(mp[1][i] != 0)
cost[i] = mp[1][i];
else
cost[i] = MAX;
cost[1] = 0;
int t = 1;
for(j = 1; j <= n - 1; j++)
{
t = 1;
int min = MAX;
for(i = 1; i <= n; i++)
if(s[i] == 0 && cost[i] < min)
{
t = i;
min = cost[i];
}
s[t] = 1;
for(i = 1; i <= n; i++)
if(s[i] == 0 && mp[t][i] != 0 && mp[t][i] + cost[t] < cost[i])
cost[i] = mp[t][i] + cost[t];
}
int gard = 1;
double max = -MAX;
int p0;
for(i = 1; i <= n; i++)
if(max < cost[i])
{
max = cost[i];
p0 = i;
}
int p1 = 1;
int p2 = 1;
for(i = 1; i <= n; i++)
for(j = i + 1; j <= n; j++)
{
double x1 = 1.0 * (cost[i] + cost[j] + mp[i][j]) / 2;
if(mp[i][j] != 0 && x1 > max)
{
gard = 0;
max = x1;
p1 = i;
p2 = j;
}
}
if(count++ != 1)
putchar(10);
printf("System #%d\n", count - 1);
if(gard == 1)
{
printf("The last domino falls after %.1lf seconds, at key domino %d.\n", max, p0);
}
else
{
if(p1 > p2)
{
int t1 = p1;
p1 = p2;
p2 = t1;
}
printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n", max, p1, p2);
}
scanf("%d%d", &n, &m);
}
//system("pause");
}
posted on 2012-08-09 20:04
小鼠標 閱讀(225)
評論(0) 編輯 收藏 引用 所屬分類:
圖論