http://poj.org/problem?id=1639
最小限制生成树 黑书上有 推荐 我看了上面的解析自己闷头写了一个 不好 我自己看着都乱 唉就这样吧
大体就是 先求出除了关键点以外的点形成的若干最小生成树 然后把这些最小生成树和关键点用最短的距离联系起来
然后不断点加与关键点之间的的连线 每联一个就会多一个环 然后就得删一个边 把环取消 不过加的边 和删的边的选取必须是加边减去删边的
值最小 一旦限度达到 或者更新后不如原来的小了 则放弃更新
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<map>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int N=101;
const int M=10000;
struct node
{
int k;
struct tt *next;
}mem[N];//邻接表头 k 表示到此点到基本点的边中 不和基本点相连的边中最长的边
struct tt
{
int wside;
struct tt *next;
int j;
};//wside 代表哪条边
struct lin
{
int x,y;
int dist;
}linkside[M];//记录边的两端 和距离
int have[M];//此条边的状态 1 表示最图中 -1 表示删掉不再用 0表示待定
int f[N];//最小生成树中的最终父节点 和dfs是标记是否搜过那个点
int m,k,limit,n;//m为边的个数 n为点的个数 limit为限度 k和基本点相连的度
map<string,int>str;
int MIN,V0;//在限制的情况下最小树 和基本点
int findx(int x)//你懂得
{
if(f[x]!=x)
f[x]=findx(f[x]);
return f[x];
}
bool cmp(lin a,lin b)
{
return a.dist<b.dist;
}
void build(int ,int ,int );
void prim()
{
sort(linkside,linkside+m,cmp);
memset(have,0,sizeof(have));
for(int i=0;i<n;++i)
f[i]=i;
for(int i=0;i<m;++i)
{
int l1=linkside[i].x,l2=linkside[i].y;
if(findx(l1)==findx(l2))//如果有环 此边不要
{
have[i]=-1;
continue;
}
if(l1!=V0&&l2!=V0)//不是有基本点的边
{
have[i]=1;//记录边状态
MIN+=linkside[i].dist;//增加全局变量
f[findx(l1)]=l2;
build(l1,l2,i);//建树
build(l2,l1,i);
}else
{
if(l1==V0)//如果为基本点相连的边 建树但不记录
build(l1,l2,i);
else
build(l2,l1,i);
}
}
}
void build(int i,int j,int l)
{
struct tt *t=new tt;
t->j=j;
t->wside=l;
t->next=mem[i].next;
mem[i].next=t;
}
void Dele(int n)
{
struct tt *t;
for(int i=0;i<=n;++i)
{
while(mem[i].next!=NULL)
{
t=mem[i].next;
mem[i].next=t->next;
delete (t);
}
}
}
void dfs(int x,int k)
{
f[x]=1;
mem[x].k=k;//更新到此点为止最长边（不含和基本点相连的）
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(!f[t->j]&&have[t->wside]==1)
{
int down=(linkside[k].dist<linkside[t->wside].dist)?t->wside:k;//选择较长的向下更新
dfs(t->j,down);
}
t=t->next;
}
}
void update()
{
memset(f,0,sizeof(f));
f[V0]=1;
struct tt *t=mem[V0].next;
while(t!=NULL)
{
if(have[t->wside]==1)
{
dfs(t->j,m);//第m条边 已被定义为距离最小
}
t=t->next;
}
}
int main()
{
//freopen("data.txt","r",stdin);
string sstemp1,sstemp2,park="Park";
while(scanf("%d",&m)!=EOF)
{
str.clear();
int I=0;
V0=-1;
for(int i=0;i<m;++i)
{
int l1,l2,d;
cin>>sstemp1>>sstemp2>>d;
if(str.find(sstemp1)==str.end())//用map 把字符串对应成数字
{str[sstemp1]=I;l1=I++;}
else
l1=str[sstemp1];
if(str.find(sstemp2)==str.end())
{str[sstemp2]=I;l2=I++;}
else
l2=str[sstemp2];
linkside[i].x=l1;
linkside[i].y=l2;
linkside[i].dist=d;
if(V0==-1)//记录基本点
{
if(sstemp1==park)
V0=l1;
if(sstemp2==park)
V0=l2;
}
}
n=I;
scanf("%d",&limit);
MIN=0;
prim();//建立除了基本点以外的若干 最小生成树
linkside[m].dist=-1;
k=0;
for(int i=0;i<m;++i)
{
if(have[i]!=0)
continue;
int l1=linkside[i].x,l2=linkside[i].y;
if(findx(l1)==findx(l2))
continue;
if(l1==V0)//对和基本点相连的边进行选最小的更新 但不能形成环 做相应的记录
{
have[i]=1;
f[findx(l1)]=l2;
++k;
MIN+=linkside[i].dist;
}
if(l2==V0)
{
have[i]=1;
f[findx(l1)]=l2;
++k;
MIN+=linkside[i].dist;
}
}
update();//更新每个点到基本点的边中最长的（不含和基本点直接相连的）
for(;k<limit;++k)
{
int wtemp=-1,ktemp,mitemp;
struct tt *t=mem[V0].next;
while(t!=NULL)
{
if(have[t->wside]==0)//选新的和基本点相连的点
{
if(wtemp==-1||linkside[t->wside].dist-linkside[mem[t->j].k].dist<mitemp)
{
wtemp=t->wside;
mitemp=linkside[t->wside].dist-linkside[mem[t->j].k].dist;
ktemp=mem[t->j].k;
}
}
t=t->next;
}
if(wtemp==-1||mitemp>=0)//如果没选到 或者更新后无法跟新最终答案 则没有必要继续更新
{
break;
}
have[wtemp]=1;
have[ktemp]=-1;
MIN+=mitemp;
update();
}
printf("Total miles driven: %d\n",MIN);
Dele(n);
}
return 0;
}