图论-多源最短路径（Floyd算法）

Floyd

模板

void floyd() {
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			if (mp[i][k] != inf)  //优化
				for (int j = 1; j <= n; j++)
					if (mp[i][j] > mp[i][k] + mp[k][j])
						mp[i][j] = mp[i][k] + mp[k][j];
}

例题

POJ-3259（负圈）

POJ-3259 Wormholes

Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1…N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes. As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself ) . To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds. Input Line 1: A single integer, F. F farm descriptions follow. Line 1 of each farm: Three space-separated integers respectively: N, M, and W Lines 2…M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path. Lines M+2…M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds. Output Lines 1…F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes). Sample Input 2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8 Sample Output NO YES Hint For farm 1, FJ cannot travel back in time. For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

分析： 给定若干双向正值边和单向负值边，问是否存在负圈（使其时光倒流回到原点）。 所以在第二重循环，求完第i个结点后判断。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 502;
int t, n, m, w, x, y, z;
int mp[maxn][maxn];
bool floyd() {
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			if (mp[i][k] != inf) {
				for (int j = 1; j <= n; j++)
					if (mp[i][j] > mp[i][k] + mp[k][j])
						mp[i][j] = mp[i][k] + mp[k][j];
				if (mp[i][i] < 0)return true;
			}
	return false;
}
int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &m, &w);
		memset(mp, inf, sizeof(mp));
		for (int i = 0; i < m; i++) {
			scanf("%d%d%d", &x, &y, &z);
			if (z < mp[x][y]) //注意坑：重边
				mp[x][y] = mp[y][x] = z;
		}
		for (int i = 0; i < w; i++) {
			scanf("%d%d%d", &x, &y, &z);
			mp[x][y] = -z;
		}
		if (floyd())puts("YES");
		else puts("NO");
	}
	return 0;
}

HDU-1385（打印路径）

HDU-1385 Minimum Transport Cost

Problem Description These are N cities in Spring country. Between each pair of cities there may be one transportation track or none. Now there is some cargo that should be delivered from one city to another. The transportation fee consists of two parts: The cost of the transportation on the path between these cities, and a certain tax which will be charged whenever any cargo passing through one city, except for the source and the destination cities. You must write a program to find the route which has the minimum cost. Input First is N, number of cities. N = 0 indicates the end of input. The data of path cost, city tax, source and destination cities are given in the input, which is of the form: a11 a12 … a1N a21 a22 … a2N … aN1 aN2 … aNN b1 b2 … bN c d e f … g h where aij is the transport cost from city i to city j, aij = -1 indicates there is no direct path between city i and city j. bi represents the tax of passing through city i. And the cargo is to be delivered from city c to city d, city e to city f, …, and g = h = -1. You must output the sequence of cities passed by and the total cost which is of the form: Output From c to d : Path: c–>c1–>…–>ck–>d Total cost : … … From e to f : Path: e–>e1–>…–>ek–>f Total cost : … Note: if there are more minimal paths, output the lexically smallest one. Print a blank line after each test case. Sample Input 5 0 3 22 -1 4 3 0 5 -1 -1 22 5 0 9 20 -1 -1 9 0 4 4 -1 20 4 0 5 17 8 3 1 1 3 3 5 2 4 -1 -1 0 Sample Output From 1 to 3 : Path: 1–>5–>4–>3 Total cost : 21 From 3 to 5 : Path: 3–>4–>5 Total cost : 16 From 2 to 4 : Path: 2–>1–>5–>4 Total cost : 17

分析：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 1003;
int mp[maxn][maxn], path[maxn][maxn];//邻接矩阵、路径
int n, x, y, u, v, cost[maxn];//额外费用
void floyd() {
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			if(mp[i][k]!=inf)
				for (int j = 1; j <= n; j++) {
					if (mp[i][j] > mp[i][k] + mp[k][j] + cost[k]) {
						mp[i][j] = mp[i][k] + mp[k][j] + cost[k];
						path[i][j] = path[i][k];
					}
					if (mp[i][j] == mp[i][k] + mp[k][j] + cost[k]) {
						if (path[i][j] > path[i][k])  //字典序
							path[i][j] = path[i][k];
					}
				}
}
int main() {
	while (~scanf("%d", &n) && n) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				path[i][j] = j;
				scanf("%d", &mp[i][j]);
				if (mp[i][j] == -1)
					mp[i][j] = inf;
			}
		}
		for (int i = 1; i <= n; i++)
			scanf("%d", &cost[i]);
		floyd();
		while (scanf("%d%d", &x, &y)) {
			if (x == -1 && y == -1)break;
			u = x, v = y;
			printf("From %d to %d :\n", x, y);
			printf("Path: %d", x);
			while (x != y) {
				printf("-->%d", path[x][y]);
				x = path[x][y];
			}
			printf("\n");
			if (mp[u][v] < inf)
				printf("Total cost : %d\n", mp[u][v]);
			else printf("-1\n");
			printf("\n");
		}
	}
	return 0;
}

HDU-1599（最小环）

HDU-1599 find the mincost route

Problem Description 杭州有N个景区，景区之间有一些双向的路来连接，现在8600想找一条旅游路线，这个路线从A点出发并且最后回到A点，假设经过的路线为V1,V2,…VK,V1,那么必须满足K>2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。 Input 第一行是2个整数N和M（N <= 100, M <= 1000)，代表景区的个数和道路的条数。 接下来的M行里，每行包括3个整数a,b,c.代表a和b之间有一条通路，并且需要花费c元(c <= 100)。 Output 对于每个测试实例，如果能找到这样一条路线的话，输出花费的最小值。如果找不到的话，输出"It’s impossible.". Sample Input 3 3 1 2 1 2 3 1 1 3 1 3 3 1 2 1 1 2 3 2 3 1 Sample Output 3 It’s impossible

分析：

（插播反爬信息 ）博主CSDN地址：https://wzlodq.blog.csdn.net

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
const int maxn = 102;
ll mp[maxn][maxn], dis[maxn][maxn];
ll n, m, a, b, c, ans;
void floyd() {
	for (int k = 1; k <= n; k++) {
		
		for (int i = 1; i < k; i++)  //枚举ij
			for (int j = i + 1; j < k; j++)  //注意ijk不能相同
				if (ans > mp[i][j] + dis[j][k] + dis[k][i])
					ans = mp[i][j] + dis[j][k] + dis[k][i];
					
		for (int i = 1; i <= n; i++)  //原floyd
			for (int j = 1; j <= n; j++)
				if (mp[i][j] > mp[i][k] + mp[k][j])
					mp[i][j] = mp[i][k] + mp[k][j];

	}
}
int main() {
	while (~scanf("%lld%lld", &n, &m)) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i == j)mp[i][j] = dis[i][j] = 0;
				else mp[i][j] = dis[i][j] = inf;
		while (m--) {
			scanf("%lld%lld%lld", &a, &b, &c);
			if (c < mp[a][b]) //防重边，怕了怕了
				mp[a][b] = dis[a][b] = c;
			if (c < mp[b][a]) 
				mp[b][a] = dis[b][a] = c;
		}
		ans = inf;
		floyd();
		if (ans == inf)puts("It's impossible.");
		else printf("%lld\n", ans);
	}
	return 0;
}

HDU-1704（传递闭包）

HDU-1704 Rank

Problem Description there are N ACMers in HDU team. ZJPCPC Sunny Cup 2007 is coming, and lcy want to select some excellent ACMers to attend the contest. There have been M matches since the last few days(No two ACMers will meet each other at two matches, means between two ACMers there will be at most one match). lcy also asks"Who is the winner between A and B?" But sometimes you can’t answer lcy’s query, for example, there are 3 people, named A, B, C.and 1 match was held between A and B, in the match A is the winner, then if lcy asks “Who is the winner between A and B”, of course you can answer “A”, but if lcy ask “Who is the winner between A and C”, you can’t tell him the answer. As lcy’s assistant, you want to know how many queries at most you can’t tell lcy(ask A B, and ask B A is the same; and lcy won’t ask the same question twice). Input The input contains multiple test cases. The first line has one integer,represent the number of test cases. Each case first contains two integers N and M(N , M <= 500), N is the number of ACMers in HDU team, and M is the number of matchs have been held.The following M lines, each line means a match and it contains two integers A and B, means A wins the match between A and B.And we define that if A wins B, and B wins C, then A wins C. Output For each test case, output a integer which represent the max possible number of queries that you can’t tell lcy. Sample Input 3 3 3 1 2 1 3 2 3 3 2 1 2 2 3 4 2 1 2 3 4 Sample Output 0 0 4 Hint in the case3, if lcy ask (1 3 or 3 1) (1 4 or 4 1) (2 3 or 3 2) (2 4 or 4 2), then you can’t tell him who is the winner.

分析： 求多少组关系没法确定，传递闭包，比如1->2，2->3（mp[1][2]=1、mp[2][3]=1），由传递关系得1->3，即原来的mp[1][3]置1。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 502;
int t, n, m, x, y, ans;
int mp[maxn][maxn];
void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; mp[i][k] && j <= n; j++)
                mp[i][j] |= mp[i][k] & mp[k][j]; //通过k传递,或运算
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        memset(mp, 0, sizeof(mp));
        while (m--) {
            scanf("%d %d", &x, &y);
            mp[x][y] = 1;
        }
        floyd();
        ans = 0;
        for (int i = 1; i <= n; i++)  //统计答案
            for (int j = i + 1; j <= n; j++)
                if (!mp[i][j] && !mp[j][i])
                    ans++;
        printf("%d\n", ans);
    }
    return 0;
}

HDU-3631（变形）

HDU-3631 Shortest Path

Problem Description When YY was a boy and LMY was a girl, they trained for NOI (National Olympiad in Informatics) in GD team. One day, GD team’s coach, Prof. GUO asked them to solve the following shortest-path problem. There is a weighted directed multigraph G. And there are following two operations for the weighted directed multigraph: (1) Mark a vertex in the graph. (2) Find the shortest-path between two vertices only through marked vertices. For it was the first time that LMY faced such a problem, she was very nervous. At this moment, YY decided to help LMY to analyze the shortest-path problem. With the help of YY, LMY solved the problem at once, admiring YY very much. Since then, when LMY meets problems, she always calls YY to analyze the problems for her. Of course, YY is very glad to help LMY. Finally, it is known to us all, YY and LMY become programming lovers. Could you also solve the shortest-path problem? Input The input consists of multiple test cases. For each test case, the first line contains three integers N, M and Q, where N is the number of vertices in the given graph, N≤300; M is the number of arcs, M≤100000; and Q is the number of operations, Q ≤100000. All vertices are number as 0, 1, 2, … , N - 1, respectively. Initially all vertices are unmarked. Each of the next M lines describes an arc by three integers (x, y, c): initial vertex (x), terminal vertex (y), and the weight of the arc ©. (c > 0) Then each of the next Q lines describes an operation, where operation “0 x” represents that vertex x is marked, and operation “1 x y” finds the length of shortest-path between x and y only through marked vertices. There is a blank line between two consecutive test cases. End of input is indicated by a line containing N = M = Q = 0. Output Start each test case with “Case #:” on a single line, where # is the case number starting from 1. For operation “0 x”, if vertex x has been marked, output “ERROR! At point x”. For operation “1 x y”, if vertex x or vertex y isn’t marked, output “ERROR! At path x to y”; if y isn’t reachable from x through marked vertices, output “No such path”; otherwise output the length of the shortest-path. The format is showed as sample output. There is a blank line between two consecutive test cases. Sample Input 5 10 10 1 2 6335 0 4 5725 3 3 6963 4 0 8146 1 2 9962 1 0 1943 2 1 2392 4 2 154 2 2 7422 1 3 9896 0 1 0 3 0 2 0 4 0 4 0 1 1 3 3 1 1 1 0 3 0 4 0 0 0 Sample Output Case 1: ERROR! At point 4 ERROR! At point 1 0 0 ERROR! At point 3 ERROR! At point 4

分析： 在有向图中两种操作：①标记一个点②在标记点上查询最短路径。查询虽然很多但每个点的标记操作只有一次（重复标记输出error），那么我们对标记操作就是把标记点作为中间结点k，去更新其余的最短路径就好了(floyd二三重循环)。 注意下标输入从0开始，还有格式。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 302;
int t = 0, n, m, q, u, v, w;
int mp[maxn][maxn];
bool flag[maxn]; //记录是否标记
void floyd(int k) {
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			if (mp[i][j] > mp[i][k] + mp[k][j])
				mp[i][j] = mp[i][k] + mp[k][j];
}
int main(){
	while (~scanf("%d %d %d", &n, &m, &q)) {
		if (n == 0 && m == 0 && q == 0) break;
		if (t != 0)printf("\n"); //谜之格式
		printf("Case %d:\n", ++t);
		memset(mp, inf, sizeof(mp));
		memset(flag, false, sizeof(flag));
		for (int i = 0; i <= n; ++i)
			mp[i][i] = 0;
		while (m--) {
			scanf("%d %d %d", &u, &v, &w);
			if (w < mp[u][v])
				mp[u][v] = w;
		}
		while (q--) {
			scanf("%d", &w);
			if (w == 0) {
				scanf("%d", &u);
				if (flag[u])printf("ERROR! At point %d\n", u);
				else {
					flag[u] = true;
					floyd(u);
				}
			}
			else {
				scanf("%d %d", &u, &v);
				if (!(flag[u] && flag[v]))
					printf("ERROR! At path %d to %d\n", u, v);
				else if (mp[u][v] == inf)
					printf("No such path\n");
				else printf("%d\n", mp[u][v]);
				
			}
		}
	}
	return 0;
}

ps：这是我有域名(博客六级)后的第一篇博客，加油(。・∀・)ノ