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;
}

19.8.3

原文：https://www.cnblogs.com/qnwyqh/p/11296669.html