题意：
农场主 FJ 有 n 头奶牛，现在给你 m 对关系(x,y)表示奶牛x的产奶速率高于奶牛y；
FJ 想按照奶牛的产奶速率由高到低排列这些奶牛，但是这 m 对关系可能不能精确确定这 n 头奶牛的关系；
问最少需要额外增加多少对关系使得可以确定这 n 头奶牛的顺序；
题解：
之所以做这道题，是因为在补CF的题时用到了bitset<>；
搜这个容器的用法是看到了一篇标题为POJ-3275:奶牛排序Ranking the Cows(Floyd、bitset)的文章；
正好拿着道题练练bitset<>；
但是一做，发现，这道题和省赛的L题好像啊，做法完全相同，只是在输出结果上处理了一下；
下午在补一下如何用bitset<>做这道题，先贴上DFS暴力AC代码；
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e3+; int n,m;
int num;
int head[maxn];
struct Edge
{
int to;
int next;
}G[maxn**];
void addEdge(int u,int v)
{
G[num]={v,head[u]};
head[u]=num++;
}
bool vis[maxn]; int DFS(int u)
{
int ans=;
vis[u]=true;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(vis[v] || (i&))
continue;
ans += DFS(v);
}
return ans;
}
int RDFS(int u)
{
int ans=;
vis[u]=true;
for(int i=head[u];~i;i=G[i].next)
{
int v=G[i].to;
if(vis[v] || !(i&))
continue;
ans += RDFS(v);
}
return ans;
}
int Solve()
{
int ans=;
for(int i=;i <= n;++i)
{
mem(vis,false);
int t1=DFS(i);
mem(vis,false);
int t2=RDFS(i);
///第i头奶牛可以确定的奶牛个数为t1+t2-1
ans += n-(t1+t2-);
}
return ans>>;
}
void Init()
{
num=;
mem(head,-);
}
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);
addEdge(v,u);
}
printf("%d\n",Solve());
}
return ;
}
思路2：（来自上述链接文章）
确定这 n 头奶牛的顺序需要 n*(n-1)/2 对关系；
(X,Y)代表 rankX > rankY
已知关系 (X,Y),(Y,Z)，那么，根据传递性可得隐藏关系(X,Z)；
如何根据给出的m条关系找到所有的隐藏关系呢？
Floyd传递闭包；
AC代码1：
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e3+; int n,m;
bool e[maxn][maxn];
vector<int >in[maxn],out[maxn];
///in[u]:指向u的节点，out[u]:u指出去的节点 int Solve()
{
int ans=;
for(int k=;k <= n;++k)
{
for(int i=;i < in[k].size();++i)
{
for(int j=;j < out[k].size();++j)
{
int u=in[k][i];
int v=out[k][j];
if(!e[u][v])///隐藏关系u->v
{
e[u][v]=true;
out[u].push_back(v);
in[v].push_back(u);
ans++;
}
}
}
}
///m:已知关系对
///ans:隐藏关系对
return n*(n-)/-m-ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i <= m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
in[v].push_back(u);
out[u].push_back(v);
e[u][v]=true;
}
printf("%d\n",Solve()); return ;
}
另一种写法就是用到了bitset<>容器；
bitset<>_bit[];
对于输入的关系<u,v>;
_bit[u].set(v);//将第v为置位1，表示有一条u->v的边
如何找到所有的隐藏关系呢？
for(int i=;i <= n;++i)
for(int j=;j <= n;++j)
if(_bit[j][i])
_bit[j] |= _bit[i];///让j节点指向i节点所有指出去的边
晚上一直困惑，为什么将if()及其之后的语句改为
if(_bit[i][j])
_bit[i] |= _bit[j];
就wa了，找了许久，终于找到了；
对于如下关系：
(①,③) , (③,②) , (②,④)
（①->③->②->④）
当 i = 1 时，如果按照更改后的写法，①只会更新出<①,②>而不会更新出关系<①,④>（纸上画一下就出来了）；
所以说，要更新内层循环的节点，这样更新的彻底；
AC代码2：
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<bitset>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=1e3+; int n,m;
bitset<maxn>_bit[maxn]; int Solve()
{
for(int i=;i <= n;++i)
for(int j=;j <= n;++j)
if(_bit[j][i])
_bit[j] |= _bit[i];///让j节点指向i节点所有指出去的边 int ans=;
for(int i=;i <= n;++i)
ans += _bit[i].count(); ///ans:m对已有关系对+隐藏关系对
return n*(n-)/-ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i <= m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
_bit[u].set(v);
}
printf("%d\n",Solve()); return ;
}