Demo entry 6334029

Project2

   

Submitted by Ken on Dec 05, 2016 at 02:26
Language: C++. Code size: 5.6 kB.

#include<stdio.h>
#include<stdlib.h>
#include<vector>

#define MaxStation 501
#define Max 1<<30//定义最大值
typedef int Vertex;

//因为结点最多可能到500,所以用链表来表示
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
	Vertex AdjV;
	int cost;
	PtrToAdjVNode Next;
};//用来存放和Station[i]相邻的结点的结构


typedef struct Vnode{
	int Dis;
	int bike;
	int isFind;
	int Path;
	std::vector<int> paths;//用来存放所有的最短路径的上一个结点
	PtrToAdjVNode FirstEdge;//和该Station相连的Station
} Station[MaxStation];//存放所有的Station的各种数据


typedef struct GNode *PtrToGNode;//图的结构
struct GNode{
	int Nv;
	int Ne;
	int wrongStation;
	int capacity;
	std::vector<int> finalPath;//存放最终路径
	std::vector<int> Path;
	int send;
	int back;
	Station stationG;
};
typedef PtrToGNode LGraph;

//因为最大结点数较大,故选用队列来记录数据
typedef struct Queue * queue;//队列的结构
struct Queue{
	int VNode;
	queue next;
};

typedef struct Q *q;//存放队列的头尾
struct Q{
	queue header;
	queue tail;
};

void Push(int V, q Q){//Push函数,将数据推入队列中
	queue tmp;
	tmp = (queue)malloc(sizeof(struct Queue));
	tmp->VNode = V;
	tmp->next = NULL;
	Q->tail->next = tmp;
	Q->tail = tmp;
}

int Pop(q Q){//Pop函数,从队列中弹出数据
	int V;
	queue tmp;
	tmp = Q->header->next;
	if (!tmp)
		return -1;
	if (tmp == Q->tail)
		Q->tail = Q->header;

	V = tmp->VNode;
	Q->header->next = tmp->next;
	
	free(tmp);
	return V;
}

//按照ppt上的来的算法,因为这是一个无向图,所以实际上采用的是类似negativeWeight的算法。
void Dijkstra(LGraph Graph);

//初始化图
LGraph Init();

//深度优先,从后往前遍历全部最短路径
void DFS(LGraph Graph, Vertex V, int send, int back);

int main(){
	LGraph Graph = Init();//初始化图
	int WS,V;//方便比较大小的几个辅助变量
	int sendin = 0, sendback = 0;//存放最终输出

	//找到最短路径
	Dijkstra(Graph);
	//借助paths,从WS开始往0查找,比较最佳路径,将最佳路径写入Path
	WS = Graph->wrongStation;
	 DFS(Graph, WS,0,0);


	//输出
	printf("%d ", Graph->send);
	printf("0");
	for (int i = Graph->finalPath.size() - 1; i >= 0; i--){
		printf("->%d", Graph->finalPath[i]);
	}

	printf(" %d", Graph->back);
	

}

LGraph Init(){//读入图的初始化函数
	LGraph Graph;
	int i,v1,v2,cost;
	PtrToAdjVNode tmpAdj, tmpN;
	Graph = new GNode;
	Graph->send  = Max;
	Graph->back = Max;
	//初始化
	Graph->stationG[0].Dis = 0;
	Graph->stationG[0].Path = 0;
	Graph->stationG[0].FirstEdge = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	Graph->stationG[0].FirstEdge->Next = NULL;
	Graph->stationG[0].bike = 5;
	Graph->stationG[0].isFind = 0;	

	//读入容量、结点数、错误结点值、边数
	scanf("%d%d%d%d", &Graph->capacity, &Graph->Nv, &Graph->wrongStation, &Graph->Ne);

	//printf("请输入自行车数\n");
	for (i = 1; i <= Graph->Nv; i++){
		scanf("%d", &Graph->stationG[i].bike);
		Graph->stationG[i].FirstEdge = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
		Graph->stationG[i].FirstEdge->Next = NULL;
		Graph->stationG[i].isFind = 0;
		Graph->stationG[i].Dis = Max;
	}//初始化

	for (i = 0; i < Graph->Ne; i++){
		//printf("请输入边\n");
		scanf("%d%d%d", &v1, &v2, &cost);

		tmpAdj = Graph->stationG[v1].FirstEdge;
		tmpN = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
		tmpN->AdjV = v2;
		tmpN->cost = cost;
		tmpN->Next = tmpAdj->Next;
		tmpAdj->Next = tmpN;

		tmpAdj = Graph->stationG[v2].FirstEdge;
		tmpN = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
		tmpN->AdjV = v1;
		tmpN->cost = cost;
		tmpN->Next = tmpAdj->Next;
		tmpAdj->Next = tmpN;

	}
	return Graph;
}

void Dijkstra(LGraph Graph){
	q Q = (q)malloc(sizeof(struct Q));
	Vertex V, W, WS = Graph->wrongStation;
	int tmpDis;
	PtrToAdjVNode tmpW;
	//初始化存放队列的结构
	Q->header = (queue)malloc(sizeof(struct Queue));
	Q->header->next = NULL;
	Q->header->VNode = -1;
	Q->tail = Q->header;

    Push(0, Q);
	while ((V = Pop(Q)) >= 0){
		tmpW = Graph->stationG[V].FirstEdge->Next;


		while (tmpW){
			tmpDis = Graph->stationG[V].Dis + tmpW->cost;
			W = tmpW->AdjV;
			if ( tmpDis < Graph->stationG[W].Dis){//如果找到更短的路径
				Graph->stationG[W].Dis = tmpDis;
				Graph->stationG[W].Path = V;
				if (Graph->stationG[W].paths.size())
					Graph->stationG[W].paths.clear();//清空vector
				Graph->stationG[W].paths.push_back(V);//将数据存放入vector
				Push(W, Q);
			}
			else if (tmpDis == Graph->stationG[W].Dis){//如果找到同样长度的路径
				Graph->stationG[W].paths.push_back(V);//将新的路径(上一个结点)也存放到vector中
				Push(W, Q);
			}
			tmpW = tmpW->Next;
		}
	}
}

void DFS(LGraph Graph, Vertex V, int send, int back){
	int bestNum = Graph->capacity / 2;

	if (V != 0 )//如果不是起始点,要继续遍历,直到起始点跳出递归
	{
		Graph->stationG[V].isFind = 1;//记录下已经过了这个结点
		Graph->Path.push_back(V);//将该结点添加进vector中
		if (Graph->stationG[V].bike <= bestNum)//如果结点中bike数比均值小,说明还需要送来车辆,增加send数
		{
			send = send + bestNum - Graph->stationG[V].bike;
		}
		else
		{
			back = back + Graph->stationG[V].bike - bestNum;//如果bike数大于均值,因为现在是从后往前遍历,所以可以削减send数
			if (send > 0)//如果之前需要send过来车,可以从过剩结点运过去,send和back值都减少
			{
				if (back>send)//back数比较大,还需要back回起始点一些
				{
					back -= send;
					send = 0;
				}
				else//send数比较大,还需要继续send
				{
					send -= back;
					back = 0;
				}
			}
		}

		for (auto &tmp: Graph->stationG[V].paths)//对所有经过V的路径进行DFS搜索
		{
			DFS(Graph, tmp, send, back);
		}
		Graph->Path.pop_back();//结束一次递归后将tmp路径中原来的自己的值弹出
	}
	else if (V == 0)//如果到了起始点,结束递归
	{
		if (send < Graph->send){//send优先,如果现在的tmp路径比最终路径send值更小,改变最终路径
			Graph->finalPath.clear();
			Graph->finalPath = Graph->Path;
			Graph->send = send;
			Graph->back = back;
		}
		else if (send == Graph->send && back < Graph->back)//如果send值相同,比较back值
		{
			Graph->finalPath.clear();
			Graph->finalPath = Graph->Path;
			Graph->send = send;
			Graph->back = back;
		}
	}
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).