2017华为软件挑战赛刚开始的时候，和队友花了一个月的时间开始弄，期间艰难困苦，有喜有悲，最好的时候排名到第一名，最差的也跑到倒数了，学习了很多东西，也知道自己很多东西还不会，写下留个纪念。
这个题目是在一定前提下，求最小费用流，我们的想法很简单，就是先找到每条最短路径，把所有消费节点看成一个超级汇点，然后随机确定服务器，找到每次分配费用流时候的最短路径，在该路径上添加最大流量，直到满足所有消费节点的流量位置，由于没有很好的确定服务器，导致最后在找服务器方面废了很多功夫，最后采取的策略是：先把所有消费节点放上服务器，然后随机选择若干服务器，一个一个删除，找到删除后能得到最低费用的服务器，然后删掉这个服务器，继续删，一直删到不能删为止，然后随机添加服务器，替换当前服务器，从而得到当前最优~
用过退火算法，但是可能没写好，比直接随机还差，最后直接随机了，这个题目最好是用其他算法，之前结构已经定性了，就没有改了，虽然有点遗憾，不过走到这里已经不遗憾了。
其他算法可以选择整数规划、单纯性、ZKW等其他最优解算法。现在比赛还没结束，所以就发初赛的代码吧，，，大家随便看看就行~
最让人失望的是：没近4强，竟然发99块钱的手环，真是low爆了，上去唱个歌都可以拿到的手环和音响就是99块钱，前四是手机，几千块，差距太大了，不得不说，真的low爆了，对华为很失望、车票也没报，而且办事效率太低，无语。
#include "deploy.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include <cstring>
#include <queue>
#include <iostream>
#include "math.h"
using namespace std;#ifdef WIN32
#define LOCALTIME_R(t) localtime((t))
#else
#define LOCALTIME_R(t) localtime_r((t), (struct tm *)&tmres)
#endif #define _DEBUG#define INLINE static __inline
#ifdef _DEBUG
#define PRINT printf
#else
#define PRINT(...)
#endif#define MODE_LOW 200
#define MODE_Middle 500#define UsingDistance
#define UsingRoombool IsUsingRoom = false;struct GraphStruct CurrentGragh; //当前得到的表结构体形式
struct GraphStruct CurrentGragh_Temp;unsigned short ConnectedLength_Min[Max_NetNodeNum][Max_NetNodeNum] = { 0 }; //定义任意两点之间最小距离
unsigned short ConnectedMin_ID[Max_NetNodeNum][Max_NetNodeNum] = { 0 }; //定义任意两点这间最小距离的ID链接，起始点，终止点，结果上一个的编号
unsigned short ConnectedLength_Min_Temp[Max_NetNodeNum][Max_NetNodeNum] = { 0 }; //定义任意两点之间最小距离
unsigned short ConnectedMin_ID_Temp[Max_NetNodeNum][Max_NetNodeNum] = { 0 }; //定义任意两点这间最小距离的ID链接，起始点，终止点，结果上一个的编号
bool IsInited = false;unsigned short ExpensePointID[Max_NetNodeNum] = { 0 }; //消费节点绑定的ID号，比实际的ID号大1，实际操作的时候减1
unsigned short SumLength[Max_NetNodeNum][2] = { 0 }; //所有的消费节点距离普通节点的距离之和short Path[Max_NetNodeNum][Max_LineNum][Max_LineNum] = { 0 }; //消费节点路径 一维：消费节点ID 二维:消费节点路径条数 三维：路径内容unsigned short Path_Num[Max_NetNodeNum][2] = { 0 }; //一维：消费节点ID 二维:0表示这是当前ID的第几条路径，1表示该路径有多少个点unsigned short PathExpense[Max_NetNodeNum][Max_NetNodeNum] = { 0 }; //占用带宽 一维：消费节点ID 二维:占用带宽数
unsigned short UnsatifiedPoint[Max_NetNodeNum] = { 0 };//当前网络不能满足的点，编号+1，实际操作时减1
unsigned short UnsatifiedNum = 0; //未满足的网络编号数量
bool IsSatified = false;
unsigned short SelectedServerNum = 1; //选中节点的数量
unsigned short NetPathALL = 0; //总路径条数unsigned short PreSearchedPath[Max_NetNodeNum] = { 0 };//上一次服务器编号
unsigned short PreServerNum = 0; //上一次服务器数量unsigned short NowSearchedPath[Max_NetNodeNum] = { 0 };//当前服务器编号
unsigned short NowServerNum = 0; //当前服务器数量
unsigned short DeleteNum = 0; //删除的点号
unsigned long ChargeALL = 0; //所有费用计算
unsigned long PreChargeALL = 0; //所有费用计算
unsigned short Cant_Delete[Max_NetNodeNum] = { 0 };
unsigned int CantDeleteNum = 0;unsigned short SinglePoint[Max_NetNodeNum] = { 0 }; //孤立节点编号
unsigned short SinglePointNum = 0; //孤立节点数量unsigned short ConnectRelation[Max_NetNodeNum][Max_NetNodeNum] = { 0 }; //节点之间的链接关系
unsigned short ConnectNum[Max_NetNodeNum] = { 0 }; //与该节点的链接个数unsigned short addnum[Max_NetNodeNum][2] = { 0 }; //服务器排序
unsigned short ExpenceClosedServer[Max_NetNodeNum][2] = { 0 }; //找消费节点最近的服务器unsigned short BandWidth[TEXT_LineNum][4] = { 0 }; //0表示起始点，1表示终点，2表示流量,3表示单价
unsigned short BandWidthNum = 0; //普通节点文件行数unsigned short ExpenseBandNeed[Max_NetNodeNum] = { 0 }; //消费节点需要的带宽unsigned short ExpensePointSum[Max_NetNodeNum][2] = { 0 }; //消费节点与和它最近的消费节点的点数累计 0表示累计数，1表示标号/*****************************************************************************/
unsigned short ConnectedNodePoint[Max_NetNodeNum][MaxConnect] = { 0 }; //用来保存与消费节点相关的点，一维下标是消费节点编号，从0开始，二维下标是相关的点
unsigned short ConnectedNodePointNum[Max_NetNodeNum] = { 0 }; //用来保存与消费节点相关的点的个数
unsigned short ConnectedExpensePoint[Max_NetNodeNum][MaxConnect] = { 0 }; //用来保存普通节点被哪些消费节点遍历了，一维是普通节点的编号，二维是消费节点的编号
unsigned short ConnectedExpensePointNum[Max_NetNodeNum] = { 0 }; //用来保存每个普通节点被遍历了几次
unsigned short NodeNum[Max_NetNodeNum][2] = { 0 }; //记录普通节点相关的点数
unsigned short SortNode[Max_NetNodeNum] = { 0 }; //得到普通节点排序的结果
/*******************************************************************************///*****************************************************************************
//计算Dijstala所需要的变量以及更新服务器的变量
unsigned short SearchedPoint[Max_NetNodeNum] = { 0 }; //定义已经找到的点，找到的话置为累计长度
unsigned short ConnectedMin_ID_Test[Max_NetNodeNum][Max_NetNodeNum] = { 0 }; //定义任意两点这间最小距离的ID链接，起始点，终止点，结果上一个的编号
unsigned short PaiXu[Max_NetNodeNum] = { 0 };
unsigned short ConnectedNum_Pre[Max_NetNodeNum][2] = { 0 };//高位表示第几个点，低位0表示被搜的编号，1表示搜到最小值的编号
unsigned short LastPoint[Max_NetNodeNum] = { 0 }; //一共找到的点数组
unsigned short SameLegthPoint[Max_NetNodeNum] = { 0 }; //当前层找到的最短路径数组
unsigned short RepeatBuf[Max_NetNodeNum] = { 0 }; //重复的Buf
//********************************************************************************//********************************************************************************
//模拟退火算法参数
#define Mapkob_Line 27
#define AccuracyOut 1
#define ControlT 10000000
#define ControlPara 0.3
#define Q 1.5float ControlT_Para = 0;unsigned short Mapkob_L = 0;
unsigned short CurrentServerBuf[Max_NetNodeNum]={0};
unsigned short CurrentServerNum = 0;
unsigned long CurrentExpense = MaxMoney;
//********************************************************************************#define NewPointNum 4void deploy_server(char * topo[MAX_EDGE_NUM], int line_num, char * filename)
{time_t long_time_start, long_time_end;time(&long_time_start); /* Get time as long integer. */long int TimeRunning = 0;// 需要输出的内容//char * topo_file2 = (char *)"17\n\n0 8 0 20\n21 8 0 20\n9 11 1 13\n21 22 2 20\n23 22 2 8\n1 3 3 11\n24 3 3 17\n27 3 3 26\n24 3 3 10\n18 17 4 11\n1 19 5 26\n1 16 6 15\n15 13 7 13\n4 5 8 18\n2 25 9 15\n0 7 10 10\n23 24 11 23";char topo_file[MAX_EDGE_NUM] = { 0 };unsigned short TopoNum = 0;GetGraph(topo, line_num); //获取图表信息if (CurrentGragh.NetNodeNum <= MODE_LOW) IsUsingRoom = false; //判断工作类型，点数少时使用距离计算else IsUsingRoom = true; //点数多时用容量计算//判断孤立节点GetSinglePoint(); //寻找孤立节点LenthSum(); //确定服务器排序SelectedServerNum = 40; //从3个服务器开始搜UnsatifiedNum = CurrentGragh.ExpenseNum;NowServerNum = SelectedServerNum;PreServerNum = SelectedServerNum;GetExpenseMin();if (true){NowServerNum = 0; PreServerNum = 0;for (int i = 0; i < CurrentGragh.ExpenseNum; i++){NowSearchedPath[NowServerNum++] = ExpensePointID[i] - 1;PreSearchedPath[PreServerNum++] = ExpensePointID[i] - 1;}UpdateMaxie(); //更新数据矩阵UpdateServerAll(NowServerNum);//更新服务器位置IsSatified = GetMaxFlow(); //计算并判断是否满足情况if (IsSatified == true) ChargeALL = GetCharge(topo_file, false);//得到当前方案满足的钱数}if (CurrentGragh.NetNodeNum <= MODE_LOW) { PreServerNum = NowServerNum; NowServerNum = NowServerNum; ChargeALL = MaxMoney; }//点数小时，全局搜索找最优else if (CurrentGragh.NetNodeNum <= MODE_Middle) { PreServerNum = NowServerNum; PreServerNum = NowServerNum; ChargeALL = MaxMoney; } //中级else {PreServerNum = NowServerNum = NowServerNum;} //高级SelectedServerNum = NowServerNum; //服务器个数PreServerNum = SelectedServerNum;NowServerNum = SelectedServerNum; //重新赋值PreChargeALL = ChargeALL; //保存上次钱数static long TempCharge = PreChargeALL;static long TempDeleteNum = 0;static bool IsDelete = false;static float aaa;static float bbb;int Temp1 = 0;ControlT_Para = ControlT;//****************************************************************初中级方案 start*********************************************************************while (CurrentGragh.NetNodeNum <= MODE_Middle){for (int i = PreServerNum - 1; i >= 0; i--) //循环次数{time(&long_time_end); /* Get time as long integer. */TimeRunning = long_time_end - long_time_start;if (TimeRunning >= 89) break;UpdateMaxie(); //更新数据矩阵DeleteNum = i; NowServerNum = 0;for (int DeleteCheck = 0; DeleteCheck < CantDeleteNum; DeleteCheck++){if (DeleteNum == Cant_Delete[DeleteCheck]){IsDelete = true;break;}}if (IsDelete == true) { IsDelete = false; continue; }for (int j = 0; (j < PreServerNum); j++){if ((j != DeleteNum))NowSearchedPath[NowServerNum++] = PreSearchedPath[j];//更新路径}SelectedServerNum = NowServerNum; //当前点数UpdateServerAll(NowServerNum);//更新服务器位置IsSatified = GetMaxFlow(); //计算并判断是否满足情况if (IsSatified == true){ChargeALL = GetCharge(topo_file, false); //得到当前方案的钱数if (TempCharge > ChargeALL) { TempCharge = ChargeALL; TempDeleteNum = DeleteNum; }//if (CurrentGragh.NetNodeNum > MODE_Middle) break; }}else{bool IsCanInput = true;for (int l = 0; l < CantDeleteNum; l++){if (PreSearchedPath[DeleteNum] == Cant_Delete[l]) IsCanInput = false;}if (IsCanInput == true) Cant_Delete[CantDeleteNum++] = PreSearchedPath[DeleteNum];continue;}}if (TempCharge < PreChargeALL){NowServerNum = PreServerNum; PreServerNum = 0;PreChargeALL = TempCharge;for (int j = 0; (j < NowServerNum); j++){if ((j != TempDeleteNum))PreSearchedPath[PreServerNum++] = PreSearchedPath[j];//更新路径}}else if (TempCharge == PreChargeALL) break;}//加点删除策略***************************************************************************************if (CurrentGragh.NetNodeNum <= MODE_Middle){CurrentServerNum = 0;for (int i = 0; i < PreServerNum; i++) CurrentServerBuf[CurrentServerNum++] = PreSearchedPath[i];TempCharge = MaxMoney; CurrentExpense = PreChargeALL; PreChargeALL = MaxMoney;}while (CurrentGragh.NetNodeNum <= MODE_Middle){time(&long_time_end); /* Get time as long integer. */TimeRunning = long_time_end - long_time_start;if (TimeRunning >= 89) break;PreServerNum = 0;for (int i = 0; i < CurrentServerNum; i++) PreSearchedPath[PreServerNum++] = CurrentServerBuf[i];TempCharge = MaxMoney; PreChargeALL = MaxMoney;unsigned short AddPointNum = 0;unsigned short PointTemp = 0;for (int i = 0; i < NewPointNum;) //添加随机点{PointTemp = rand() % (CurrentGragh.NetNodeNum - 1); //产生0-PreServerNum-1的随机数bool IsInBuf = false;for (int j = 0; j < PreServerNum; j++){if (PointTemp == PreSearchedPath[j]){IsInBuf = true;break;}}if (IsInBuf == true) continue;PreSearchedPath[PreServerNum++] = PointTemp;i++;}memset(Cant_Delete, 0, Max_NetNodeNum*sizeof(unsigned short));while (CurrentGragh.NetNodeNum <= MODE_Middle){for (int i = PreServerNum - 1; i >= 0; i--) //循环次数{time(&long_time_end); /* Get time as long integer. */TimeRunning = long_time_end - long_time_start;if (TimeRunning >= 89) break;UpdateMaxie(); //更新数据矩阵DeleteNum = i; NowServerNum = 0;for (int DeleteCheck = 0; DeleteCheck < CantDeleteNum; DeleteCheck++){if (DeleteNum == Cant_Delete[DeleteCheck]){IsDelete = true;break;}}if (IsDelete == true) { IsDelete = false; continue; }for (int j = 0; (j < PreServerNum); j++){if ((j != DeleteNum))NowSearchedPath[NowServerNum++] = PreSearchedPath[j];//更新路径}SelectedServerNum = NowServerNum; //当前点数UpdateServerAll(NowServerNum);//更新服务器位置IsSatified = GetMaxFlow(); //计算并判断是否满足情况if (IsSatified == true){ChargeALL = GetCharge(topo_file, false); //得到当前方案的钱数if (TempCharge > ChargeALL) { TempCharge = ChargeALL; TempDeleteNum = DeleteNum; }//if (CurrentGragh.NetNodeNum > MODE_Middle) break; }}else{bool IsCanInput = true;for (int l = 0; l < CantDeleteNum; l++){if (PreSearchedPath[DeleteNum] == Cant_Delete[l]) IsCanInput = false;}if (IsCanInput == true) Cant_Delete[CantDeleteNum++] = PreSearchedPath[DeleteNum];continue;}}if (TempCharge < PreChargeALL){NowServerNum = PreServerNum; PreServerNum = 0;PreChargeALL = TempCharge;for (int j = 0; (j < NowServerNum); j++){if ((j != TempDeleteNum))PreSearchedPath[PreServerNum++] = PreSearchedPath[j];//更新路径}}else if (TempCharge == PreChargeALL) break;}if (CurrentExpense > PreChargeALL){CurrentServerNum = 0; CurrentExpense = PreChargeALL;for (int i = 0; i < PreServerNum; i++)CurrentServerBuf[CurrentServerNum++] = PreSearchedPath[i];}PRINT("当前费用：%d", CurrentExpense);PRINT("计算费用：%d", PreChargeALL);PRINT(" 当前时间：%d", TimeRunning);PRINT(" 当前服务器数：%d\n", PreServerNum);}if (CurrentGragh.NetNodeNum < MODE_Middle){PreServerNum = 0; PreChargeALL = CurrentExpense;for (int i = 0; i < CurrentServerNum; i++) PreSearchedPath[PreServerNum++] = CurrentServerBuf[i];}//****************************************************************高级方案 start*********************************************************************while (CurrentGragh.NetNodeNum > MODE_Middle){for (int MapkobLine = 0; MapkobLine < Mapkob_Line; MapkobLine++) //Mapkob 链长{time(&long_time_end); /* Get time as long integer. */TimeRunning = long_time_end - long_time_start;if (TimeRunning >= 90) break;UpdateMaxie(); //更新数据矩阵DeleteNum = rand() % (PreServerNum - 1); //产生0-PreServerNum-1的随机数NowServerNum = 0;for (int DeleteCheck = 0; DeleteCheck < CantDeleteNum; DeleteCheck++){if (DeleteNum == Cant_Delete[DeleteCheck]){IsDelete = true;break;}}if (IsDelete == true) { IsDelete = false; continue; }for (int j = 0; (j < PreServerNum); j++){if ((j != DeleteNum))NowSearchedPath[NowServerNum++] = PreSearchedPath[j];//更新路径}SelectedServerNum = NowServerNum; //当前点数UpdateServerAll(NowServerNum);//更新服务器位置IsSatified = GetMaxFlow(); //计算并判断是否满足情况if (IsSatified == true){ChargeALL = GetCharge(topo_file, false); //得到当前方案的钱数if (TempCharge > ChargeALL) { TempCharge = ChargeALL; TempDeleteNum = DeleteNum; }//if (CurrentGragh.NetNodeNum > MODE_Middle) break; }}else{bool IsCanInput = true;for (int l = 0; l < CantDeleteNum; l++){if (PreSearchedPath[DeleteNum] == Cant_Delete[l]) IsCanInput = false;}if (IsCanInput == true) Cant_Delete[CantDeleteNum++] = PreSearchedPath[DeleteNum];continue;}}if (TempCharge < PreChargeALL){NowServerNum = PreServerNum; PreServerNum = 0;PreChargeALL = TempCharge;for (int j = 0; (j < NowServerNum); j++){if ((j != TempDeleteNum))PreSearchedPath[PreServerNum++] = PreSearchedPath[j];//更新路径}}else if (TempCharge == PreChargeALL) break;PRINT("当前费用：%d", PreChargeALL);PRINT(" 当前时间：%d", TimeRunning);PRINT(" 当前服务器数：%d\n", NowServerNum);}SelectedServerNum = NowServerNum;NowServerNum = PreServerNum; NetPathALL = 0;if (CurrentGragh.NetNodeNum <= MODE_Middle) //初级和中级，服务器交换{for (int i = 0; i < NowServerNum; i++) NowSearchedPath[i] = PreSearchedPath[i];for (int i = 0; i < CurrentGragh.ExpenseNum; i++) //判断某个消费节点是不是服务器{bool IsServer = false;unsigned short SearchedServerNum = 0;for (int j = 0; j < NowServerNum; j++) //判断该消费节点是不是服务器，是第几个服务器{if (ExpensePointID[i] - 1 == NowSearchedPath[j]){IsServer = true;SearchedServerNum = j;break;}}if (IsServer == false) continue;//如果该消费节点不是服务器，直接继续搜消费节点上的服务器//找到与该消费节点最近的消费节点，判断是不是服务器unsigned short ClosedLength = MaxERROR,CloseNum=0,Temp=0;for (int j = 0; j < CurrentGragh.ExpenseNum; j++) //找到最短路径的消费节点{if (j != i){Temp = ConnectedLength_Min_Temp[ExpensePointID[i] - 1][ExpensePointID[j] - 1];//当前距离if (Temp < ClosedLength){ClosedLength = Temp;CloseNum = j;}}}IsServer = false;for (int j = 0; j < NowServerNum; j++) //判断该消费节点是不是服务器，是第几个服务器{if (ExpensePointID[CloseNum] - 1 == NowSearchedPath[j]){IsServer = true;SearchedServerNum = j;break;}}if (IsServer == false) //如果该节点不是服务器，把该节点置为服务器，交换{NowSearchedPath[SearchedServerNum] = ExpensePointID[CloseNum] - 1;UpdateMaxie(); //更新数据矩阵UpdateServerAll(NowServerNum); //更新服务器位置IsSatified = GetMaxFlow(); //计算并判断是否满足情况ChargeALL = GetCharge(topo_file, false); //得到当前方案的钱数if ((IsSatified==true)&&(ChargeALL < PreChargeALL)) //当前钱数降了{continue;}else{NowSearchedPath[SearchedServerNum] = ExpensePointID[i] - 1;}}}}else{//for (int i = 0; i < CurrentServerNum; i++) NowSearchedPath[i] = CurrentServerBuf[i];NowServerNum = PreServerNum;for (int i = 0; i < NowServerNum; i++) NowSearchedPath[i] = PreSearchedPath[i];}//当前算得的点数大于消费节点数，或者当前消费大于直接放在服务器的消费数，直接把服务器放在消费节点位置上if ((NowServerNum >= CurrentGragh.ExpenseNum) || (PreChargeALL>CurrentGragh.ExpenseNum*CurrentGragh.ServerCost)){PreServerNum = CurrentGragh.ExpenseNum;NowServerNum = CurrentGragh.ExpenseNum;for (int i = 0; i < CurrentGragh.ExpenseNum; i++){NowSearchedPath[i] = ExpensePointID[i] - 1; //服务器位置}}UpdateMaxie(); //更新数据矩阵UpdateServerAll(NowServerNum); //更新服务器位置IsSatified = GetMaxFlow(); //计算并判断是否满足情况ChargeALL = GetCharge(topo_file, true); //得到当前方案的钱数if (IsSatified == true) PRINT("\n答案正确！\n");else PRINT("\n答案错误!\n");/*char aaa[2];itoa(10, aaa, 10);*/unsigned short PreID = 0;unsigned short NowID = 0;int kk = 0;bool IsContinue = false;//*************************************************写入文件系统start****************************************************//sprintf(&topo_file[0], "%ld", NetPathALL); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;sprintf(&topo_file[TopoNum++], "%s", "\n"); sprintf(&topo_file[TopoNum++], "%s", "\n"); for (int x = 0; x < NowServerNum; x++){for (int i = 0; i < CurrentGragh.ExpenseNum; i++) //消费节点{for (int j = 0; j < Path_Num[i][0]; j++) //消费节点边数{PreID = ExpensePointID[i] - 1;//消费节点IDkk = 0;for (kk = 0; Path[i][j][kk] != -1; kk++) {} kk--;if (kk == -1) kk = 0;if ((Path[i][j][kk] == NowSearchedPath[x]))IsContinue = true;if (IsContinue == true){while (kk >= 0){sprintf(&topo_file[TopoNum], "%ld", Path[i][j][kk]); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;sprintf(&topo_file[TopoNum], "%s", " "); TopoNum++;kk--;}sprintf(&topo_file[TopoNum], "%ld", ExpensePointID[i] - 1); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;sprintf(&topo_file[TopoNum], "%s", " "); TopoNum++;sprintf(&topo_file[TopoNum], "%ld", i); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;sprintf(&topo_file[TopoNum], "%s", " "); TopoNum++;sprintf(&topo_file[TopoNum], "%ld", PathExpense[i][j]); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;if ((x != NowServerNum - 1) || (i != CurrentGragh.ExpenseNum - 1) || (j != Path_Num[i][0] - 1)){sprintf(&topo_file[TopoNum], "%s", "\n"); TopoNum += 1;}}else if (ExpensePointID[i] - 1 == NowSearchedPath[x]){sprintf(&topo_file[TopoNum], "%ld", ExpensePointID[i] - 1); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;sprintf(&topo_file[TopoNum], "%s", " "); TopoNum++;sprintf(&topo_file[TopoNum], "%ld", i); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;sprintf(&topo_file[TopoNum], "%s", " "); TopoNum++;sprintf(&topo_file[TopoNum], "%ld", PathExpense[i][j]); while ((topo_file[TopoNum] >= 0x30) && (topo_file[TopoNum] <= 0x39)) TopoNum++;if ((x != NowServerNum - 1) || (i != CurrentGragh.ExpenseNum - 1) || (j != Path_Num[i][0] - 1)){sprintf(&topo_file[TopoNum], "%s", "\n"); TopoNum += 1;}}IsContinue = false;}}}if (topo_file[TopoNum - 1] == 0x0a) topo_file[TopoNum - 1] = 0;//*************************************************写入文件系统end****************************************************//// 直接调用输出文件的方法输出到指定文件中(ps请注意格式的正确性，如果有解，第一行只有一个数据；第二行为空；第三行开始才是具体的数据，数据之间用一个空格分隔开)write_result(topo_file, filename);
}/*********************************************
函数名：GetNum(char * graph[MAX_EDGE_NUM],unsigned short X_Line,bool Isclear)
函数功能：得到数据
函数变量：graph[MAX_EDGE_NUM]，unsigned short X_Line，bool Isclear
函数返回值：unsined int
**********************************************/
unsigned short GetNum(char * graph[MAX_EDGE_NUM], unsigned short X_Line)
{unsigned short RetureValue = 0;static unsigned char Y_Line = 0;static unsigned short X_Line_Last = 0;if (X_Line_Last != X_Line) Y_Line = 0;while ((*(graph[X_Line] + Y_Line) < 0x30) || (*(graph[X_Line] + Y_Line)>0x39)) Y_Line++;while ((*(graph[X_Line] + Y_Line) >= 0x30) && (*(graph[X_Line] + Y_Line) <= 0x39)){RetureValue = RetureValue * 10 + *(graph[X_Line] + Y_Line) - 0x30;Y_Line++;}X_Line_Last = X_Line;return RetureValue;
}/*********************************************
函数名：GetGraph(char * graph[MAX_EDGE_NUM])
函数功能：导入文件，生成图数组
函数变量：graph[MAX_EDGE_NUM]
函数返回值：null
**********************************************/void GetGraph(char * graph_input[MAX_EDGE_NUM], int edge_num_input)
{int i = 0, j = 0;unsigned short Net_X, Net_Y;static bool IsFirstInput = false;if (IsFirstInput == true) return;while ((graph_input[i][0] < 0x30) || (graph_input[i][0]>0x39)) i++; //获取第一行点数、链路数、消费节点数CurrentGragh.NetNodeNum = GetNum(graph_input, i);CurrentGragh.NetLinkNum = GetNum(graph_input, i);CurrentGragh.ExpenseNum = GetNum(graph_input, i); i++;while ((graph_input[i][0] < 0x30) || (graph_input[i][0]>0x39)) i++; //获取第三行，服务器价格CurrentGragh.ServerCost = GetNum(graph_input, i); i++;while ((graph_input[i][0] < 0x30) || (graph_input[i][0]>0x39)) i++;while ((graph_input[i][0] >= 0x30) && (graph_input[i][0] <= 0x39)) //获取普通网络节点的链接关系，生成链接矩阵{Net_X = GetNum(graph_input, i);Net_Y = GetNum(graph_input, i);//CurrentGragh.Net_Graph[Net_X][Net_Y].NetMode = Normal_Net;//CurrentGragh.Net_Graph[Net_Y][Net_X].NetMode = Normal_Net;CurrentGragh.Net_Graph[Net_X][Net_Y].BandWidth_Max =CurrentGragh.Net_Graph[Net_Y][Net_X].BandWidth_Max = GetNum(graph_input, i);CurrentGragh.Net_Graph[Net_X][Net_Y].SingleCost =CurrentGragh.Net_Graph[Net_Y][Net_X].SingleCost = GetNum(graph_input, i);BandWidth[BandWidthNum][0] = Net_X;BandWidth[BandWidthNum][1] = Net_Y;BandWidth[BandWidthNum][2] = CurrentGragh.Net_Graph[Net_X][Net_Y].BandWidth_Max;BandWidth[BandWidthNum++][3] = CurrentGragh.Net_Graph[Net_X][Net_Y].SingleCost;if (IsFirstInput == false){ConnectRelation[Net_X][ConnectNum[Net_X]++] = Net_Y;ConnectRelation[Net_Y][ConnectNum[Net_Y]++] = Net_X;}i++;}while ((graph_input[i][0] < 0x30) || (graph_input[i][0]>0x39)) i++;short ExpenseLine = 0;while ((ExpenseLine<CurrentGragh.ExpenseNum)&&(graph_input[i][0] >= 0x30) && (graph_input[i][0] <= 0x39)) //获得消费节点链接关系，生成消费矩阵{Net_X = GetNum(graph_input, i);Net_Y = GetNum(graph_input, i);CurrentGragh.Net_Graph[Net_X + CurrentGragh.NetNodeNum][Net_Y].ConnectID = Net_Y;CurrentGragh.Net_Graph[Net_Y][Net_X + CurrentGragh.NetNodeNum].ConnectID = Net_Y;//CurrentGragh.Net_Graph[Net_X + CurrentGragh.NetNodeNum][Net_Y].NetMode = Expense_Net;//CurrentGragh.Net_Graph[Net_Y][Net_X + CurrentGragh.NetNodeNum].NetMode = Expense_Net;CurrentGragh.Net_Graph[Net_Y][Net_X + CurrentGragh.NetNodeNum].BandWidth_Need =CurrentGragh.Net_Graph[Net_X + CurrentGragh.NetNodeNum][Net_Y].BandWidth_Need = GetNum(graph_input, i);ExpensePointID[Net_X] = Net_Y + 1;ExpenseBandNeed[Net_X] = CurrentGragh.Net_Graph[Net_X + CurrentGragh.NetNodeNum][Net_Y].BandWidth_Need;i++; ExpenseLine++;}IsFirstInput = true;
}/*********************************************
函数名：unsigned short Dijkstra_Graph(struct ParaNetStruct GraphNet[Max_NetNodeNum][Max_NetNodeNum])
函数功能：导入图像矩阵，计算初始点和结束点最短距离
函数变量：Start_Point：初始点 End_Point：结束点
函数返回值：节点距离
**********************************************/
//unsigned short Dijkstra_Graph(unsigned short Start_Point, unsigned short End_Point)
//{
// unsigned short Connect_Min = MaxERROR; //定义与某一点相连的路径最小值
// unsigned short Current_Aspect = 0; //当前层，或者与当前寻找的次数
// unsigned short SearchedPoint[1000] = { 0 }; //定义已经找到的点，找到的话置为累计长度
// unsigned short Current_Point = 0; //当前点
// unsigned short SameLegthNum = 0; //当前层找到的最小路径数量
// unsigned short SameLegthPoint[1000] = { 0 }; //当前层找到的最短路径数组
// unsigned short i = 0;
// unsigned short Sum_Legtgh = 0; //累计长度
// int LastNum = 1; //一共找到的点数
// unsigned short LastPoint[1000] = { 0 }; //一共找到的点数组
// LastPoint[0] = Start_Point; //第一次赋值
// unsigned short ConnectedNum_Pre[1000][2] = { 0 };//高位表示第几个点，低位0表示被搜的编号，1表示搜到最小值的编号
//
// for (Current_Aspect = 0; Current_Aspect < CurrentGragh.NetNodeNum; Current_Aspect++) //表示是第几次寻找
// {
// for (int n = 0; n < LastNum; n++)
// {
// Current_Point = LastPoint[n];
// if ((SearchedPoint[Current_Point] != 0) || (Current_Point == Start_Point)) //此点已经存在，即已经被搜寻过
// {
// for (int k = 0; k < ConnectNum[Current_Point]; k++)
// {
// i = ConnectRelation[Current_Point][k];
// if ((i != Start_Point) && (Connect_Min >= SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[Current_Point][i].SingleCost) && (CurrentGragh.Net_Graph[Current_Point][i].BandWidth_Max != 0) && (SearchedPoint[i] == 0)) //找到这一层的最小值
// {
// if (Connect_Min>SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[Current_Point][i].SingleCost) //最小值更新
// {
// SameLegthNum = 0;
// }
// Connect_Min = SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[Current_Point][i].SingleCost; //当前最小值
// ConnectedNum_Pre[SameLegthNum][0] = Current_Point; //记录被搜的编号
// ConnectedNum_Pre[SameLegthNum][1] = i; //记录搜到最小值的编号
// SameLegthPoint[SameLegthNum++] = i; //记录最小值个数以及坐标
// }
// }
// }
// }
//
// if (SameLegthNum == 0) break; //没有找到点，退出搜索
// for (i = 0; i < SameLegthNum; i++)
// {
// SearchedPoint[SameLegthPoint[i]] = Connect_Min; //放入最短长度
// ConnectedLength_Min[Start_Point][SameLegthPoint[i]] = Connect_Min;//最小距离放入链接数组
// ConnectedMin_ID[Start_Point][ConnectedNum_Pre[i][1]] = ConnectedNum_Pre[i][0];
//
// if (IsInited == false)
// {
// ConnectedLength_Min_Temp[Start_Point][SameLegthPoint[i]] = Connect_Min;
// ConnectedLength_Min_Temp[SameLegthPoint[i]][Start_Point] = Connect_Min; //最小距离放入链接数组
// ConnectedMin_ID_Temp[Start_Point][ConnectedNum_Pre[i][1]] = ConnectedNum_Pre[i][0];
// }
//
// LastPoint[LastNum++] = SameLegthPoint[i]; //记录已经被找过的点数
// if (SameLegthPoint[i] == End_Point)
// return Connect_Min;
// }
// SameLegthNum = 0; Connect_Min = MaxERROR; //累计清零
// }
//}/*********************************************
函数名：void Dijkstra_Graph_2(unsigned short Start_Point)
函数功能：导入图像矩阵，计算其他所有节点到初始节点最短距离
函数变量：Start_Point：初始点
函数返回值：null
**********************************************/void Dijkstra_Graph_2(unsigned short Start_Point)
{unsigned short Connect_Min = MaxERROR; //定义与某一点相连的路径最小值unsigned short Current_Aspect = 0; //当前层，或者与当前寻找的次数unsigned short Current_Point = 0; //当前点unsigned short SameLegthNum = 0; //当前层找到的最小路径数量unsigned short i = 0;unsigned short Sum_Legtgh = 0; //累计长度int LastNum = 1; //一共找到的点数memset(SearchedPoint, 0, Max_NetNodeNum*sizeof(unsigned short));LastPoint[0] = Start_Point; //第一次赋值for (Current_Aspect = 0; Current_Aspect < CurrentGragh.NetNodeNum; Current_Aspect++) //表示是第几次寻找{for (int n = 0; n < LastNum; n++){Current_Point = LastPoint[n];if ((SearchedPoint[Current_Point] != 0) || (Current_Point == Start_Point)) //此点已经存在，即已经被搜寻过{for (int k = 0; k < ConnectNum[Current_Point]; k++){i = ConnectRelation[Current_Point][k];if ((i != Start_Point) && (Connect_Min >= SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[Current_Point][i].SingleCost) && (CurrentGragh.Net_Graph[Current_Point][i].BandWidth_Max != 0) && (SearchedPoint[i] == 0)) //找到这一层的最小值{if (Connect_Min>SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[Current_Point][i].SingleCost) //最小值更新{SameLegthNum = 0;}Connect_Min = SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[Current_Point][i].SingleCost; //当前最小值ConnectedNum_Pre[SameLegthNum][0] = Current_Point; //记录被搜的编号ConnectedNum_Pre[SameLegthNum][1] = i; //记录搜到最小值的编号SameLegthPoint[SameLegthNum++] = i; //记录最小值个数以及坐标}}}}if (SameLegthNum == 0) break; //没有找到点，退出搜索for (i = 0; i < SameLegthNum; i++){SearchedPoint[SameLegthPoint[i]] = Connect_Min; //放入最短长度ConnectedLength_Min[Start_Point][SameLegthPoint[i]] = Connect_Min;ConnectedMin_ID[Start_Point][ConnectedNum_Pre[i][1]] = ConnectedNum_Pre[i][0];if (IsInited == false){ConnectedLength_Min_Temp[Start_Point][SameLegthPoint[i]] = Connect_Min;ConnectedLength_Min_Temp[SameLegthPoint[i]][Start_Point] = Connect_Min; //最小距离放入链接数组ConnectedMin_ID_Temp[Start_Point][ConnectedNum_Pre[i][1]] = ConnectedNum_Pre[i][0];}LastPoint[LastNum++] = SameLegthPoint[i]; //记录已经被找过的点数}SameLegthNum = 0; Connect_Min = MaxERROR; //累计清零}
}/*********************************************
函数名：unsigned short MinPoint( unsigned short servernum, unsigned short expensepoint)
函数功能：选出与该消费节点相连的最短的服务器
函数变量：servernum是服务器的个数，expensepoint是消费节点的ID
函数返回值：服务器标号
**********************************************/
unsigned short MinPoint(unsigned short servernum, unsigned short expensepoint)//servernum是服务器的个数，expensepoint是消费节点的ID，选出与该消费节点相连的最短的服务器
{unsigned short i = 0;unsigned short MinServerPoint = 0;unsigned short MiniPath = MaxERROR;for (i = 0; i < servernum; i++){if (ConnectedLength_Min[expensepoint][NowSearchedPath[i]] < MiniPath){MiniPath = ConnectedLength_Min[expensepoint][NowSearchedPath[i]];MinServerPoint = NowSearchedPath[i];}}return MinServerPoint;
}/*********************************************
函数名：void LenthSum()
函数功能：计算所有消费节点到任意节点最短距离总和
函数变量：null
函数返回值：null
**********************************************/
void LenthSum()
{
#ifdef UsingDistanceif (IsUsingRoom == false){static unsigned short Sum = 0;for (int i = 0; i < CurrentGragh.NetNodeNum; i++){Dijkstra_Graph_2(i);//找第i个节点所有连接距离for (int j = 0; j < CurrentGragh.ExpenseNum; j++){Sum += ConnectedLength_Min[i][ExpensePointID[j] - 1];}//PRINT("到%d结点距离:%d\n", i, Sum);SumLength[i][0] = Sum;SumLength[i][1] = i;for (int k = 0; k < SinglePointNum; k++){if (i == ExpensePointID[SinglePoint[k]] - 1){SumLength[i][0] = 0;SumLength[i][1] = i;break;}}Sum = 0;}MaoPao(SumLength, CurrentGragh.NetNodeNum);for (int i = 0; i < CurrentGragh.NetNodeNum; i++){PreSearchedPath[PreServerNum++] = SumLength[i][1];//保存第一次计算的路径排序NowSearchedPath[NowServerNum++] = SumLength[i][1];//PRINT("到%d结点距离:%d\n", SumLength[i][1], SumLength[i][0]);}IsInited = true;}
#endif // UsingDistance
#ifdef UsingRoomif (IsUsingRoom == true){unsigned short Sum = 0;unsigned short LineNum = 0;for (int i = 0; i < CurrentGragh.NetNodeNum; i++){Dijkstra_Graph_2(i);//找第i个节点所有连接距离for (int j = 0; j < CurrentGragh.NetNodeNum; j++){Sum += CurrentGragh.Net_Graph[i][j].BandWidth_Max;if (CurrentGragh.Net_Graph[i][j].BandWidth_Max != 0) LineNum++;}SumLength[i][0] = Sum*LineNum;SumLength[i][1] = i;Sum = 0;LineNum = 0;for (int k = 0; k < SinglePointNum; k++){if (i == ExpensePointID[SinglePoint[k]] - 1){SumLength[i][0] = MaxERROR; //最大SumLength[i][1] = i;break;}}}MaoPao(SumLength, CurrentGragh.NetNodeNum);for (int i = 0; i < CurrentGragh.NetNodeNum; i++){PreSearchedPath[PreServerNum++] = SumLength[i][1];//保存第一次计算的路径排序NowSearchedPath[NowServerNum++] = SumLength[i][1];//PRINT("到%d结点距离:%d\n", SumLength[i][1], SumLength[i][0]);}IsInited = true;}
#endif // UsingRoom
}/*********************************************
函数名：void MaoPao(unsigned short Point[Max_NetNodeNum][2], unsigned short PointNum)
函数功能：冒泡法排序
函数变量：Point[Max_NetNodeNum][2]：服务器数组，PointNum:普通节点点数
函数返回值：null
**********************************************/
void MaoPao(unsigned short Point[Max_NetNodeNum][2], unsigned short PointNum)
{int i = 0, j = 0;unsigned short Temp = 0;//存放最小值unsigned short idTemp = 0;for (i = 0; i < PointNum; i++){for (j = i + 1; j < PointNum; j++){
#ifdef UsingDistanceif ((Point[i][0]>Point[j][0]) && (IsUsingRoom == false)){Temp = Point[i][0];Point[i][0] = Point[j][0];Point[j][0] = Temp;idTemp = Point[i][1];Point[i][1] = Point[j][1];Point[j][1] = idTemp;}
#endif // UsingDistance#ifdef UsingRoomif ((Point[i][0]<Point[j][0]) && (IsUsingRoom == true)){Temp = Point[i][0];Point[i][0] = Point[j][0];Point[j][0] = Temp;idTemp = Point[i][1];Point[i][1] = Point[j][1];Point[j][1] = idTemp;}
#endif // UsingDistance}}
}/*********************************************
函数名：unsigned short GetMinFlow(unsigned short StartPoint, unsigned short EndPoint)
函数功能：计算最短距离里面的最小流量
函数变量：Start_Point：初始点服务器，EndPoint终止点消费节点 0-N
函数返回值：最短距离带宽
**********************************************/
unsigned short GetMinFlow(unsigned short StartPoint, unsigned short expenseID)
{unsigned short MinFlow = MaxERROR; //表示最小流量unsigned short PreID = ExpensePointID[expenseID] - 1; //链接的前一个点 unsigned short NowID = ExpensePointID[expenseID] - 1; //当前点Path_Num[expenseID][1] = 0;//路径清零while (NowID != StartPoint) //搜寻到初始点为止{PreID = ConnectedMin_ID[StartPoint][NowID];if (MinFlow > CurrentGragh.Net_Graph[PreID][NowID].BandWidth_Max)//当前最小带宽MinFlow = CurrentGragh.Net_Graph[PreID][NowID].BandWidth_Max;Path[expenseID][Path_Num[expenseID][0]][Path_Num[expenseID][1]++] = PreID; //记录路径NowID = PreID; //循环赋值}Path[expenseID][Path_Num[expenseID][0]][Path_Num[expenseID][1]++] = -1;//路径结束标志return MinFlow;
}/*********************************************
函数名：unsigned short UpdateGraph(unsigned short MinFlow, unsigned short serverID, unsigned short expenseID)
函数功能：更新图表并计算
函数变量：MinFlow：路径上最小带宽，serverID： 服务器地址 expenseID：消费节点编号 0-N
函数返回值：最短距离带宽
**********************************************/
unsigned short UpdateGraph(unsigned short MinFlow, unsigned short serverID, unsigned short expenseID)
{unsigned short needBandWidth = 0;unsigned short sendBandWidth = 0;unsigned short PreID = ExpensePointID[expenseID] - 1; //链接的前一个点 unsigned short NowID = ExpensePointID[expenseID] - 1; //当前点bool IsNeedRefresh = false;needBandWidth = CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + expenseID][ExpensePointID[expenseID] - 1].BandWidth_Need - CurrentGragh.Net_Graph[expenseID][ExpensePointID[expenseID] - 1].SatisfiedBandWidth;if (needBandWidth > MinFlow)//比较最大传输带宽和需要带宽大小sendBandWidth = MinFlow;elsesendBandWidth = needBandWidth;PathExpense[expenseID][Path_Num[expenseID][0]] = sendBandWidth;//记录该路径上的带宽if (sendBandWidth!=0) Path_Num[expenseID][0]++;//路径条数++else return sendBandWidth;while (NowID != serverID) //搜寻到初始点为止{PreID = ConnectedMin_ID[serverID][NowID];CurrentGragh.Net_Graph[PreID][NowID].BandWidth_Max = CurrentGragh.Net_Graph[PreID][NowID].BandWidth_Max - sendBandWidth;//更新网络节点剩余带宽if (CurrentGragh.Net_Graph[PreID][NowID].BandWidth_Max == 0){IsNeedRefresh = true;}NowID = PreID; //循环赋值}if (IsNeedRefresh == true) UpdateServerAll(NowServerNum);// 更新服务器CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + expenseID][ExpensePointID[expenseID] - 1].BandWidth_Need -= sendBandWidth;//更新消费节点需要带宽return sendBandWidth;
}/*********************************************
函数名：void UpdateServerAll(unsigned short ServerNum)
函数功能：更新所有服务器与网络链接关系
函数变量：ServerNum：服务器个数
函数返回值：最短距离带宽
**********************************************/void UpdateServerAll(unsigned short ServerNum)
{for (int i = 0; i < CurrentGragh.ExpenseNum; i++)UpdateSinggleServer(NowServerNum, i);
}void UpdateSinggleServer(unsigned short ServerNum, unsigned short SingleExpensePoint)
{unsigned short Connect_Min = MaxERROR; //定义与某一点相连的路径最小值unsigned short Current_Aspect = 0; //当前层，或者与当前寻找的次数unsigned short Current_Point = 0; //当前点unsigned short SameLegthNum = 0; //当前层找到的最小路径数量unsigned short i = 0;unsigned short Sum_Legtgh = 0; //累计长度unsigned short LastNum = 1; //一共找到的点数unsigned short Start_Point = ExpensePointID[SingleExpensePoint] - 1;unsigned short PreID = 0, NowID = 0;unsigned short PaiXuNum = 0;memset(SearchedPoint, 0, Max_NetNodeNum*sizeof(unsigned short));LastPoint[0] = Start_Point; //第一次赋值for (int n = 0; n < NowServerNum; n++) //服务器和消费节点直接相连{if (Start_Point == NowSearchedPath[n]){ExpenceClosedServer[SingleExpensePoint][0] = 0; //记录离消费节点最近的服务器距离ExpenceClosedServer[SingleExpensePoint][1] = NowSearchedPath[n]; //记录离消费节点最近的服务器编号return;}}for (Current_Aspect = 0; Current_Aspect < CurrentGragh.NetNodeNum; Current_Aspect++) //表示是第几次寻找{for (int n = 0; n < LastNum; n++){Current_Point = LastPoint[n];if ((SearchedPoint[Current_Point] != 0) || (Current_Point == Start_Point)) //此点已经存在，即已经被搜寻过{for (int k = 0; k < ConnectNum[Current_Point]; k++){i = ConnectRelation[Current_Point][k];if ((i != Start_Point) && (Connect_Min >= SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[i][Current_Point].SingleCost) && (CurrentGragh.Net_Graph[i][Current_Point].BandWidth_Max != 0) && (SearchedPoint[i] == 0)) //找到这一层的最小值{if (Connect_Min>SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[i][Current_Point].SingleCost) //最小值更新{SameLegthNum = 0;}Connect_Min = SearchedPoint[Current_Point] + CurrentGragh.Net_Graph[i][Current_Point].SingleCost; //当前最小值ConnectedNum_Pre[SameLegthNum][0] = Current_Point; //记录被搜的编号ConnectedNum_Pre[SameLegthNum][1] = i; //记录搜到最小值的编号SameLegthPoint[SameLegthNum++] = i; //记录最小值个数以及坐标}}}}if (SameLegthNum == 0) break; //没有找到点，退出搜索else //寻找有没有相同的终点，有的话，走路径最短的那一条{unsigned short RepeatNum = 0; //重复的个数memset(RepeatBuf, 0, Max_NetNodeNum*sizeof(unsigned short));unsigned short MaxFlow = 0, MaxFlowPoint = 0;for (int i = 0; (i < SameLegthNum); i++) //第几个点{MaxFlow = CurrentGragh.Net_Graph[SameLegthPoint[i]][ConnectedNum_Pre[i][0]].BandWidth_Max;MaxFlowPoint = ConnectedNum_Pre[i][0];RepeatNum = 1; RepeatBuf[0] = i;for (int j = i + 1; (j < SameLegthNum) && (j != i); j++){if (SameLegthPoint[i] == SameLegthPoint[j]) //两个点是同一个点{if (CurrentGragh.Net_Graph[SameLegthPoint[j]][ConnectedNum_Pre[j][0]].BandWidth_Max > MaxFlow){MaxFlow = CurrentGragh.Net_Graph[SearchedPoint[j]][ConnectedNum_Pre[j][0]].BandWidth_Max;MaxFlowPoint = ConnectedNum_Pre[j][0];}RepeatBuf[RepeatNum++] = j;//第几个点 }}for (int k = 0; k < RepeatNum; k++){ConnectedNum_Pre[RepeatBuf[k]][0] = MaxFlowPoint;ConnectedNum_Pre[RepeatBuf[k]][1] = SameLegthPoint[i];}}}for (i = 0; i < SameLegthNum; i++){SearchedPoint[SameLegthPoint[i]] = Connect_Min; //放入最短长度ConnectedLength_Min[SameLegthPoint[i]][Start_Point] = Connect_Min; //最小距离放入链接数组ConnectedMin_ID_Test[Start_Point][ConnectedNum_Pre[i][1]] = ConnectedNum_Pre[i][0];LastPoint[LastNum++] = SameLegthPoint[i]; //记录已经被找过的点数for (int n = 0; n < NowServerNum; n++){if (SameLegthPoint[i] == NowSearchedPath[n]) //找到最近的服务器{PreID = Start_Point; NowID = NowSearchedPath[n];ExpenceClosedServer[SingleExpensePoint][0] = Connect_Min; //记录离消费节点最近的服务器距离ExpenceClosedServer[SingleExpensePoint][1] = NowSearchedPath[n]; //记录离消费节点最近的服务器编号while (NowID != Start_Point){NowID = ConnectedMin_ID_Test[Start_Point][NowID];PaiXu[PaiXuNum++] = NowID;}NowID = Start_Point;while (PaiXuNum > 1){ConnectedMin_ID[NowSearchedPath[n]][NowID] = PaiXu[PaiXuNum - 2];NowID = PaiXu[PaiXuNum - 2];PaiXuNum--;}ConnectedMin_ID[NowSearchedPath[n]][NowID] = NowSearchedPath[n];return;}}}SameLegthNum = 0; Connect_Min = MaxERROR; PaiXuNum = 0; //累计清零}
}/*********************************************
函数名：void SatifyPoint(unsigned short expenseID, unsigned short servernumed)
函数功能：满足特定消费节点需要
函数变量：servernumed：服务器个数 expenseID：消费节点标号 0-N
函数返回值：null
**********************************************/
void SatifyPoint(unsigned short expenseID, unsigned short servernumed)
{unsigned short serverID = 0;unsigned short MiniFlow = 0;static unsigned short temp = 0;while (CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + expenseID][ExpensePointID[expenseID] - 1].BandWidth_Need != 0)//判断当前节点是否被满足{if (temp == CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + expenseID][ExpensePointID[expenseID] - 1].BandWidth_Need){UnsatifiedPoint[UnsatifiedNum++] = expenseID;break;}temp = CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + expenseID][ExpensePointID[expenseID] - 1].BandWidth_Need;serverID = MinPoint(servernumed, ExpensePointID[expenseID] - 1); //获得最短路径的服务器编号MiniFlow = GetMinFlow(serverID, expenseID); //获得改路径上的最小带宽UpdateGraph(MiniFlow, serverID, expenseID); //满足更新NetPathALL++; //路径累计}
}/*********************************************
函数名：unsigned short GetCharge(void)
函数功能：获得所有费用
函数变量：void
函数返回值：null
**********************************************/
unsigned long GetCharge(char * TextFile, bool IsPrint)
{unsigned long ChargeALL_Temp = 0;unsigned short PreID = 0;unsigned short NowID = 0;ChargeALL_Temp += NowServerNum*CurrentGragh.ServerCost;//获得服务器费用if (IsPrint == true) PRINT("总条数：%d\n", NetPathALL);for (int i = 0; i < CurrentGragh.ExpenseNum; i++) //消费节点{for (int j = 0; j < Path_Num[i][0]; j++) //消费节点边数{PreID = ExpensePointID[i] - 1;//消费节点IDif (IsPrint == true) PRINT("%d ", i);if (IsPrint == true) PRINT("%d ", PreID);for (int k = 0; Path[i][j][k] != -1; k++){NowID = Path[i][j][k];ChargeALL_Temp += CurrentGragh.Net_Graph[NowID][PreID].SingleCost*PathExpense[i][j];PreID = NowID;if (IsPrint == true) PRINT("%d ", Path[i][j][k]);}if (IsPrint == true) PRINT("流量：%d\n", PathExpense[i][j]);}}if (IsPrint == true) PRINT("总费用：%d\n", ChargeALL_Temp);return ChargeALL_Temp;
}/*********************************************
函数名：void UpdateMaxie(void)
函数功能：更新矩阵
函数变量：void
函数返回值：null
**********************************************/
void UpdateMaxie(void)
{int i = 0, j = 0;for (i = 0; i < CurrentGragh.ExpenseNum + CurrentGragh.NetNodeNum; i++){if (i < CurrentGragh.ExpenseNum) { Path_Num[i][0] = 0; Path_Num[i][1] = 0; }//路径数和路径上点数清零for (j = 0; j < CurrentGragh.ExpenseNum + CurrentGragh.NetNodeNum; j++){ConnectedLength_Min[i][j] = ConnectedLength_Min_Temp[i][j];ConnectedMin_ID[i][j] = ConnectedMin_ID_Temp[i][j];}}for (i = 0; i < BandWidthNum; i++){CurrentGragh.Net_Graph[BandWidth[i][0]][BandWidth[i][1]].BandWidth_Max = BandWidth[i][2];CurrentGragh.Net_Graph[BandWidth[i][1]][BandWidth[i][0]].BandWidth_Max = BandWidth[i][2];CurrentGragh.Net_Graph[BandWidth[i][0]][BandWidth[i][1]].SingleCost = BandWidth[i][3];CurrentGragh.Net_Graph[BandWidth[i][1]][BandWidth[i][0]].SingleCost = BandWidth[i][3];}for (i = 0; i < CurrentGragh.ExpenseNum; i++){CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + i][ExpensePointID[i] - 1].BandWidth_Need = ExpenseBandNeed[i];CurrentGragh.Net_Graph[ExpensePointID[i] - 1][CurrentGragh.NetNodeNum + i].BandWidth_Need = ExpenseBandNeed[i];}
}/*********************************************
函数名：void GetMaxFlow(void)
函数功能：获得最大流量和最小费用
函数变量：void
函数返回值：null
**********************************************/unsigned short SameLengthBuf[Max_NetNodeNum] = { 0 };
bool GetMaxFlow(void)
{unsigned long MaxFlowALL = 0;unsigned short MinPath = MaxERROR;unsigned short MinPathTemp = MaxERROR;unsigned short ServerID = 0, ExpenseID = 0;unsigned long CurrentFlow = 0;unsigned long SumFlow = 0;unsigned long PreSumFlow = 0;unsigned long MaxFlow = 0;unsigned long MaxFlowTemp = 0;unsigned short SameLengthNum = 0;//相同长度累计NetPathALL = 0;//所有路径清零for (int i = 0; i < CurrentGragh.ExpenseNum; i++) MaxFlowALL += CurrentGragh.Net_Graph[i + CurrentGragh.NetNodeNum][ExpensePointID[i] - 1].BandWidth_Need;while (SumFlow != MaxFlowALL){MinPath = MaxERROR;for (int i = 0; i < CurrentGragh.ExpenseNum; i++) //找到最短路径和编号{MinPathTemp = ConnectedLength_Min[ExpenceClosedServer[i][1]][ExpensePointID[i] - 1]; //消费节点到服务器最短路径if ((MinPathTemp <= MinPath) && (CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + i][ExpensePointID[i] - 1].BandWidth_Need != 0)){if (MinPathTemp < MinPath) SameLengthNum = 0;MinPath = MinPathTemp;//赋值ServerID = ExpenceClosedServer[i][1]; ExpenseID = i; //保存服务器编号和消费节点编号0-NSameLengthBuf[SameLengthNum++] = i;}}MaxFlow = 0; MaxFlowTemp = 0;for (int k = 0; k < SameLengthNum; k++) //在最短路径中选择流量量大或最小{unsigned short i = SameLengthBuf[k];if ((ExpenceClosedServer[i][0] == MinPath) && (CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + i][ExpensePointID[i] - 1].BandWidth_Need != 0)) //是最短路径时{MaxFlowTemp = GetMinFlow(ExpenceClosedServer[i][1], i); //获取最近的服务器流量if (MaxFlowTemp != MaxERROR){if (MaxFlowTemp>CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + i][ExpensePointID[i] - 1].BandWidth_Need)MaxFlowTemp = CurrentGragh.Net_Graph[CurrentGragh.NetNodeNum + i][ExpensePointID[i] - 1].BandWidth_Need;}if ((MaxFlowTemp > MaxFlow) && (MaxFlowTemp != MaxERROR) && (MaxFlowTemp != 0)){MaxFlow = MaxFlowTemp;ServerID = ExpenceClosedServer[i][1]; ExpenseID = i;//保存服务器编号和消费节点编号0-N}}}//PRINT("路径服务器%d,消费节点%d\n", ServerID, ExpenseID);if (MinPath != MaxERROR){CurrentFlow = GetMinFlow(ServerID, ExpenseID); //获得改路径上的最小带宽CurrentFlow = UpdateGraph(CurrentFlow, ServerID, ExpenseID); //满足更新if (CurrentFlow != 0) NetPathALL++; //路径累计//CurrentFlow=UpdateGraph(CurrentFlow, ServerID, ExpenseID);SumFlow += CurrentFlow;//当前累计流量if (SumFlow == PreSumFlow) { return false; }PreSumFlow = SumFlow;}}return true;
}/*********************************************
函数名：void GetSinglePoint(void)
函数功能：获得系统中的孤立节点
函数变量：void
函数返回值：null
**********************************************/
unsigned short CurrentBuf[Max_NetNodeNum][2] = { 0 };
void GetSinglePoint(void)
{memset(CurrentBuf, 0, 2*Max_NetNodeNum*sizeof(unsigned short));for (int i = 0; i < CurrentGragh.ExpenseNum; i++) //当链接的消费节点线路的流量*单位费用>一个服务器单价的时候，直接放一个服务器在该消费节点{unsigned long ChargeExpense = 0; //当前花费unsigned short CurrentFlow = 0; //当前流量unsigned short CurrentNeed = CurrentGragh.Net_Graph[i + CurrentGragh.NetNodeNum][ExpensePointID[i] - 1].BandWidth_Need; //当前需要流量unsigned short CurentTemp = 0;for (int j = 0; j < ConnectNum[ExpensePointID[i] - 1]; j++) //当前所有连接的消费节点{CurrentBuf[j][0] = CurrentGragh.Net_Graph[ExpensePointID[i] - 1][ConnectRelation[ExpensePointID[i] - 1][j]].SingleCost;CurrentBuf[j][1] = ConnectRelation[ExpensePointID[i] - 1][j];}//MaoPao(CurrentBuf, ConnectNum[ExpensePointID[i] - 1],);//路径，单价从小到大排序\//冒泡法startint ii, jj;unsigned short Temp = 0;//存放最小值unsigned short idTemp = 0;for (ii = 0; ii < ConnectNum[ExpensePointID[i] - 1]; ii++){for (jj = ii + 1; jj < ConnectNum[ExpensePointID[i] - 1]; jj++){if ((CurrentBuf[ii][0]>CurrentBuf[jj][0])){Temp = CurrentBuf[ii][0];CurrentBuf[ii][0] = CurrentBuf[jj][0];CurrentBuf[jj][0] = Temp;idTemp = CurrentBuf[ii][1];CurrentBuf[ii][1] = CurrentBuf[jj][1];CurrentBuf[jj][1] = idTemp;}}}//冒泡法Endfor (int j = 0; j < ConnectNum[ExpensePointID[i] - 1]; j++) //排序后得到最短钱数{if (CurrentFlow < CurrentGragh.Net_Graph[i + CurrentGragh.NetNodeNum][ExpensePointID[i] - 1].BandWidth_Need){CurentTemp = (CurrentGragh.Net_Graph[ExpensePointID[i] - 1][CurrentBuf[j][1]].BandWidth_Max> CurrentNeed) ? CurrentNeed : CurrentGragh.Net_Graph[ExpensePointID[i] - 1][CurrentBuf[j][1]].BandWidth_Max;CurrentFlow += CurentTemp;ChargeExpense += CurentTemp*CurrentGragh.Net_Graph[ExpensePointID[i] - 1][CurrentBuf[j][1]].SingleCost;CurrentNeed -= CurentTemp;}}if ((ChargeExpense > CurrentGragh.ServerCost) || (CurrentFlow<CurrentGragh.Net_Graph[i + CurrentGragh.NetNodeNum][ExpensePointID[i] - 1].BandWidth_Need)){SinglePoint[SinglePointNum++] = i;//放入孤立节点，直接把服务器放在这}}
}void DivisionBlock(void)
{unsigned short TempPoint = 0;unsigned short TempNumExpense = 0;unsigned short TempNumNode = 0;unsigned short temp = 0;int k = 0;for (int i = 0; i < CurrentGragh.ExpenseNum; i++) //遍历每个消费节点{TempPoint = ExpensePointID[i] - 1;ConnectedNodePoint[i][TempNumExpense++] = TempPoint; //把与消费节点绑定的普通节点记录下来ConnectedExpensePoint[TempPoint][ConnectedExpensePointNum[TempPoint]++] = i; //把普通节点与哪些消费节点有关系记录下来for (int j = 0; j < 2; j++) //每个消费节点遍历深度为2{for (k = 0; k < CurrentGragh.NetNodeNum; k++){if (CurrentGragh.Net_Graph[TempPoint][k].BandWidth_Max != 0){ConnectedNodePoint[i][TempNumExpense++] = k;ConnectedExpensePoint[k][ConnectedExpensePointNum[k]++] = i;}}TempPoint = k;}ConnectedNodePointNum[i] = TempNumExpense;//ConnectedExpensePointNum[]TempNumExpense = 0;TempNumNode = 0;}/*上面把消费节点遍历了一遍*//*下面的部分为划分成不同的小块*/PreServerNum = 0; NowServerNum = 0;/*得到每个普通节点与其他节点的大概关系*/for (int j = 0; j < CurrentGragh.NetNodeNum; j++){if (ConnectedExpensePointNum[j] != 0){for (int p = 0; p < ConnectedExpensePointNum[j]; p++){temp += ConnectedNodePointNum[ConnectedExpensePoint[j][p]];}}NodeNum[j][0] = temp;NodeNum[j][1] = j;temp = 0;}int i = 0, j = 0;unsigned short Temp = 0;//存放最小值unsigned short idTemp = 0;for (i = 0; i < CurrentGragh.NetNodeNum; i++){for (j = i + 1; j < CurrentGragh.NetNodeNum; j++){if (NodeNum[i][0] < NodeNum[j][0]){Temp = NodeNum[i][0];NodeNum[i][0] = NodeNum[j][0];NodeNum[j][0] = Temp;idTemp = NodeNum[i][1];NodeNum[i][1] = NodeNum[j][1];NodeNum[j][1] = idTemp;}}}
}/*********************************************
函数名：void GetExpenseMin(void)
函数功能：获得系统中的消费节点最短距离
函数变量：void
函数返回值：null
**********************************************/
void GetExpenseMin(void)
{short i = 0, j = 0;short MinLength = MaxERROR;//最小距离short CurrentID = MaxERROR;memset(ExpensePointSum, 0, Max_NetNodeNum * 2 * sizeof(unsigned short));for (i = 0; i < CurrentGragh.ExpenseNum; i++) //当前消费节点{MinLength = MaxERROR; CurrentID = MaxERROR;for (j = 0; (j < CurrentGragh.ExpenseNum); j++) //与这比较的消费节点{if ((i != j) && (MinLength>ConnectedLength_Min[ExpensePointID[i] - 1][ExpensePointID[j] - 1]) && (ConnectedLength_Min[ExpensePointID[i] - 1][ExpensePointID[j] - 1] != 0)){MinLength = ConnectedLength_Min[ExpensePointID[i] - 1][ExpensePointID[j] - 1];CurrentID = j;}}if ((MinLength != 0) && (MinLength != MaxERROR)){unsigned short PreID = ExpensePointID[i] - 1; //链接的前一个点 unsigned short NowID = ExpensePointID[CurrentID] - 1; //当前点ExpensePointSum[NowID][0]++;ExpensePointSum[NowID][1] = NowID;while (NowID != ExpensePointID[i] - 1) //搜寻到初始点为止{PreID = ConnectedMin_ID[ExpensePointID[i] - 1][NowID];NowID = PreID; //循环赋值ExpensePointSum[NowID][0]++;ExpensePointSum[NowID][1] = NowID;}}}//冒泡排序unsigned short Temp = 0;//存放最小值unsigned short idTemp = 0;for (i = 0; i < CurrentGragh.NetNodeNum; i++){for (j = i + 1; j < CurrentGragh.NetNodeNum; j++){if ((ExpensePointSum[i][0]<ExpensePointSum[j][0])){Temp = ExpensePointSum[i][0];ExpensePointSum[i][0] = ExpensePointSum[j][0];ExpensePointSum[j][0] = Temp;idTemp = ExpensePointSum[i][1];ExpensePointSum[i][1] = ExpensePointSum[j][1];ExpensePointSum[j][1] = idTemp;}}}
}
