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;
            }