bzoj 3373: [Usaco2004 Mar]Lying Livestock 说谎的牲畜
2024-09-27 22:49:49
3373: [Usaco2004 Mar]Lying Livestock 说谎的牲畜
Description
兽群中总是有一些麻烦制造者.约翰知道他的N(1≤N≤100)头奶牛中有一头总是说谎,其他的总是说真话.他想快速的找出这个麻烦制造者.为了实现这个目标,他一个一个的问这些奶牛Q(1≤Q≤1000)个关于它们吃草的简单问题(虽然大多数奶牛是诚实的但它们依旧很笨只能懂得一些关于食物的话题).
他将这些问题用以下的格式写了下来:
牛4说:牛5比牛10吃得多
牛6说:牛10比牛7吃得多
牛3说:牛2比牛6吃得多
牛1说:牛7比牛5吃得多
从这个例子中不难看出说谎的奶牛只有可能是4,6,1.你的任务是确定可能说谎的奶牛的个
数.可能说谎的奶牛是指如果这头奶牛说谎则输入数据中不存在矛盾.
Input
第1行:两个用空格分开的整数N和Q.第2到Q+1:每一行描述一个问题,由3个用空格隔开的整数A,B,C表示,意思是A说B牛吃的比C牛多.一头奶牛可能回答多次.
Output
仅一行一个整数即可能说谎的奶牛的头数.
Sample Input
3 4
3 1 2
1 3 1
1 3 2
2 2 1
3 1 2
1 3 1
1 3 2
2 2 1
Sample Output
2
样例说明
3头奶牛给出了4个回答.奶牛1说3>1,3>2,奶牛2说2>1,奶牛3说1>2.当然“>”的意思是“吃得多”. 显然,2号和3号的话是矛盾的.它们都有可能说谎.如果1号说谎则2,3都没说谎,那是不可能的.所以,1号说的一定是实话.
样例说明
3头奶牛给出了4个回答.奶牛1说3>1,3>2,奶牛2说2>1,奶牛3说1>2.当然“>”的意思是“吃得多”. 显然,2号和3号的话是矛盾的.它们都有可能说谎.如果1号说谎则2,3都没说谎,那是不可能的.所以,1号说的一定是实话.
题解:
n最大只有100,所以枚举每头牛还是很显然的。
我们假设这头牛说谎,那么对于当前这头牛说的话,x>y变为x<=y,则y+0<=x,y向x连一条权值为0的边;反之x+1>=y,x向y连一条权值为-1的边,最后跑一边最短路判负环。。
#include<stdio.h>
#include<iostream>
using namespace std;
const int N=;
const int M=;
int n,m,i,j,ans,w,a[M],x[M],y[M],dis[N],s[N],p[N],g[M];
int tot,head[N],Next[M],to[M],v[M];
void add(int x,int y,int z)
{
tot++;
to[tot]=y;
v[tot]=z;
Next[tot]=head[x];
head[x]=tot;
}
int spfa(int X)
{
int x,i;
w=;
for(i=;i<=n;i++)
dis[i]=,p[i]=,s[i]=,g[++w]=i;
while(w)
{
x=g[w--];
if(s[x]>=n) return ;
p[x]=;
for(i=head[x];i!=-;i=Next[i])
if(dis[x]+v[i]<dis[to[i]])
{
dis[to[i]]=dis[x]+v[i];
if(p[to[i]]==)
{
p[to[i]]=;
g[++w]=to[i];
s[to[i]]++;
}
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=;i<=m;i++)
scanf("%d%d%d",&a[i],&x[i],&y[i]);
for(i=;i<=n;i++)
{
tot=;
for(j=;j<=n;j++) head[j]=-;
for(j=;j<=m;j++)
if(a[j]==i) add(y[j],x[j],);else add(x[j],y[j],-);
ans+=spfa(i);
}
cout<<ans;
return ;
}
最新文章
- Linux程序包管理之yum及源代码安装
- enum与字符串转换
- linux下使用shell查看apache IP访问量
- Java 参数传递都是值传递
- OS | 哲学家问题
- Android中Listview实现分页加载效果OnScrollListener
- 走进Linux之systemd启动过程
- windows服务安装及卸载
- Windows Azure 上的 Symfony,适用于 PHP 开发者的强大组合
- Bmob 之 列表查询
- Linux文件权限rwx简单了解
- 2018c语言第1次作业
- 通过jstack与jmap分析一次cpu打满的线上故障
- springmvc是如何工作的
- Oracle 学习笔记 (七)
- POJ2253(dijkstra堆优化)
- edraw的符号制作
- 廖雪峰Java2面向对象编程-5包和classpath-1包package
- RYU 灭龙战 fourth day (1)
- 铁乐学python_day05-作业
热门文章
- vue-cli proxyTable中跨域中pathRewrite 怎么用
- ImageView设置边框 以及内部图片居中显示 在AndroidStudio中添加shape.xml文件
- Spring Boot中配置文件application.properties使用
- 从零开始PHP攻略(001)——Bob的汽车零部件商店
- Django【进阶】分页功能Pagination
- python基础===Windows环境下使用pip install 安装出错";Cannot unpack file";解决办法
- CentOS在ssh下远程重装系统
- selenium遇到的一些问题,持续更新
- C基础 一个可以改变linux的函数getch
- VPS性能测试(1):CPU物理个数、内核、超线程、多核心