3436: 小K的农场
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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=100010; 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,-1,sizeof(dis)); dis[0]=0; q.push(0); vis[10]=1; num[0]++; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; 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]=1,q.push(v); } } } return true; } int main() { int M,opt,a,b,c; scanf("%d%d",&N,&M); rep(i,1,N) add(0,i,0); rep(i,1,M){ scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&a,&b,&c); add(b,a,c); } else if(opt==2) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } else { scanf("%d%d",&a,&b); add(a,b,0); add(b,a,0); } } if(SPFA()) puts("Yes"); else puts("No"); return 0; }
然后优化了一下，把次数改为前者+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=20010; int Laxt[maxn],Next[maxn<<1],To[maxn<<1],Len[maxn<<1]; 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,-1,sizeof(dis)); dis[0]=0; q.push(0); vis[0]=1; num[0]++; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; 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]+1; if(num[v]>N) return false; if(!vis[v]) vis[v]=1,q.push(v); } } } return true; } int main() { int M,opt,a,b,c; scanf("%d%d",&N,&M); rep(i,1,N) add(0,i,0); rep(i,1,M){ scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&a,&b,&c); add(b,a,c); } else if(opt==2) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } else { scanf("%d%d",&a,&b); add(a,b,0); add(b,a,0); } } if(SPFA()) puts("Yes"); else puts("No"); return 0; }
把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=20010; int Laxt[maxn],Next[maxn<<1],To[maxn<<1],Len[maxn<<1]; 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,-1,sizeof(dis)); dis[0]=0; q.push(0); vis[0]=1; num[0]++; while(!q.empty()){ int u=q.top(); q.pop(); vis[u]=0; 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]+1; if(num[v]>N) return false; if(!vis[v]) vis[v]=1,q.push(v); } } } return true; } int main() { int M,opt,a,b,c; scanf("%d%d",&N,&M); rep(i,1,N) add(0,i,0); rep(i,1,M){ scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&a,&b,&c); add(b,a,c); } else if(opt==2) { scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } else { scanf("%d%d",&a,&b); add(a,b,0); add(b,a,0); } } if(SPFA()) puts("Yes"); else puts("No"); return 0; }