poj1639 Picnic Planning 最小度数限制生成树「建议收藏」

题意：若干个人开车要去park聚会，可是park能停的车是有限的，为k。所以这些人要通过先开车到其它人家中，停车，然后拼车去聚会。另外，车的容量是无限的，他们家停车位也是无限的。

求开车总行程最短。

       就是求一最小生成树，可是对于当中一个点其度不能超过k。

思路：

1. 将park点取出 将剩下的点求出最小生成树  出现i个联通块

2. 再每一个块中选择与park点相邻的最小边  

到此park点已经连了i条边

park点最大能够连接k个点

得到Sum值

3. 须要求出i+1–>k 条的Sum值

每次加入一条边在树上形成一个环 然后 删去一条环上的边（权值最大）取Sum=min（Sum，Sum+加入边-删去边）  复杂度O(n^2)

由于第三步复杂度高须要优化第三步

优化：先记录Vi->Vp路径上且不与Vp直接相连的边的权值的Max[ i ]

加入边时 取cost(Vi,Vp)-Max [ i ]最小值 加入(Vi,Vp)边

再枚举ViVp原有的路径上不与Vp相连的边，找到最大权值的边；

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn =111+5;
const int maxe = 15000+5;
const int INF = 460002326;
#include <map>
map<string,int>mp;
map<string,int>::iterator it;
int car,n,cost[maxn][maxn],sum,father[maxn];
int best[maxn];
bool vis[maxn];
bool edge[maxn][maxn];
bool use[maxn];
void dfs(int root)//将一个连通块中各个点标记其father
{
    for(int i=1; i<n; i++)
    {
        if(vis[i]&&edge[root][i])
        {
            father[i]=root;
            vis[i]=false;
            dfs(i);
        }
    }
}
void prim(int s)
{
    int Min_i,Min,dis[maxn],num[maxn];
    memset(vis,false,sizeof(vis));
    for(int i=0; i<n; i++)
    {
        dis[i]=cost[i][s];
        num[i]=s;//此时dis[i]的值来自哪个点
    }
    dis[s]=0;
    vis[s]=use[s]=true;
    while(true)
    {
        Min=INF,Min_i=-1;
        for(int i=0; i<n; i++)
        {
            if(!use[i]&&!vis[i]&&(Min_i==-1||Min>dis[i]))
            {
                Min_i=i;
                Min=dis[i];
            }
        }
        if(Min==INF)    break;
        sum+=Min;
        vis[Min_i]=true;
        use[Min_i]=true;//标记连通块用过的点
        edge[Min_i][num[Min_i]]=edge[num[Min_i]][Min_i]=true;
        for(int i=0; i<n; i++)
        {
            if(!use[i]&&!vis[i]&&dis[i]>cost[i][Min_i])
            {
                num[i]=Min_i;
                dis[i]=cost[i][Min_i];
            }
        }
    }
    Min=INF;
    int root=-1;
    for(int i=0; i<n; i++)//寻找该连通块到Park点的最小距离
    {
        if(vis[i]&&cost[0][i]<Min&&i!=0)//在这棵树中
        {
            Min=cost[0][i];
            root=i;
        }
    }
    vis[root]=false;
    dfs(root);//以root为根
    father[root]=0;
    sum+=Min;
}
int Best(int j)//更新当中各个点到park路径上边权值最大的点
{
    if(father[j]==0)//假设father为0，记为-1
        return best[j]=-1;
    if(best[j]!=-1) return best[j];//假设已经存在 。直接返回
    int tmp=Best(father[j]);
    if(tmp!=-1)//这说明其父节点不与park相连
    {
        if(cost[tmp][father[tmp]]>cost[father[j]][j])
            best[j]=tmp;
        else best[j]=j;
    }
    else best[j]=j;//其父节点与source相连  将j赋给自己
    return best[j];
}
void solve()
{
    int mst=0;
    memset(father,-1,sizeof(father));
    memset(use,0,sizeof(use));
    memset(edge,false,sizeof(edge));
    use[0]=true;
    for(int i=0; i<n; i++)
    {
        if(!use[i])//use用过要标记
        {
            prim(i);//除Park外建最小生成树
            mst++;
        }
    }
    for(int i=mst+1; i<n&&i<=car; i++)
    {
        memset(best,-1,sizeof(best));
        for(int j=0; j<n; j++)
        {
            if(j!=0&&best[j]==-1&&father[j]!=0)
                    Best(j);
        }
        int minadd=INF;
        int ax,bx,change;
        for(int j=0; j<n; j++)
        {
            if(cost[0][j]!=INF&&father[j]!=0)
            {
                ax=best[j];
                bx=father[ax];
                if(minadd>cost[0][j]-cost[ax][bx])//cost[0][j]表示加入的边 cost[ax][bx]表示断开的边
                {                                                       
                    minadd=cost[0][j]-cost[ax][bx];//更新减小的值以及连接的点
                    change=j;
                }
            }
        }
        if(minadd>=0)   //表示要添加sum值    则已经得到最小的sum值
            break;
        sum+=minadd;//更新
        ax=best[change];
        bx=father[ax];
        cost[ax][bx]=cost[bx][ax]=INF;
        father[change]=0;
        cost[0][change]=cost[change][0]=INF;
    }
}
int main()
{
    int t;
   // freopen("in.txt","r",stdin);
    cin>>t;
    mp.clear();
    string s1,s2;
    int val;
    for(int i=0; i<maxn; i++)
        for(int j=0; j<maxn; j++)
            cost[i][j]=INF;
    n=1,sum=0;
    mp["Park"]=0;//Park为0；
    for(int i=0; i<t; i++)
    {
        cin>>s1>>s2>>val;
        it=mp.find(s1);//map映射值
        if(it==mp.end())
            mp[s1]=n++;
        it=mp.find(s2);
        if(it==mp.end())
            mp[s2]=n++;
        if(cost[mp[s1]][mp[s2]]>val)//可能会有重边。其实没有。。。。
。            cost[mp[s1]][mp[s2]]=cost[mp[s2]][mp[s1]]=val;    }    cin>>car;    solve();    cout<<"Total miles driven: "<<sum<<endl;    return 0;}