HDU 1031 Jungle Roads
這題就是最小生成樹的模板題，可是這題的數據給的有點坑。
首先我不清楚給出的村莊是否就是按照從A開始的字母順序排列，所以我就用一個exist布爾數組來標記這個村莊是否存在；
在者就是兩個村莊之間可能有多條路，所以存儲的時候應該存儲最小的，可是題目沒有這樣的例子，哎！
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=1<<28;
int road[27][27],mincost[27];
bool used[27],exist[27];
int n;
int solve()
{
fill(mincost,mincost+27,inf);
memset(used,false,sizeof(used));
for(int i=1;i<=26;i++)
if(exist[i])
{
mincost[1]=0;
break;
}
int cost=0;
while(true)
{
int _min=inf,u=-1;
for(int i=1;i<=26;i++)
if(exist[i]&&!used[i]&&_min>mincost[i])
_min=mincost[i],u=i;
if(u==-1)
break;
used[u]=true;
cost+=_min;
for(int i=1;i<=n;i++)
if(exist[i])
mincost[i]=min(mincost[i],road[u][i]);
}
return cost;
}
int main()
{
while(scanf("%d",&n),n!=0)
{
char s1[2],s2[2];
for(int i=0;i<27;i++)
for(int j=0;j<27;j++)
road[i][j]=inf;
int m,k,a,b;
memset(exist,false,sizeof(exist));
for(int i=1;i
