| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 669 人关注过本帖
标题:这个中国邮路问题不太懂,有人帮我解释一下吗
只看楼主 加入收藏
王叫兽Joe
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2014-5-23
结帖率:33.33%
收藏
已结贴  问题点数:10 回复次数:4 
这个中国邮路问题不太懂,有人帮我解释一下吗
#include <limits.h>
#include <iostream>
#include <cstdlib>
#include <set>
#include <vector>
using namespace std;
#define MAX_NODE 26
#define COST_NO_LINK    INT_MAX
int Graph[MAX_NODE][MAX_NODE];
int Cost[MAX_NODE][MAX_NODE];
int V_dingdianshu, E_bianshu, Start_Point;
int Odd_Grouping[MAX_NODE];
int Bak_Odd_Grouping[MAX_NODE];
int SHORTEST_PATH_WEIGHT(COST_NO_LINK);
int Dist[MAX_NODE];
int ShortCache[MAX_NODE][MAX_NODE];
void Input()//构造图
{
    int i, j;
    int m, n;
    char cs, cm, cn;
    int w;
    cout << "输入图的顶点数:";
    cin >> V_dingdianshu;
    cout << "输入图边的数目:";
    cin >> E_bianshu;
    cout << "输入起点:";
    cin >> cs;
    Start_Point = cs - 'a';
    for(i = 0; i < V_dingdianshu; i++)
    {
        for(j = 0; j < V_dingdianshu; j++)
        {
            Graph[i][j] = 0;
            ShortCache[i][j] = 0;
            Cost[i][j] = COST_NO_LINK;
        }
        Cost[i][i] = 0;
    }

    cout << "输入" << E_bianshu << "条边对应的顶点和权值(顶点从开始编号):" << endl;
    for(i = 0; i < E_bianshu; i++)
    {
        cin >> cm >> cn >> w;
        m = cm - 'a';
        n = cn - 'a';
        Graph[m][n] += 1;
        Graph[n][m] += 1;
        Cost[m][n] = w;
        Cost[n][m] = w;
    }
}
int Dijstra(int v0, int v1, bool useCache)
{
    if(useCache && ShortCache[v0][v1] != 0)
        return ShortCache[v0][v1];
    int i, s, w, min, minIndex;
    bool Final[MAX_NODE];
    for (s = 0; s < V_dingdianshu; s++)
    {
        Final[s] = false;
        Dist[s] = COST_NO_LINK;
    }
    Final[v0] = true;
    Dist[v0] = 0;
    s = v0;
    for (i = 0; i < V_dingdianshu; i++)
    {
        for(w = 0; w < V_dingdianshu; w++)
        {
            if(!Final[w]
                && Cost[s][w] < COST_NO_LINK
                && Dist[w] > Dist[s] + Cost[s][w])
            {
                if(Dist[s] + Cost[s][w] <= 0)
                {
                    cout << "求最短路径数据溢出。" << endl;
                    exit(-1);
                }
                Dist[w] = Dist[s] + Cost[s][w];
            }
        }
        if(s == v1)
        {
            ShortCache[v0][v1] = Dist[s];
            ShortCache[v1][v0] = Dist[s];
            return Dist[s];
        }
        min = COST_NO_LINK;
        for(w = 0; w < V_dingdianshu; w++)
        {
            if(!Final[w]
                && Dist[w] < min)
            {
                minIndex = w;
                min = Dist[w];
            }
        }
        s = minIndex;
        Final[s] = true;
    }
    cout << "程序异常!应该早找到了最短路径!" << endl;
    exit(-1);
}
bool ConnectivityTest(int start, bool& bNoPoints)
{
    set<int> nodeSet;
    vector<int> for_test_nodes;
    int i, j;
    set<int> singlePoints;
    bool hasEdge = false;
    for(i = 0; i < V_dingdianshu; i++)
    {
        hasEdge = false;
        for(j = 0; j < V_dingdianshu; j++)
        {
            if (Graph[i][j] > 0)
            {
                hasEdge = true;
                break;
            }
        }
        if (!hasEdge)
        {
            singlePoints.insert(i);
        }
    }
    bNoPoints = (singlePoints.size() == V_dingdianshu);
    if(singlePoints.find(start) != singlePoints.end())
        return false;
    for_test_nodes.push_back(start);
    while(for_test_nodes.size() > 0)
    {
        int testNode = for_test_nodes.back();
        for_test_nodes.pop_back();
        for(i = 0; i < V_dingdianshu; i++)
        {
            if(Graph[testNode][i] > 0)
            {
                if(nodeSet.insert(i).second)
                    for_test_nodes.push_back(i);
            }
        }
    }
    for(i = 0; i < V_dingdianshu; i++)//检测图的连通性
        if (singlePoints.find(i) == singlePoints.end()
            && nodeSet.find(i) == nodeSet.end())
            return false;
    return true;
}
int OddTest()//检测图中的奇度点
{
    int i, j, rSum, count;
    for(i = 0; i < V_dingdianshu; i++)
    {
        Odd_Grouping[i] = 0;
        Bak_Odd_Grouping[i] = 0;
    }
    count = 0;
    for(i = 0; i < V_dingdianshu; i++)
    {
        rSum = 0;
        for(j = 0; j < V_dingdianshu; j++)
        {
            rSum += Graph[i][j];
        }
        if(rSum % 2 == 1)
        {
            Odd_Grouping[i] = 1;
            count++;
        }
    }
    return count;
}
void Bak_Grouping()
{
    int i;
    for(i = 0; i < V_dingdianshu; i++)
        Bak_Odd_Grouping[i] = Odd_Grouping[i];
}
bool Grouping(int level)
{
    if(level < 2)
    {
        cout<< "小于的level值是不允许的。" << endl;
        exit(-1);
    }
    int i, j, findI = -1;
    for(i = 0; i < V_dingdianshu; i++)
    {
        if(Odd_Grouping[i] == 1)
        {
            Odd_Grouping[i] = level;
            findI = i;
            break;
        }
    }
    bool re = true;
    if(findI == -1)
    {
        int weightSum = 0;
        for(i = 2; i < level; i++)
        {
            int index[2];
            int *pIndex = index;
            for(j = 0; j < V_dingdianshu; j++)
            {
                if(Odd_Grouping[j] == i)
                {
                    *pIndex = j;
                    if(pIndex == index + 1) break;
                    pIndex++;
                }
            }
            weightSum += Dijstra(index[0], index[1], true);
        }

        if(weightSum < SHORTEST_PATH_WEIGHT)
        {
            Bak_Grouping();
            SHORTEST_PATH_WEIGHT = weightSum;
            return true;
        }
        else return false;
    }
    else if(findI > -1)
    {
        for(; i < V_dingdianshu; i++)
        {
            if(Odd_Grouping[i] == 1)
            {
                Odd_Grouping[i] = level;
                re = Grouping(level + 1);
                Odd_Grouping[i] = 1;
            }
        }
    }
    else
    {
        cout<< "findCount值异常!" << endl;
        exit(-1);
    }
    if(findI > -1) Odd_Grouping[findI] = 1;
    return re;
}
void AddShortPath(int from, int to)//添加最短路径
{
    int i, back;
    Dijstra(from, to, false);
    back = to;
    while(back != from)
    {
        for(i = 0; i < V_dingdianshu; i++)
        {
            if(i != back
                && Dist[i] < COST_NO_LINK
                && Dist[back] < COST_NO_LINK
                && Dist[i] + Cost[i][back] == Dist[back])
            {
                Graph[i][back]++;
                Graph[back][i]++;
                back = i;
                break;
            }
        }
        if(i == V_dingdianshu)
        {
            cout << "程序异常,最短路径出问题了。" << endl;
            exit(-1);
        }
    }
}
void AddShortPaths()
{
    int i, j;
    for(i = 0; i < V_dingdianshu; i++)
    {
        if(Bak_Odd_Grouping[i] > 1)
        {
            for(j = i + 1; j < V_dingdianshu; j++)
            {
                if(Bak_Odd_Grouping[j] == Bak_Odd_Grouping[i])
                {
                    AddShortPath(i, j);
                    break;
                }
            }
        }
    }
}
void OddDeal()
{
    int oddCount = OddTest();
    if(oddCount > 0)
    {
        if(oddCount % 2 == 1)
        {
            cout << "这是个奇怪的图,存在奇数个奇度顶点的连通图吗?" << endl;
            exit(-1);
        }
        Grouping(2);
        AddShortPaths();
    }
}
void Fleury(int start)//弗洛伊德算法
{
    int i;
    int vi = start;
    bool bNoPoints, bCnecTest;
    cout << "你要的结果:";
    while(true)
    {
        for(i = 0; i < V_dingdianshu; i++)
        {
            if (Graph[vi][i] > 0)
            {
                Graph[vi][i]--;
                Graph[i][vi]--;
                bCnecTest = ConnectivityTest(i, bNoPoints);
                if(!bNoPoints && !bCnecTest)
                {
                    Graph[vi][i]++;
                    Graph[i][vi]++;
                    continue;
                }
      cout << (char)('a' + vi) << "-" << (char)('a' + i) << " ";
                vi = i;
                break;
            }
        }
        if (i == V_dingdianshu)
        {
            cout << endl;
            break;
        }
    }
}
int main()//主函数
{
    Input();
    bool b;
    if(!ConnectivityTest(0, b))
    {
        cout << "该图不是连通图!\n";
        exit(0);
    }
    OddDeal();
    Fleury(Start_Point);
    system("PAUSE");
    return 0;
}
搜索更多相关主题的帖子: include 中国 
2014-07-05 09:18
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6815
专家分:42393
注 册:2010-12-16
收藏
得分:5 
好长,

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2014-07-05 12:55
l3456
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:80
专家分:133
注 册:2014-4-16
收藏
得分:5 
好长

走向光明的菜鸟学生,励志成为新一代程序猿
2014-07-06 09:44
午夜小学徒
Rank: 2
等 级:论坛游民
威 望:3
帖 子:52
专家分:40
注 册:2014-7-17
收藏
得分:0 
卖萌的啊
2014-08-02 16:04
午夜小学徒
Rank: 2
等 级:论坛游民
威 望:3
帖 子:52
专家分:40
注 册:2014-7-17
收藏
得分:0 
看的眼晕
2014-08-02 16:30
快速回复:这个中国邮路问题不太懂,有人帮我解释一下吗
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.038286 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved