pku1639最小限度生成树.txt

MST算法就是最小生成树算法！ 在ACM中这个应该是比较简单的一个算法！ 大家好好学习吧！

/*
PKU 1639  最小度限制生成树模板
http://www.cppblog.com/ACM-Boy/archive/2008/07/30/57547.html
22-03-09 01:50
  Name:ecjtuqx
  Copyright: qiuxiong
  Author: qiuxiong
  Date: 22-03-09 01:50
  Description: 
题目大意：
一些人想从各自的家中开车到一个地方野餐，每个人的家中都可以容纳无限多的车子，
每个人的车子可以容纳无限多的人。每个人可以先开车到另一人家中，将车停在那人家中，
两人（或多人）再开同一辆车开往目的地。但野餐的地方只有有限个停车位k，告诉你一些路程的长度，
问你将所有人都聚集再野餐地点，所使用的最短路程是多少。
思路：
因为题目中说到，一个人可以先开车到其他人家中，然后他们再一起开车前往目的地，
所以将问题抽象出来，将各人的家和目的地看作点，将各个路程看作边，若没有目的地停车位（点的度）的限制，
问题就可以转化为求最小生成树的问题。但加上了对某一点度的限制，问题就变得复杂了。
假设，若我们将度限制条件放在一边，直接求最小生成树。如果在最小生成树中，
目的地所在点的度数已经满足degree <= k，那么度限制生成树就已经得到了。因为不可能有比它权值和更小的生成树了，
并且点的度数满足条件。
还有一种情况，那就是先按最小生成树算法得到的生成树中，目的地所在点的度数degree > k，
那么很自然的，我们就要想到删去degree-k条树中与规定点相连的边，使得它满足度限制要求。
每删去边之后，都要再加上一条边，否则图就会不连通，但是，又应该怎样删边呢？假设，规定点的度数为t，
那么就有t根与规定点相连的子树T1、T2、……、Tt，若删去Ti与规定点相连的那条边，Ti这棵子树就“悬空”了，
必须将Ti这棵树“架”到其他子树上才可以。经过这样一次的“删添”操作之后，修改之后的图仍然是棵树，
但规定点的度数减少了1，只要这样进行t-k次，就可以得到满足条件的度限制生成树了。但怎样保证最小呢？
只要在每次的“删添”操作时，保证“添”的边的权值减去“删”的边的权值的差值（必大于等于0）最小就可以了。
除了这种方法，lrj的书上还介绍了另一种方法。其大致思想是：现将规定点以及与它相连的边都去掉，
再在剩下的图中求出每个连通分量的最小生成树，在进行“差额最小添删操作”，求出满足度限制的情况下的可能的权值，
在其中不断更新树的权值和。具体算法将黑书P300~P303。
*/
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 50;
struct Edge 
{
   int a, b;
   int len;
};
vector<Edge> edge;
map<string, int> nameIndex;
int G[MAX][MAX];
int tree[MAX][MAX];
int n, m, k;
int parkIndex;
int degree[MAX];
int treeDegree[MAX];
int p[MAX];
int inTree[MAX];
int rank[MAX];
int minCost;
int treeTag[MAX];             //对子树进行标记
int visited[MAX];
int subTreeNum;
bool operator< (Edge e1, Edge e2)
{
   return ( e1.len < e2.len );
}
void Input ()
{  
    string a, b;
    int index1, index2;
    int len;
    Edge e;
    n = 0;
    cin>>m;
    for(int i=0;i<m;i++)
    {
       cin>>a>>b>>len;
       if(nameIndex.find(a)==nameIndex.end())
       {
          nameIndex[a]=n;
          index1=n;
          n++;
       }
       else             
       {
          index1=nameIndex[a];
       }
       if(nameIndex.find(b)==nameIndex.end())
       {
          nameIndex[b]=n;
          index2=n;
          n++;
	   }
	   else
	   {
		   index2 = nameIndex[b];
	   }
	   if(a=="Park")
		   parkIndex=index1;
       if(b=="Park")
		   parkIndex=index2;
       G[index1][index2]=G[index2][index1]=len;
       e.a=index1;
       e.b=index2;
       e.len=len;
       edge.push_back(e);
       degree[index1]++;
       degree[index2]++;
	}
	cin>>k;
}
int Find(int x)
{
	int t,root,w;
    t=x;
    while(p[t]!=-1)
         t=p[t];
    root=t;
    t=x;
    while(p[t]!=-1)
    {
      w=p[t];
      p[t]=root;
      t=w;
    }
    return root;
}
void Union(int x,int y)
{
	int r1, r2;
    r1=Find(x);
    r2=Find(y);
    if(rank[r1]>=rank[r2])
	{
		p[r2]=r1;
		if(rank[r1]==rank[r2])
			rank[r1]++;
    }
    else
		p[r1] = r2;
}
bool Kruskal()
{
	int i, r1, r2, k, total, Max;
	memset(p, -1, sizeof(p));
    memset(inTree, 0, sizeof(inTree));
    memset(rank, 1, sizeof(rank));
	//qsort(edge, edgeNum, sizeof(edge[0]), cmp);
    sort(edge.begin(), edge.end());
    Max=-1;
    k=0;
    minCost=0;
    for(i=0;i<edge.size()&&k<n-1;i++)
    {
		r1=Find(edge[i].a);
        r2=Find(edge[i].b);
        if(r1!=r2)
        {
			tree[edge[i].a][edge[i].b]=tree[edge[i].b][edge[i].a]=edge[i].len;
             Union(r1, r2);
             inTree[i]=1;
             treeDegree[edge[i].a]++;
             treeDegree[edge[i].b]++;
			 k++;
			 minCost+=edge[i].len;
         }
    }
   if(k==n-1)
        return true;
    else           
		return false;
}
void DFS (int cur, int index)
{

  visited[cur]=1;
  treeTag[cur]=index;
  int i;
  for(i=0;i<n;i++)
  {
	  if(tree[cur][i]&&!visited[i])
	  {
		  DFS(i,index);
	  }
  }
}
void MakeTreeTag ()
{
	int i;
    subTreeNum=0;
    memset(visited,0,sizeof(visited));
         visited[parkIndex]=1;
    memset(treeTag, -1, sizeof(treeTag));
    for(i=0;i<n;i++)
    {
		if(tree[parkIndex][i])
			DFS(i,subTreeNum++);
    }
}
//将原来的子树架在另一棵树上
void ChangeTreeTag (int pre, int cur)
{
	int i;
	for (i=0;i<n;i++)
		if(treeTag[i]==pre)
			treeTag[i]=cur;
}
//从当前子树查找与其他子树相连的最小边
Edge FindMinEdge (int curTag)
{
	int i;
    Edge e;
    e.len=-1;
    for(i=0;i<edge.size();i++)
    {
		if(((treeTag[edge[i].a]==curTag&&treeTag[edge[i].b]!=curTag&&edge[i].b!=parkIndex)||(treeTag[edge[i].b]==curTag&&treeTag[edge[i].a]!=curTag&&edge[i].a!=parkIndex))&&G[edge[i].a][edge[i].b])
           {
			if(e.len==-1||edge[i].len<e.len)
            {
				  e.a=edge[i].a;
                  e.b=edge[i].b;
                  e.len = edge[i].len;
                           
			}
		}
	}
  return e;
}
void DeleteAdd ()
{
	int i,minDif,delTag,newTag;
    minDif=-1;
    Edge addEdge, delEdge, temp;
    for(i=0;i<n;i++)
    {
		if(i==parkIndex)
			continue;
          temp=FindMinEdge(treeTag[i]);
        if(temp.len==-1)
			continue;
        if(tree[parkIndex][i]&&(minDif==-1||temp.len-tree[parkIndex][i]<minDif))
          {
			minDif=temp.len-tree[parkIndex][i];
			addEdge=temp;
            delEdge.a=parkIndex;
            delEdge.b=i;
            delTag=treeTag[i];
            if(treeTag[addEdge.a]!=delTag)
               newTag=treeTag[addEdge.a];
             else
				 newTag=treeTag[addEdge.b];
           }
         }
         tree[delEdge.a][delEdge.b]=tree[delEdge.b][delEdge.a]=0;
         G[delEdge.a][delEdge.b]=G[delEdge.b][delEdge.a]=0;
         tree[addEdge.a][addEdge.b]=tree[addEdge.b][addEdge.a]=addEdge.len;
         minCost += minDif;
         ChangeTreeTag(delTag, newTag);
}
void Solve ()
{
    Kruskal();
    if(treeDegree[parkIndex]<=k)
      {
         cout<<"Total miles driven: "<<minCost<<endl;
              return;
      }
    MakeTreeTag();
    int i;
    for(i=0;i<treeDegree[parkIndex]-k;i++)
        DeleteAdd();
    cout<<"Total miles driven: "<<minCost<<endl;
}
int main()
{
	Input();
    Solve();
    return 0;
}
/*
10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3
Sample Output
Total miles driven: 183
*/