Poj 1639 K度限最小生成树

题意：给出一个无向图，求在已知顶点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;
            }

补充：软件开发 , C语言 ,