<题目链接>
题目大意：
FJ想按照奶牛产奶的能力给她们排序。现在已知有N头奶牛$(1 ≤ N ≤ 1,000)$。FJ通过比较，已经知道了M$1 ≤ M ≤ 10,000$对相对关系。每一对关系表示为“X Y”，意指X的产奶能力强于Y。现在FJ想要知道，他至少还要调查多少对关系才能完成整个排序。
解题分析：
因为完全图只需要$n*(n-1)/2$对关系就能确定所有的所有节点的顺序，所以这里我们只需要求出传递闭包之后，能够确定的关系数，然后相减即可。因为本题 $n\leq10^3$，$O(n^3)$的Floyd复杂度过高，所以这里用到了bitset优化。同时，因为本题边非常少$m\leq10^4$，所以本题还可以用领接表优化Floyd。
bitset优化Floyd
#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std; const int N = 1e3+;
bitset<N>b[N]; int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(b,,sizeof(b));
for(int i=;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
b[u].set(v);
}
for(int j=;j<=n;j++){
for(int i=;i<=n;i++){
if(b[i][j])b[i]|=b[j]; //Floyd传递闭包
}
}
int ans=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(b[i][j])ans++; //ans为传递闭包之后，全图的关系对
}
}
printf("%d\n",n*(n-)/-ans); //n*(n-1)/2为完全图所需的关系对，减去当前图的关系对之后，就是需要添加的关系对
}
}
领接表优化Floyd
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std; #define pb push_back
const int N = 1e3+;
vector<int>from[N],to[N];
bool mp[N][N];
int n,m; void init(){
memset(mp,false,sizeof(mp));
for(int i=;i<=n;i++){
from[i].clear();to[i].clear();
}
}
void addedge(int u,int v){
mp[u][v]=true;
from[v].pb(u),to[u].pb(v);
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
for(int i=;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);
}
for(int k=;k<=n;k++){
for(int i=;i<from[k].size();i++){ //能够直接到达k的点
for(int j=;j<to[k].size();j++){ //能够由k直接到达的点
int u=from[k][i],v=to[k][j];
if(!mp[u][v])addedge(u,v); //只用更新那些没有传递关系的点
}
}
}
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(mp[i][j])ans++;
printf("%d\n",n*(n-)/-ans);
}
}
2019-03-07