Codeforces Gym 100015G Guessing Game 差分约束
Guessing Game
题目连接:
http://codeforces.com/gym/100015/attachments
Description
Jaehyun has two lists of integers, namely a1,...,aN and b1,...,bM.Je!rey wants to know what these
numbers are, but Jaehyun won’t tell him the numbers directly. So, Je!rey asks Jaehyun a series of questions
of the form “How big is ai + bj ?” Jaehyun won’t even tell him that, though; instead, he answers either
“It’s at least c,” or “It’s at most c.” (Right, Jaehyun simply doesn’t want to give his numbers for whatever
reason.) After getting Jaehyun’s responses, Je!rey tries to guess the numbers, but he cannot figure them out
no matter how hard he tries. He starts to wonder if Jaehyun has lied while answering some of the questions.
Write a program to help Je!rey.
Input
The input consists of multiple test cases. Each test case begins with a line containing three positive integers
N, M,and Q, which denote the lengths of the Jaehyun’s lists and the number of questions that Je!rey
asked. These numbers satisfy 2 ! N + M ! 1,000 and 1 ! Q ! 10,000. Each of the next Q lines is of the
form ij<=c or ij>=c.Theformerrepresents ai + bj ! c, and the latter represents ai + bj " c. It is
guaranteed that #1,000 ! c ! 1,000. The input terminates with a line with N = M = Q = 0. For example:
Output
For each test case, print a single line that contains “Possible” if there exist integers a1,...,aN and b1,...,bM
that are consistent with Jaehyun’s answers, or “Impossible” if it can be proven that Jaehyun has definitely
lied (quotes added for clarity). The correct output for the sample input above would be:
Sample Input
2 1 3
1 1 <= 3
2 1 <= 5
1 1 >= 4
2 2 4
1 1 <= 3
2 1 <= 4
1 2 >= 5
2 2 >= 7
0 0 0
Sample Output
Impossible
Possible
Hint
题意
a数组有n个数,b数组有m个数
然后告诉你一些不等式表示a[i]+b[j]<=C之类的
问你能否找到一组解
题解:
差分约束的裸题
我们建边之后,跑最短路,看是否有负环,如果存在负环的话,就说明这个不等式显然是不成立的
就好了
代码
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct node
{
int x,y;
};
vector<node> E[2005];
int n,m,q;
int inq[2005],dis[2005];
int flag=0;
void solve(int x)
{
if(flag)
return;
inq[x]=1;
for(int i=0;i<E[x].size();i++)
{
node v = E[x][i];
if(dis[v.x]>dis[x]+v.y)
{
dis[v.x]=dis[x]+v.y;
if(inq[v.x])
{
flag=1;
return;
}
if(!inq[v.x])
{
dis[v.x]=dis[x]+v.y;
solve(v.x);
}
}
}
inq[x]=0;
}
int main()
{
//freopen("1.in","r",stdin);
while(scanf("%d%d%d",&n,&m,&q)!=EOF)
{
if(n==0&&m==0&&q==0)
break;
flag = 0;
memset(inq,0,sizeof(inq));
memset(dis,0,sizeof(dis));
for(int i=0;i<=n+m;i++)
E[i].clear();
for(int i=0;i<=n;i++)
dis[i]=inf;
for(int i=0;i<q;i++)
{
int x,y,z;
string s;
scanf("%d%d",&x,&y);cin>>s;
scanf("%d",&z);
if(s==">=")
E[x].push_back((node){n+y,-z});
if(s=="<=")
E[y+n].push_back((node){x,z});
}
for(int i=1;i<=n+m;i++)
dis[i]=0,solve(i);
if(flag)printf("Impossible\n");
else printf("Possible\n");
}
}
最新文章
- centos下升级mysql后遇到的小问题
- TypeScript Generics(泛型)
- Centos6.5下的Hadoop安装
- 关于分布式事务的一个误解:使用了TransactionScope就一定会开启分布式事务吗?
- NYOJ题目766回文数
- centos更改默认语言
- gif动态图片去白边,杂边
- LiteHttp:一款‘智能’的HTTP框架类库
- css/js online online code editor/formator/debuger
- 0环境设置 - SQLPLUS设置
- 批量执行sql语句
- python下使用protobuf
- 《JavaScript设计模式与开发实践》笔记第一章
- 01 响应式页面-@media介绍,
- DroidGap
- Yahoo邮箱最后登录,成为历史!
- 4820: [Sdoi2017]硬币游戏
- [CodeForces]CodeForces 13D 几何 思维
- Python编程-基础知识-List
- 解决js中文输入法无法触发onkeyup事件问题(转)
热门文章
- java定时器的几种用法
- <;转>;selenium+python+API分类总结
- WebGoat学习——跨站请求伪造(Cross Site Request Forgery (CSRF))
- TCP/IP 相关知识点与面试题集
- PYTHON压平嵌套列表
- java webservice的多种实现方法汇总
- (原创)jquery插件-可选可填控件
- 随手记录一个 firefox的backgroundPostion-x和-y的问题
- JVM系列四:生产环境参数实例及分析【生产环境实例增加中】
- C# Common Keyword