程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj1639 Picnic Planning 最小度數限制生成樹

poj1639 Picnic Planning 最小度數限制生成樹

編輯：C++入門知識

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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn =111+5;
const int maxe = 15000+5;
const int INF = 460002326;
#include 
mapmp;
map::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; idis[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; icost[i][Min_i])
            {
                num[i]=Min_i;
                dis[i]=cost[i][Min_i];
            }
        }
    }
    Min=INF;
    int root=-1;
    for(int i=0; icost[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; icost[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>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: "<