POJ3275:Ranking the Cows(Bitset加速floyd求闭包传递)
Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.
FJ has already compared the milk output rate for M (1 ≤ M ≤ 10,000) pairs of cows. He wants to make a list of C additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible.
Input
Lines 2.. M+1: Two space-separated integers, respectively: X and Y. Both X and Y are in the range 1... N and describe a comparison where cow X was ranked higher than cowY.
Output
Sample Input
5 5
2 1
1 5
2 3
1 4
3 4
Sample Output
3
Hint
题意:有N头奶牛,现在给出M对产奶量关系U>V,问至少还需要知道多少奶牛可以做到全部奶牛产奶关系。
思路:有向图,问至少再加多少边,使得任意两点S、T的可以到达(S到达T或者到达S)。闭包传递后不能到达的需要加边,ans++。
至于为什么闭包传递后不连通就就要ans++呢,假设已知了1>2>3>4,5>6>7,我们知道了4>5不就行了吗,ans=1啊。
但是注意题目说的是"确定",而比较了4和5之后可能会4<5,即任然不可以把知道全部顺序。
所以剩下对于C(n,2)对关系里不确定的关系,都有知道才能“确定”所有的大小关系。
#include<cstdio>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
bitset<maxn>mp[maxn];
int main()
{
int N,M,ans,i,j,k;
while(~scanf("%d%d",&N,&M)){
ans=;memset(mp,,sizeof(mp));
for(i=;i<=M;i++){
scanf("%d%d",&j,&k);
mp[j].set(k);
} for(k=;k<=N;k++)
for(i=;i<=N;i++)
if(mp[i][k])
mp[i]|=mp[k];
for(i=;i<=N;i++)
for(j=i+;j<=N;j++)
if(!mp[i][j]&&!mp[j][i])
ans++;
printf("%d\n",ans);
}
return ;
}
最新文章
- cocos2d-x宏定义
- SQL语句小总结
- web工程依赖的问题
- javascript中数组揭秘
- coins_多重背包
- Map中如何把没有定义操作符<;的类作为key
- Tomcat架构(二)
- BZOJ 1782: [Usaco2010 Feb]slowdown 慢慢游( BIT + dfs )
- CentOS6.8安装mysql5.6
- java调用wkhtmltopdf生成pdf文件,美观,省事
- 常用CSS样式速查
- 补齐-Django之Model操作
- TCP加速锐速SS(ServerSpeeder)破解版一键安装
- 2018.11.01 bzoj4325: NOIP2015 斗地主(贪心+搜索)
- Exception in thread main java.lang.NoClassDefFoundError: org/apache/juli/logging/LogFacto
- sql server 查询分析器中表名无效,有红线,其实是这张表的
- 仿照swpu邮寄系统的登录页面
- 【spring源码学习】spring的IOC容器之自定义xml配置标签扩展namspaceHandler向IOC容器中注册bean
- 不使用C++ 11的整数转字符串
- Git在Xcode中的配置与使用常见问题总结