19.8.3

Floyd，没什么好说的，贴代码

#include<bits/stdc++.h>
using namespace std;
const long long inf=0x3f3f3f3f3f3f3f3f;
long long d[101][101],v,e;
void fl()
{
for(int k=0;k<v;k++)
for(int i=0;i<v;i++)
for(int j=0;j<v;j++)
{
if(d[i][k]==inf||d[k][j]==inf)continue;
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
int main()
{
cin>>v>>e;
for(int i=0;i<v;i++)
for(int j=0;j<v;j++) {
if(i!=j)
d[i][j]=inf;
else
d[i][i] = 0;
}
for(int i=1;i<=e;i++)
{
int s,t,di;
cin>>s>>t>>di;
d[s][t]=di;
}
fl();
for(int i=0;i<v;i++)
{
if(d[i][i]<0){
cout<<"NEGATIVE CYCLE"<<endl;
return 0;
}
}
for(int i=0;i<v;i++){
for(int j=0;j<v;j++)
if(d[i][j]>=inf)cout<<"INF"<<" ";
else cout<<d[i][j]<<" ";
cout<<endl;
}
}

调试很多遍，发现是无穷大值设小了的玄学问题.....

还有一道也是Floyd，数据很水

?

用Floyd实现的传递闭包，一遍过，很简单，思路就是统计一点与其他所有点的关系是否确定而已（话说约翰家的奶牛都是什么神仙）

#include<bits/stdc++.h>using namespace std;int n,m,d[101][101],ans;int main(){ cin>>n>>m; for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; d[a][b]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][k]&&d[k][j]) d[i][j]=1; for(int i=1;i<=n;i++) { int gf=0; for(int j=1;j<=n;j++) if(d[i][j]||d[j][i]) gf++; if(gf==n-1)ans++; } cout<<ans<<endl; return 0;}