25 Oct 2016 本文阅读量次

【CODEVS 1021】玛丽卡

题目链接：玛丽卡

思路

第一时间想到的就是枚举每一条边使其堵塞，然后跑SPFA，求一个最大值。这样肯定不行(╮(╯▽╰)╭)，再想一下，既然是影响最终的最短路，那就应该在最短路上做手脚: 先跑一遍 SPFA，求出最短路径，然后枚举最短路上的每一条边使其堵塞，再跑SPFA，求最大值。这就减少了大量不必要的计算，降低了复杂度(我第一次写的只有70分- -! 写太丑)。
还有要说的就是: 一定要细心再细心。。。。。。

代码

70分, 写很丑辣眼睛(主要是用DFS求路径和修改边权复杂度较高，其实SPFA就可以记录路径)

/*
* Copyright © Eliot
* Date: 2016-10-26
* Author: Eliot
* QQ: 1161142536
* Description: 70分 玛丽卡
*/

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

#define MAX  1001

int N = 0, M = 0;
int x = 0, y = 0, c = 0;

/***********************
Description: 邻接表
***********************/
struct STRUCT {
	int nPre;
	int nTo;
	int nVal;
}EDGE[100 * MAX];
int head[MAX] = { 0 };
int nCount = 0;

/***********************
Description: 添边
***********************/
void Add(int a, int b, int c) {
	EDGE[++nCount].nTo = b;
	EDGE[nCount].nVal = c;
	EDGE[nCount].nPre = head[a];
	head[a] = nCount;
}

/***********************
Description: SPFA最短路
***********************/
queue<int> Q;
int dis[MAX] = { 0 };
bool IsStack[MAX] = { false };
int SPFA(int nStart) {
	memset(dis, 0x7, sizeof(dis));

	Q.push(nStart);
	IsStack[nStart] = true;
	dis[nStart] = 0;

	while (!Q.empty()) {
		int nPoint = Q.front();
		Q.pop();
		IsStack[nPoint] = false;

		for (int i = head[nPoint]; i != 0; i = EDGE[i].nPre) {
			int nNextPoint = EDGE[i].nTo;

			if (dis[nPoint] + EDGE[i].nVal < dis[nNextPoint]) {
				dis[nNextPoint] = dis[nPoint] + EDGE[i].nVal;
				if (!IsStack[nNextPoint]) {
					IsStack[nNextPoint] = true;
					Q.push(nNextPoint);
				}
			}
		}
	}
}

/***********************
Description: DFS求路径
***********************/
bool Is[MAX] = { false };
int Arr[MAX] = { 0 }, _A[MAX] = { 0 };
void DFS(int nPoint, int nLen, int Count, int nMin) {
	for (int i = head[nPoint]; i != 0; i = EDGE[i].nPre) {
		int nNextPoint = EDGE[i].nTo;
		if (Is[nNextPoint]) continue;

		Arr[Count] = nNextPoint;
		Is[nNextPoint] = true;
		nLen += EDGE[i].nVal;
		if (nLen >= nMin) {
			Arr[Count] = 0;
			Is[nNextPoint] = false;
			nLen -= EDGE[i].nVal;

			continue;
		}

		if (nNextPoint == N && nMin == nLen) {
			for (int i = 1; i <= Count; i++) _A[i] = Arr[i];
			return;
		}
		else {
			DFS(nNextPoint, nLen, Count + 1, nMin);
		}
		Is[nNextPoint] = false;
		nLen -= EDGE[i].nVal;
	}
}

/***********************
Description: 修改边权值
***********************/
int Change(int A, int B) {
	int nRetn = 0;
	for (int i = head[A]; i != 0; i = EDGE[i].nPre) {
		if (EDGE[i].nTo == B) {
			nRetn = EDGE[i].nVal;
			EDGE[i].nVal = 999999;
			return nRetn;
		}
	}
}

/***********************
Description: 恢复边权值
***********************/
void Recover(int A, int B, int nR) {
	for (int i = head[A]; i != 0; i = EDGE[i].nPre) {
		if (EDGE[i].nTo == B) {
			EDGE[i].nVal = nR;
			break;
		}
	}
}

int ans = 0;
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d", &x, &y, &c);
		Add(x, y, c);
		Add(y, x, c);
	}
	SPFA(1);
	int nMin = dis[N];

	Is[1] = true;
	_A[0] = 1;
	DFS(1, 0, 1, nMin);
    
    //枚举最短路中的每条边
	int i = 0;
	while (true) {
		if (i == N) break;
		int A = _A[i], B = _A[i + 1];
		
		int nRetn = Change(A, B);
		SPFA(1);
		ans = max(ans, dis[N]);
		Recover(A, B, nRetn);

		i ++;
	}

	cout << ans << endl;
	return 0;
}

100分，放弃使用DFS求路径，转而使用SPFA记录路径；判断边是否可用集合到SPFA.

SPFA记录最短路径 ：申请一个nPre数组，在进行松弛操作的时候，记录下当前点的前驱，最后倒序输出即最短路径.
For example:

int SPFA(int nStart) {
	memset(dis, 0x7, sizeof(dis));

	Q.push(nStart);
	IsStack[nStart] = true;
	dis[nStart] = 0;

	while (!Q.empty()) {
		int nPoint = Q.front();
		Q.pop();
		IsStack[nPoint] = false;

		for (int i = head[nPoint]; i != 0; i = EDGE[i].nPre) {
			int nNextPoint = EDGE[i].nTo;

			if (dis[nPoint] + EDGE[i].nVal < dis[nNextPoint]) {
				dis[nNextPoint] = dis[nPoint] + EDGE[i].nVal;
				//这里记录下前驱
				nPre[nNextPoint] = nPoint;
				if (!IsStack[nNextPoint]) {
					IsStack[nNextPoint] = true;
					Q.push(nNextPoint);
				}
			}
		}
	}
}

/*
* Copyright © Eliot
* Date: 2016-10-26
* Author: Eliot
* QQ: 1161142536
* Description: 100分 玛丽卡
*/

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

#define MAX  1001

int N = 0, M = 0;
int x = 0, y = 0, c = 0;

/***********************
Description: 邻接表
***********************/
struct STRUCT {
	int nPre;
	int nTo;
	int nVal;
}EDGE[1000 * MAX];
int head[MAX] = { 0 };
int nCount = 0;

/***********************
Description: 添边
***********************/
void Add(int a, int b, int c) {
	EDGE[++nCount].nTo = b;
	EDGE[nCount].nVal = c;
	EDGE[nCount].nPre = head[a];
	head[a] = nCount;
}

/******************************************************
Description: SPFA最短路， 在其中判断 A， B 是否可以相连
******************************************************/
queue<int> Q;
int dis[MAX] = { 0 };
int nPre[MAX] = { 0 };
bool IsStack[MAX] = { false };
int SPFA(int nStart, int A, int B) {
	memset(dis, 0x7, sizeof(dis));

	Q.push(nStart);
	IsStack[nStart] = true;
	dis[nStart] = 0;

	while (!Q.empty()) {
		int nPoint = Q.front();
		Q.pop();
		IsStack[nPoint] = false;
		
		for (int i = head[nPoint]; i != 0; i = EDGE[i].nPre) {
			int nNextPoint = EDGE[i].nTo;
			if ((nPoint == A && nNextPoint == B) || (nPoint == B && nNextPoint == A)) continue ;

			if (dis[nPoint] + EDGE[i].nVal < dis[nNextPoint]) {
				dis[nNextPoint] = dis[nPoint] + EDGE[i].nVal;
				nPre[nNextPoint] = nPoint;
				if (!IsStack[nNextPoint]) {
					IsStack[nNextPoint] = true;
					Q.push(nNextPoint);
				}
			}
		}
	}
}

int ans = 0;
int Arr[MAX] = { 0 }, C = 0;
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d", &x, &y, &c);
		Add(x, y, c);
		Add(y, x, c);
	}
	SPFA(1, -1, -1);
	int nMin = dis[N];
    
    //记录路径
	int P = N;
	while (P != 1) {
		Arr[++C] = nPre[P];
		P = nPre[P];
	}
	C ++;
	Arr[0] = N;
    
    //枚举最短路中的每一条边
	for (int i = 0; i < C - 1; i++) {
		int A = Arr[i], B = Arr[i + 1];
		SPFA(1, A, B);
		ans = max(ans, dis[N]);
	}

	cout << ans << endl;
	return 0;
}

【CODEVS 1021】玛丽卡

思路

代码

Tags:

Status:

Share:

Comments: