pku1639
這題郁悶啊，手抄prayer的模板都抄不對~~~
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<stdio.h>
#include<string>
#define N1 110
using namespace std;
int const INF=100000000;
int cost[N1][N1];//花費 = 邊
int used[N1][N1];//表示這條邊是否在生成樹中
int father[N1];//生成樹中點的父節點
int maxlen[N1];//表示i點到根路徑上除了與根直接相連的邊外，邊權最大的邊權
int vis[N1];//標記
int d[N1]; //求最小生成樹時的最小生成樹代價
int AnsMst;//當前m度生成樹的代價
int N, degree, lim;//degree表示最小限度，lim表示限度值
int g[N1][N1];//生成樹中的兒子關系，正向表
map<string, int> mat;
void MST(int S) //求從S點開始的最小生成樹
{
while(1){
int K=-1;
for(int i=1; i<=N; i++){
if(!vis[i] && d[i]!=INF && (K==-1||d[K]>d[i]))
K=i;
}
if(K==-1) break;
vis[K]=1;
AnsMst+=d[K];
g[father[K]][++g[father[K]][0]]=K;//記錄兒子
if(d[K]!=0) maxlen[K] = max(maxlen[father[K]], d[K]);//算邊權最大的邊
used[K][father[K]] = used[father[K]][K] = 1;//標記邊在生成樹中
for(int i=1; i<=N; i++){
if(!vis[i] && cost[K][i]<d[i]){
father[i]=K;
d[i]=cost[K][i];
}
}
}
}
void Build()
{
for(int i=1; i<=N; i++)
father[i]=i;
for(int i=1; i<=N; i++)
d[i]=INF;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
used[i][j] = 0;//所有的邊都在生成樹外
for(int i=1; i<=N; i++)
g[i][0]=0; //兒子數全為0
for (int i = 1; i <= N; i++) vis[i] = 0; // 標記清空
vis[1]=1;
degree=0;
maxlen[1]=-INF; //根的maxlen為-INF;
AnsMst=0; //開始時生成樹的代價為0
while(1){
int K=-1;
for(int i=1; i<=N; i++){
if(!vis[i] && (K==-1 ||cost[1][i]<cost[1][K]))
K=i; //找個距根邊權最小的點開始做最小生成樹
}
if(K==-1) break;
father[K]=1; //father 為 1
maxlen[K]=-INF; //maxlen[k]=--INF;
d[K]=0;
degree++;//連通分支個數加1
AnsMst+=cost[1][K]; //生成樹代價增加
MST(K);
}
}
void Init()//開始的輸入處理
{
mat.clear();
mat["Park"]=1;
N=1;
int M;
scanf("%d", &M);
for(int i=1; i<=30; i++)
for(int j=1; j<=30; j++)
cost[i][j]=INF;
while(M--){
string a, b;
int c;
cin>>a>>b>>c;
int ida, idb;
if(mat.find(a)==mat.end()) mat[a]=++N, ida=N;
else ida=mat[a];
if(mat.find(b)==mat.end()) mat[b]=++N, idb=N;
else idb=mat[b];
cost[ida][idb]=cost[idb][ida]=c;
}
scanf("%d", &lim);
}
void Dfs(int nod, int fa) //更新維護maxlen和生成樹中的父子關系
{
father[nod]=fa;
vis[nod]=1;
if(fa==1) maxlen[nod]=-INF;
else
maxlen[nod]=max(maxlen[fa], cost[nod][fa]);
for(int i=1; i<=g[nod][0]; i++)
if(used[nod][g[nod][i]]&&!vis[g[nod][i]])
Dfs(g[nod][i], nod);
}
void Solve(){
if(degree>lim)
printf("Error\n");
int ans=AnsMst;
while(degree<lim){
degree++;
int id=-1;
int delta=INF;
for(int i=1; i<=N; i++){//找代價最小的進行擴張
if(cost[1][i]!=INF && !used[1][i]){
if(id==-1){
id=i;
delta=cost[1][i]-maxlen[i];
continue;
}
if(cost[1][i]-maxlen[i]<delta){
id=i;
delta=cost[1][i]-maxlen[i];
}
}
}
if(id==-1){ break;}
AnsMst+=delta;//加上delta值
ans=min(ans, AnsMst);
int Len=maxlen[id];
used[1][id]=used[id][1]=1;//表示邊被加入到當前的生成樹中
g[1][++g[1][0]]=id; //表示根多加了一個兒子
while(cost[id][father[id]]!=Len){//找最大的邊，并順路維護兒子關系
int fa=father[id];
g[id][++g[id][0]]=fa;
id=fa;
}
used[id][father[id]]=used[father[id]][id]=0;//標記邊被刪去
for(int i=1; i<=N; i++)
vis[i]=0;
Dfs(1, 1);//維護
}
printf("Total miles driven: %d\n", ans);
}
int main()
{
Init();
Build();
Solve();
return 0;
}