本題描述了一個連接不同城市的道路系統，N個城市之間有M條道路，給出邊的權值。其中有D條道路被破壞，這將導致兩個非常重要的城市A和B之間的通訊中斷。現在要修復被破壞一些已經被破壞的道路，使A和B可以通訊，且使總總造價最小。
對于這題，我的思路是：對于被破壞的公路，權值為原來的權值；沒有被破壞的，因為不需要重建，即重建的造價為0，所以權值修改為0，轉化為了求A和B之間最短路徑的題目。
我是用begin[i]和end[i]記錄被破壞道路的起點和終點，這樣做需要注意一點，即在構造新圖的時候，必須仍舊是無向圖。為了代碼的簡潔，程序中用到了goto語句。
我的代碼如下：
#include<stdio.h>
#define MAXN 101
#define MAXINT 200000000
long n,m,d,a,b,g[MAXN][MAXN],begin[220],end[220];
void solve()
{
long i,j,k,min,g2[MAXN][MAXN],dist[MAXN],visit[MAXN];
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
{
if(g[i][j]!=MAXINT)
g2[i][j]=0;
else g2[i][j]=MAXINT;
}
for(i=1;i<=d;i++)
{
g2[begin[i]][end[i]]=g[begin[i]][end[i]];
g2[end[i]][begin[i]]=g[end[i]][begin[i]];
}
// Init
for(i=0;i<=n;i++)
visit[i]=0;
visit[a]=1;
for(i=1;i<=n;i++)
dist[i]=g2[a][i];
dist[a]=0;
for(i=1;i<=n;i++)
{
min=MAXINT;
k=0;
for(j=1;j<=n;j++)
if(!visit[j]&&dist[j]<min)
{
min=dist[j];
k=j;
}
if(k==0) break;
visit[k]=1;
for(j=1;j<=n;j++)
if(!visit[j]&&dist[k]+g2[k][j]<dist[j])
dist[j]=dist[k]+g2[k][j];
}
printf("%ld\n",dist[b]);
}
void run()
{
long i,j,t1,t2,w;
RUN_BEGIN:
scanf("%ld",&n);
if(n==0) return;
scanf("%ld",&m);
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
g[i][j]=MAXINT;
for(i=1;i<=m;i++)
{
scanf("%ld%ld%ld",&t1,&t2,&w);
g[t1][t2]=w;
g[t2][t1]=w;
}
scanf("%ld",&d);
for(i=1;i<=d;i++)
scanf("%ld%ld",&begin[i],&end[i]);
scanf("%ld%ld",&a,&b);
solve();
goto RUN_BEGIN;
}
int main()
{
freopen("rebuild.in","r",stdin);
freopen("rebuild.out","w",stdout);
run();
return 0;
}
posted on 2010-01-06 19:56
lee1r 閱讀(505)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論