#include?
#include?
#include?

#define?min（ab）?（?（a）?#define?MAX_NODE?100
#define?MAX_EDGE?100
#define?INF?0x7fffffff??????//?表示兩點不連通

typedef?struct?
{
????int?number;???//?標記位
????int?cost;?????//?結(jié)點間距
????int?dis;??????//?結(jié)點最近距離
}Node;

typedef?struct?
{
????int?from;?????//?邊起點
????int?to;???????//?邊終點
????int?dis;??????//?邊距離
}Edge;

int?n?m;??????????????????????????????//?點的個數(shù)和邊的個數(shù)
int?total_edge?odd_point;?????????????//?總邊數(shù)和奇點數(shù)
Node?map[MAX_NODE][MAX_NODE];??????????//?結(jié)點連接情況
int?point[MAX_NODE];???????????????????//?每個結(jié)點的度數(shù)
int?need_add_num?min_count?edge_num;?//?需要添加邊的個數(shù)??
Edge?odd_edge[MAX_EDGE];
int?point_flag[MAX_EDGE];
int?min_edge[MAX_EDGE];
int?tmp_edge[MAX_EDGE];
int?top;
int?finish_flag?=?0;
int?path_stack[MAX_EDGE];



void?Floyd（）
{
????//?比較i到j(luò)直達近還是從i到k加上k到j(luò)近。添加的結(jié)點k放在最外層循環(huán)。
????for?（int?k?=?1;?k?<=?n;?k++）
????????for?（int?i?=?1;?i?<=?n;?i++）
????????????if（map[i][k].dis?!=?INF）
????????????{
????????????????for?（int?j?=?1;?j?????????????????????if（map[k][j].dis?!=?INF）
????????????????????{
????????????????????????map[i][j].dis?=?map[j][i].dis?=?min（map[i][j].dis?map[i][k].dis?+?map[k][j].dis）;
????????????????????}
????????????}
}

void?search_edge（int?count?int?step）
{
????//?深度尋找距離最短的添加最優(yōu)方案
????//?step用于記錄數(shù)量，count記錄最短長度
????//?尋找路徑存入了數(shù)組中，可通過i訪問

????if?（step?==?need_add_num）
????{
????????if?（count?????????{
????????????for?（int?i?=?0;?i?????????????{
????????????????min_edge[i]?=?tmp_edge[i];
????????????}
????????????min_count?=?count;
????????}
????????return;
????}
????int?a?b?c;
????for?（int?i?=?0;?i?????{
????????a?=?odd_edge[i].from;
????????b?=?odd_edge[i].to;
????????c?=?odd_edge[i].dis;
????????if?（point_flag[a]?==?1?&&?point_flag[b]?==?1）
????????????//?如果兩點均未相連
????????{
????????????point_flag[a]?=?point_flag[b]?=?0;????//?置標記位為0
????????????tmp_edge[step]?=?i;
????????????search_edge（count?+?c?step?+?1）;
????????????point_flag[a]?=?point_flag[b]?=?1;
????????}
????}
}

void?dijkstra_to_add_edge（int?s?int?e）?//用dijkstra算法確定從該始點到終點的最短路徑
{
????int?dis[MAX_NODE];???????//?點到起始（s）點的距離
????int?used[MAX_NODE];??????//?標記位
????int?pre[MAX_NODE];???????//?記錄其從哪一點過來的，方便回溯

????memset（used?0?sizeof（used））;???//?初始化
????for?（int?i?=?1;?i?<=?n;?i++）
????{
????????dis[i]?=?INF;
????}
????dis[s]?=?0;

????while?（1）
????{
????????int?v?=?-1;
????????for?（int?i?=?1;?i?<=?n;?i++）
????????{
????????????if?（!used[i]?&&?（v?==?-1?||?dis[i]?????????????{
????????????????v?=?i;
????????????}
????????}
????????if?（v?==?e?||?v?==?-1）
????????//?當當前點是末點e時或本身v就是最小時
????????????break;
????????used[v]?=?1;????//?修改標記位
????????for?（int?i?=?1;?i?<=?n;?i++）
????????{
????????????if?（map[v][i].cost?????????????{
????????????????pre[i]?=?v;
????????

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????15641??2018-04-28?13:28??研討代碼以及測試用例\Debug\main.o

?????文件??????64197??2018-04-28?13:28??研討代碼以及測試用例\Debug\yantao.exe

?????文件?????????53??2018-04-23?14:51??研討代碼以及測試用例\in1.txt

?????文件?????????44??2018-04-23?15:01??研討代碼以及測試用例\in2.txt

?????文件?????????63??2018-04-23?16:04??研討代碼以及測試用例\in3.txt

?????文件?????????68??2018-04-23?16:07??研討代碼以及測試用例\in4.txt

?????文件?????????39??2018-04-23?14:19??研討代碼以及測試用例\in5.txt

?????文件?????????42??2018-04-26?10:42??研討代碼以及測試用例\in6.txt

?????文件???????7583??2018-04-28?13:28??研討代碼以及測試用例\main.cpp

?????文件?????????37??2018-04-28?13:18??研討代碼以及測試用例\out1.txt

?????文件?????????31??2018-04-28?13:22??研討代碼以及測試用例\out2.txt

?????文件?????????40??2018-04-28?13:24??研討代碼以及測試用例\out3.txt

?????文件?????????43??2018-04-28?13:26??研討代碼以及測試用例\out4.txt

?????文件?????????25??2018-04-28?13:28??研討代碼以及測試用例\out5.txt

?????文件?????????34??2018-04-28?13:17??研討代碼以及測試用例\out6.txt

?????文件???????1478??2018-04-28?13:39??研討代碼以及測試用例\yantao.mdsp

?????文件?????173433??2018-04-28?12:21??DS研討第七題—第十四小組.pptx

?????目錄??????????0??2018-04-28?13:28??研討代碼以及測試用例\Debug

?????目錄??????????0??2018-04-28?13:39??研討代碼以及測試用例

-----------?---------??----------?-----??----

???????????????262851????????????????????19