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;
}