思路：
怎么可能有思路呜呜呜思路一：除了A可以打败B时，将 mp[A][B] 置1，其余全部为零，求最长路。 注意：Floyd内的判断比较难想，需要手推一下，发现若不加判断会把不可达的点变可达，显然不可以。思路二：传递闭包。感谢chc960609的BLOG。
代码：
求最长路：125ms 712kB
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std
;
const int maxn
= 105;
int mp
[maxn
][maxn
];
int N
,M
;
void Floyd(){
for(int k
=1;k
<=N
;k
++)
for(int i
=1;i
<=N
;i
++)
for(int j
=1;j
<=N
;j
++){
if(i
== j
)
continue;
if(mp
[k
][j
] && mp
[i
][k
])
mp
[i
][j
] = max(mp
[i
][j
] , mp
[i
][k
] + mp
[k
][j
]);
}
return ;
}
int main(){
cin
>>N
>>M
;
memset(mp
,0,sizeof(mp
));
for(int i
=1;i
<=M
;i
++){
int A
,B
;
cin
>>A
>>B
;
mp
[A
][B
] = 1;
}
Floyd();
int ans
= 0;
for(int i
=1;i
<=N
;i
++){
int j
;
for(j
=1;j
<=N
;j
++){
if(i
== j
)
continue;
if(mp
[i
][j
] || mp
[j
][i
])
;
else
break;
}
if(j
> N
)
ans
++;
}
cout
<<ans
<<endl
;
return 0;
}
传递闭包：110ms 676kB
#include <iostream>
#include <cstring>
using namespace std
;
const int maxn
= 105;
bool mp
[maxn
][maxn
];
int N
,M
;
void Floyd(){
for(int k
=1;k
<=N
;k
++)
for(int i
=1;i
<=N
;i
++)
for(int j
=1;j
<=N
;j
++)
mp
[i
][j
] = mp
[i
][j
] || (mp
[i
][k
]&&mp
[k
][j
]);
return ;
}
int main(){
memset(mp
,0,sizeof(mp
));
cin
>>N
>>M
;
for(int i
=1;i
<=N
;i
++)
mp
[i
][i
] = true
;
while(M
--){
int a
,b
;
cin
>>a
>>b
;
mp
[a
][b
] = true
;
}
Floyd();
int ans
= 0;
for(int i
=1;i
<=N
;i
++){
int j
;
for(j
=1;j
<=N
;j
++){
if(mp
[i
][j
] || mp
[j
][i
])
;
else
break;
}
if(j
>N
)
ans
++;
}
cout
<<ans
<<endl
;
return 0;
}
