Floyd模板题
谢谢没有稗子提出问题
就是单向的
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;
int d[N][N], n, m;
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
scanf("%d%d",&x,&y);
d[x][y] = 1;
}
//floyd求任意两点之间的最短路径
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
d[i][j] |= (d[i][k] && d[k][j]);//dp
}
//输出
int ans = 0;
for(int i = 1; i <= n; i++){
int t = 0;
for(int j = 1; j <= n; j++)
if(d[i][j] | d[j][i]) t++; //可以比较i,j之间的关系
if(t == n - 1) ans++;//可以比较其他n-1个点的关系,说明可以被定位
}
cout << ans;
return 0;
}
之前写的臭代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;
int d[N][N], d2[N][N], n, m;
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
scanf("%d%d",&x,&y);
d[x][y] = d2[y][x] = 1;
//d[x][y] = 1,代表x > y
//d[y][x] = 1,代表y < x
}
//floyd求任意两点之间的最短路径
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
d[i][j] |= (d[i][k] && d[k][j]);//d与d2互不干扰,分开dp
d2[i][j] |= (d2[i][k] && d2[k][j]);
}
//输出
int ans = 0;
for(int i = 1; i <= n; i++){
int t = 0;
for(int j = 1; j <= n; j++)
if(d[i][j] | d2[i][j]) t++;//可以比较i,j之间的关系
if(t == n - 1) ans++;//可以比较其他n-1个点的关系,说明可以被定位
}
cout << ans;
return 0;
}
请问为什么这里要用两个数组记录关系呢,记录关系存在的时候 $d(i,j)=d(j,i)=1$ 为什么不行呢
大于的关系和小于的关系不能混用,你可以思考一下
A < B A < C !=> B < C 是这个意思嘛
这样只用一个数组也能AC呀
确实