最短路-Floyd

Floyd

Floyd是多源最短路径算法，算法的主要思想是动态规划，通过插入点不断进行更新松弛，即f [i] [j]=min(f[i] [j],f [i] [k]+f [k] [j])，时间复杂度 O(n3)。

模板

void floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j]>f[i][k]+f[k][j]){f[i][j]=f[i][k]+f[k][j];}}}}
}

例题

POJ-3259 Wormholes

POJ-3259

题目描述

题目背景

ajil在学习acm的同时也是一个物理学爱好者，他最近迷上了虫洞的研究。
虫洞非常nb，它是 单向 的，它可以进行时空穿梭旅行，它可以让你到达某个地点的同时回到一段时间之前。
通过他的超前研究，他用现代科学无法理解的方式在南中附大的校园中发现了很多个虫洞。

题目描述

南中附大的校园可分为F块区域，每个区域有N（1≤N≤500）栋教学楼被编号为1…N，之间有M（1≤M≤2500）条双向路径，K（1≤K≤200）个虫洞。
就在昨天，ajil研究虫洞研究的太入迷了，以至于自己的web实训都忘了交，现在他想要通过时间旅行来回到实训提交截止时间之前，
他会为你提供这F个区域完整的图。所有的路径所花时间都不大于10000秒，所有的虫洞都回到不大于10000秒之前。
他想知道每块区域是否可以通过时间旅行来回到实训提交截止时间之前，请你帮帮他。

Input

首先是一个整数F，表示校园被分为了F块区域
接下来会有F块区域的数据。

每组数据第1行：分别是三个空格隔开的整数：N，M和 K

第2行到M+1行：三个空格分开的数字（U，V，W）描述教学楼间的双向道路：从U到V需要耗费W秒。两个教学楼可能由一个以上的路径来连接。

第M+2到M+K+1行：三个空格分开的数字（U，V，W）描述虫洞：从U到V可以使时间倒流W秒。

Output

F行，每行对应一块区域。 每块区域输出单独的一行，” YES”表示能满足要求，”NO”表示不能满足要求。

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

思路分析

判断是否有负权环

详细代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int INF=0x3f3f3f3f;
int t,n,m,k;
int f[502][502];
bool floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j]>f[i][k]+f[k][j]){f[i][j]=f[i][k]+f[k][j];}}if(f[i][i]<0)	return true;}}return false;
}
int main(){scanf("%d",&t);while(t--){memset(f,INF,sizeof(f));scanf("%d%d%d",&n,&m,&k);int u,v,w;for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);if(w<f[u][v])	f[u][v]=w,f[v][u]=w;}for(int i=0;i<k;i++){scanf("%d%d%d",&u,&v,&w);f[u][v]=-w;}if(floyd())		puts("YES");else	puts("NO");}return 0;
}

POJ-3660 Cow Contest

POJ-3660

题目描述

FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1…N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

Input

第1行: 2个用空格隔开的整数：N 和 M 第2…M+1行: 每行为2个用空格隔开的整数A、B，描述了参加某一轮比赛的奶 牛的编号，以及结果（编号为A，即为每行的第一个数的奶牛为 胜者）

Output

第1行: 输出1个整数，表示排名可以确定的奶牛的数目

Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output

2

思路分析

总共有n头奶牛，若一头奶牛与其他n-1头奶牛都比赛过，则它的排名可以确定。即判断一头奶牛的它的出度和入度之和是否等于n-1，若等于，则表示可以确定排名的奶牛数目加1.其中，若1胜过2，2胜过3，那么1胜过3，可以通过Floyd求解出来。

详细代码

#include<cstdio>
#include<iostream>using namespace std;
int n,m;
bool a[102][102];
void Floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][k] && a[k][j] ){a[i][j]=true;}}}} 
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);a[u][v]=true;}Floyd();int ans=0;for(int i=1;i<=n;i++){int cnt=0;for(int j=1;j<=n;j++){if(i==j)	continue;if(a[i][j])	cnt++;if(a[j][i])	cnt++;}if(cnt==n-1)	ans++;}printf("%d\n",ans);return 0;
}
s=0;for(int i=1;i<=n;i++){int cnt=0;for(int j=1;j<=n;j++){if(i==j)	continue;if(a[i][j])	cnt++;if(a[j][i])	cnt++;}if(cnt==n-1)	ans++;}printf("%d\n",ans);return 0;
}