3436: 小K的农场
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2111 Solved: 986
[Submit][Status][Discuss]
Description
背景
小K是个特么喜欢玩MC的孩纸。。。
描述
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得
一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多
多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存
不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
Input
第一行包括两个整数n和m，分别表示农场数目和小K记忆中的信息的数目接下来m行：如果每行的第一个数是1，接
下来有三个整数a,b,c，表示农场a比农场b至少多种植了c个单位的作物如果每行第一个数是2，接下来有三个整数a
，b，c，表示农场a比农场b至多多种植了c个单位的作物如果每行第一个数是3，接下来有两个整数a,b，表示农场a
种植的数量与b一样。1<=n,m,a,b,c<=10000
Output
如果存在某种情况与小K的记忆吻合，输出”Yes”，否则输出”No”
Sample Input
3 3
3 1 2
1 1 3 1
2 2 3 2
3 1 2
1 1 3 1
2 2 3 2
Sample Output
Yes
样例解释
三个农场种植的数量可以为（2,2,1）
样例解释
三个农场种植的数量可以为（2,2,1）
HINT
Source
（注意判定条件是>N，不是大于等于。
用dis表示不等式，然后跑最短路或者最长路即可。 9520ms
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn],To[maxn],Len[maxn];
int cnt,vis[maxn],num[maxn],dis[maxn],N;
void add(int u,int v,int w){
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w;
}
bool SPFA()
{
queue<int>q;
memset(dis,-,sizeof(dis));
dis[]=; q.push(); vis[]=; num[]++;
while(!q.empty()){
int u=q.front(); q.pop(); vis[u]=;
for(int i=Laxt[u];i;i=Next[i]){ int v=To[i];
if(dis[v]<dis[u]+Len[i]){
dis[v]=dis[u]+Len[i];
if((++num[v])>N) return false;
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return true;
}
int main()
{
int M,opt,a,b,c;
scanf("%d%d",&N,&M);
rep(i,,N) add(,i,);
rep(i,,M){
scanf("%d",&opt);
if(opt==) {
scanf("%d%d%d",&a,&b,&c);
add(b,a,c);
}
else if(opt==) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,-c);
}
else {
scanf("%d%d",&a,&b);
add(a,b,); add(b,a,);
}
}
if(SPFA()) puts("Yes");
else puts("No");
return ;
}
然后优化了一下，把次数改为前者+1，而不是自加1。4452ms。 但是注意一下，CF1131D里这样是错的。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn<<],To[maxn<<],Len[maxn<<];
int cnt,vis[maxn],num[maxn],dis[maxn],N;
void add(int u,int v,int w){
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w;
}
bool SPFA()
{
queue<int>q;
memset(dis,-,sizeof(dis));
dis[]=; q.push(); vis[]=; num[]++;
while(!q.empty()){
int u=q.front(); q.pop(); vis[u]=;
for(int i=Laxt[u];i;i=Next[i]){ int v=To[i];
if(dis[v]<dis[u]+Len[i]){
dis[v]=dis[u]+Len[i];
num[v]=num[u]+;
if(num[v]>N) return false;
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return true;
}
int main()
{
int M,opt,a,b,c;
scanf("%d%d",&N,&M);
rep(i,,N) add(,i,);
rep(i,,M){
scanf("%d",&opt);
if(opt==) {
scanf("%d%d%d",&a,&b,&c);
add(b,a,c);
}
else if(opt==) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,-c);
}
else {
scanf("%d%d",&a,&b);
add(a,b,); add(b,a,);
}
}
if(SPFA()) puts("Yes");
else puts("No");
return ;
}
把queue改为stack，然后就124ms了，估计不是因为queue比stack快，而是数据使然。
（据说是改为stck变为深搜DFS了！）
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn<<],To[maxn<<],Len[maxn<<];
int cnt,vis[maxn],num[maxn],dis[maxn],N;
void add(int u,int v,int w){
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w;
}
bool SPFA()
{
stack<int>q;
memset(dis,-,sizeof(dis));
dis[]=; q.push(); vis[]=; num[]++;
while(!q.empty()){
int u=q.top(); q.pop(); vis[u]=;
for(int i=Laxt[u];i;i=Next[i]){ int v=To[i];
if(dis[v]<dis[u]+Len[i]){
dis[v]=dis[u]+Len[i];
num[v]=num[u]+;
if(num[v]>N) return false;
if(!vis[v]) vis[v]=,q.push(v);
}
}
}
return true;
}
int main()
{
int M,opt,a,b,c;
scanf("%d%d",&N,&M);
rep(i,,N) add(,i,);
rep(i,,M){
scanf("%d",&opt);
if(opt==) {
scanf("%d%d%d",&a,&b,&c);
add(b,a,c);
}
else if(opt==) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,-c);
}
else {
scanf("%d%d",&a,&b);
add(a,b,); add(b,a,);
}
}
if(SPFA()) puts("Yes");
else puts("No");
return ;
}