acleast

这是我有史以来写得最长的一个程序，前段时间就看了这个题，在网上搜了一下算法，当时看得还有点不太明白，大牛也都说这题代码太长
不好写，开始写了一些，后面发现不会写了，就放下了。昨天又来看这个题，居然写出来了，不过还是花了我一个晚上的时间来调试，开始
交一次结果就RE了，后来在网上找来了官方数据一个一个的运行才发现找圈DFS的时候陷入了死循环，加了一个标志变量，还是WA，后来
反复看解思路才知道换边的时候每一次循环最多只能换一次，而且要换差值最大的那条边，又加了一个优先队列，才终于攻下这道题。

题目大意是：
矮人虽小却喜欢乘坐巨大的轿车，轿车大到可以装下无论多少矮人。某天，N(N≤5000)个矮人打算到野外聚餐。为了集中到聚餐地点，矮人A要么开车到矮人B家中，留下自己的轿车在矮人B家，然后乘坐B的轿车同行；要么直接开车到聚餐地点，并将车停放在聚餐地。
虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放K辆轿车。现在给你一张加权无向图，它描述了N个矮人的家和聚餐地点，要你求出所有矮人开车的最短总路程。

    [输入文件]
第一行是整数M(M<=49000)，接下来M行描述了M条道路。每行形式如同：S1 S2 x，S1和S2均是大于0小于5000的整数，x小于等于1000。最后一行包含两个整数k，root。root表示聚餐的地点。

    [输出文件]
仅一行，形式如同：Total miles driven: xxxXxx是整数，表示最短总路程。

解题思路：

　　1)将根节点从图中去除掉
　　2)对去除根节点的图求MST，注意这里去除根后的图可能是不连通的，所以计算MST的时候要对每个连通图都进行计算
这里我选择用Kruscal算法+并查集求MST.求完后用DFS将属于同一个连通分量的点放在一个数组里面，并得到连通分量的个数。
　　3)针对每一个连通分量，选择从根节点到这个连通分量里的节点的具有最小权值的边加入图中，假设有deep个连通分
量则一共需要加deep条边
　　4)由1)2)3)步骤即得到一棵deep最小限度生成树
　　5)假设题目限定的停车位数是k,那么还需要找k - deep条从根节点出发的边，所以循环k- deep次，每次做
如下操作：
    　　a)假设对于节点k, 边[root, j, w]不在当前树中(权值为w), 那么如果把这条边加入树中就会构成一条环
    　　b)假设这个环中不是与根直接相连的具有最大权值的边为[from, to, weight]
    遍历寻找具有最大weight - w值的边，如果这个差值大于0，则将这条边[root, j]加入树中并去除边[from, to]，如果差值小于等于0则退出

以下是我的代码：

  1#include<iostream>
  2#include<string>
  3#include<vector>
  4#include<algorithm>
  5#include<map>
  6#include<queue>
  7using namespace std;
  8#define N 25
  9
 10struct node{
 11    int id;
 12    int u,v;
 13    int len;
 14    const bool operator<(const node &b)const{
 15        return len<b.len;
 16    }
 17}edge[N*N];
 18
 19map<string,int> name;
 20int pre[N];
 21int data[N][N];　//存储两点之间的距离
 22int num[N];
 23bool dd[N][N];　//标志边是否在生成树中
 24bool mark[N];
 25
 26int stack[N][N];
 27int n,k,size;
 28int sum,deep;
 29
 30void init()
 31{
 32    int m,w,u,v;
 33    string str1,str2;
 34    map<string,int>::iterator mp;
 35    name["Park"]=0;
 36    memset(link,0,sizeof(link));
 37    deep=size=n=0;
 38    sum=0;
 39    cin>>m;
 40    for(int i=1;i<=m;i++){
 41        cin>>str1>>str2>>w;
 42
 43        mp=name.find(str1);
 44        if(mp!=name.end())
 45            u=mp->second;
 46        else{
 47            n++;
 48            name[str1]=n;
 49            u=n;
 50        }
 51        
 52        mp=name.find(str2);
 53        if(mp!=name.end()) 
 54            v=mp->second;
 55        else{
 56            n++;
 57            name[str2]=n;
 58            v=n;
 59        }        
 60        if(u&&v){
 61            edge[size].u=u;
 62            edge[size].v=v;
 63            edge[size].len=w;
 64            size++;
 65        }    
 66        if(!data[u][v])   //防止重边
 67            data[u][v]=data[v][u]=w;
 68        else{
 69            data[u][v]=min(w,data[u][v]);
 70            data[v][u]=data[u][v];
 71        }
 72    }
 73    cin>>k;
 74}
 75
 76int find(int i)
 77{
 78    if(i==pre[i]) return i;
 79    return pre[i]=find(pre[i]);
 80}
 81//kruskal求最小生成树
 82void mst()
 83{
 84    int p,q;
 85    sort(edge,edge+size);
 86    for(int i=1;i<=n;i++) pre[i]=i;
 87    for(int i=0;i<size;i++){
 88        p=find(edge[i].u);
 89        q=find(edge[i].v);
 90        if(p!=q){
 91            dd[edge[i].u][edge[i].v]=true;
 92            dd[edge[i].v][edge[i].u]=true;
 93            pre[p]=q;
 94            sum+=edge[i].len;
 95        }
 96    }
 97}
 98
 99void dfs(int i)　//寻找连能分量
100{
101    num[i]=deep;
102    stack[deep][0]++;
103    stack[deep][stack[deep][0]]=i;
104    for(int j=1;j<=n;j++){
105        if(dd[i][j]&&!num[j])
106            dfs(j);
107    }
108}
109
110bool tdfs(int i){
111    mark[i]=true;
112    if(i==0) return true;
113    for(int j=0;j<=n;j++){
114        if(dd[i][j]&&data[i][j]&&!mark[j]){
115            pre[j]=i;
116            mark[j]=true;
117            if(tdfs(j))
118                return true;
119            mark[j]=false;
120        }
121    }
122    return false;
123}
124void solve()
125{
126    mst();
127    for(int i=1;i<=n;i++){
128        if(!num[i]){
129            deep++;
130            dfs(i);　　//寻找连通分量，将同一个连通分量的点放在stack[deep]中
131        }
132    }
133    
134    for(int i=1;i<=deep;i++){　//在每一个连通分量中找一个离0点最近的点，添加到生成树中
135        int mi=INT_MAX,minj;
136        for(int j=1;j<=stack[i][0];j++){
137            if(mi>data[0][stack[i][j]]&&data[0][stack[i][j]]){
138                mi=data[0][stack[i][j]];
139                minj=stack[i][j];
140            }
141        }
142        dd[0][minj]=true;
143        dd[minj][0]=true;
144        sum+=mi;
145    }
146    priority_queue<node> myque;
147    node stem;
148    int from,to,w;
149    for(int i=1;i<=k-deep;i++){
150        while(!myque.empty()) myque.pop();
151        for(int j=1;j<=n;j++){
152            if(!dd[0][j]&&data[0][j]){
153                memset(mark,false,sizeof(mark));
154                memset(pre,0,sizeof(pre));
155                from=to=0;
156                int w=0;
157                tdfs(j);　//在所形成的圈中找一条data[from][to]-data[0][j]最大的边
158                int tp=0;
159                while(pre[tp]){　//找到那条边
160                    if(data[pre[tp]][tp]>w){
161                        w=data[pre[tp]][tp];
162                        from=pre[tp];
163                        to=tp;
164                    }
165                    tp=pre[tp];
166                }
167                if(from&&to&&data[from][to]>data[0][j]){
168                    stem.id=j;　
169                    stem.u=from;
170                    stem.v=to;
171                    stem.len=data[from][to]-data[0][j];
172                    myque.push(stem);　//将所找到的边添加到优先队列中
173                }                
174            }
175        }
176        if(myque.empty()) break;
177        stem=myque.top();
178        sum-=stem.len;
179        dd[stem.v][stem.u]=dd[stem.u][stem.v]=false;
180        dd[0][stem.id]=dd[stem.id][0]=true;
181    }　//在找到的边中找出data[from][to]-data[0][j]最大的边
182    cout<<"Total miles driven: "<<sum<<endl;
183}
184
185int main()
186{
187    init();
188    solve();
189    return 0;
190}
191