posts - 33,  comments - 33,  trackbacks - 0
题意:给出一个无向图,求在已知顶点v0的度不超过K的情况下,所得的最小生成树
题解:
首先不考虑v0点,先求得v1-v(n-1)的MST,然后分两种情况考虑:
令d为v0的度
情况1 : 当d == 1,时 ,答案显然是min{edge(0,i)}+MST{v1-v(n-1)}
当 1 < d <= K时,考虑逐步添加一条{0-i}边,添加边后势必构成回路,然后在回路中找到
权值最大的边,然后在MST中将这条边删除并修改为{0-i}
代码:
#include <stdio.h>
#include 
<algorithm>
#include 
<iostream>
#include 
<string>
#include 
<map>
using namespace std;

const int V = 21;
const int INF = 1 << 30;
int n;

struct Edge
{
    
int from;
    
int to;
    
int weight;
}
;

map
<string,int> Map;
int graph[V][V];
Edge edges[V];
int vertexNum;
int s;
bool visited[V];//边(0,i)是否在edges中

void init()
{
    memset(visited,
0,sizeof(visited));
    Map.clear();
    
for(int i = 0; i < V; ++i)
    
{
        
for(int j = 0; j < V; ++j)
        
{
            graph[i][j] 
= INF;
        }

    }

}



void input()
{
    
string name1,name2;
    
int dis;
    Map[
"Park"= 0;
    
int k = 1;
    
for(int i = 0; i < n; ++i)
    
{
        cin 
>> name1 >> name2 >> dis;
        
if(Map.find(name1) == Map.end())
            Map[name1] 
= k++;
        
if(Map.find(name2) == Map.end())
            Map[name2] 
= k++;
        
int id1 = Map[name1];
        
int id2 = Map[name2];
        graph[id1][id2] 
= graph[id2][id1] = dis;
    }

    scanf(
"%d",&s);
}


//求v0 - v(_vertexNum-1)的最小生成树
int Prim(int _vertexNum)
{
    
int mstWeight = 0;
    
for(int i = 1; i < _vertexNum - 1++i)
    
{
        edges[i].from 
= 1;
        edges[i].to 
= i + 1;
        edges[i].weight 
= graph[1][i+1];
    }

    
for (int i = 2; i < _vertexNum; ++i)
    
{
        
int id = i-1;
        
int minW = edges[i-1].weight;
        
for (int j = i; j < _vertexNum-1++j)
        
{
            
if (minW > edges[j].weight)
            
{
                minW 
= edges[j].weight;
                id 
= j;
            }

        }

        mstWeight 
+= minW;

        swap(edges[i
-1],edges[id]); 
        
int k = edges[i-1].to;

        
for (int j = i; j < _vertexNum -1++j)
        
{
            
int v = edges[j].to;
            
int w = graph[k][v];
            
if(w < edges[j].weight)
            
{
                edges[j].weight 
= w;
                edges[j].from 
= k;
            }

        }

    }

    
return mstWeight;
}


//返回回路中最大的边
bool isCycle;
void maxWeightInCycle(int _mv,int _from,int _to,int& _maxW,int& _id)
{
    
if (_to == _mv)
    
{
        isCycle 
= true;
        
return;
    }

    
for (int i = 0; i < vertexNum-1++i)
    
{
        
if (edges[i].from != _to && edges[i].to != _to)
        
{
            
continue;
        }

        
if (edges[i].from == _to && edges[i].to != _from)
        
{
            maxWeightInCycle(_mv,_to,edges[i].to,_maxW,_id);
            
if (isCycle)
            
{
                
if (_maxW < edges[i].weight && edges[i].to != 0)
                
{
                    _maxW 
= edges[i].weight;
                    _id 
= i;
                }

                
break;
            }

        }

        
else if(edges[i].to == _to && edges[i].from != _from)
        
{
            maxWeightInCycle(_mv,_to,edges[i].from,_maxW,_id);
            
if (isCycle)
            
{
                
if (_maxW < edges[i].weight && edges[i].from != 0)
                
{
                    _maxW 
= edges[i].weight;
                    _id 
= i;
                }

                
break;
            }

        }

    }

}


void Test()
{
    init();
    input();
    vertexNum 
= Map.size();
    
    
int ans = Prim(vertexNum);//v0 - vn-1
    int minW = INF; 
    
int id = -1;
    
for (int i = 1; i < vertexNum; ++i)
    
{
        
if (minW > graph[0][i])
        
{
            minW 
= graph[0][i];
            id 
= i;
        }

    }

    ans 
+= graph[0][id];
    visited[id] 
= true;
    
//添加边(0,id)
    edges[0].from = 0;
    edges[
0].to = id;
    edges[
0].weight = minW;

    
//枚举顶点0 的度
    for (int d = 2; d <= s; ++d)
    
{
        
int dec = INF;
        
int edgeId = -1;
        id 
= -1;
        
for (int i = 1; i < vertexNum; ++i)
        
{
            
if (visited[i])//已经在MST树中了
            {
                
continue;
            }

            
int maxW = 0,maxId = -1;
            isCycle 
= false;
            
//添加边(0-i),并返回回路最大边
            maxWeightInCycle(0,0,i,maxW,maxId);
            
if (dec > graph[0][i] - maxW)
            
{
                dec 
= graph[0][i] - maxW;
                edgeId 
= maxId;
                id 
= i;
            }

        }

        
if (dec >= 0)
        
{
            
break;
        }

        
else
        
{
            
//将回路最大边删除,并修改为0点的边
            if (edgeId != -1)
            
{
                edges[edgeId].from 
= 0;
                edges[edgeId].to 
= id;
                edges[edgeId].weight 
= graph[0][id];
            }

            visited[id] 
= true;
            ans 
+= dec;
        }

    }

    printf(
"Total miles driven: %d\n",ans);
}


int main()
{
    
//freopen("data.txt","r",stdin);
    while(scanf("%d",&n) != EOF)
    
{
        Test();
    }

    
return 0;
}


posted on 2011-06-02 11:49 bennycen 阅读(1359) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理