五通桥移动网站建设,抚州营销型网站建设,搜索引擎优化是什么,优秀个人主页小 K 的农场
题目描述
小 K 在 MC 里面建立很多很多的农场#xff0c;总共 n n n 个#xff0c;以至于他自己都忘记了每个农场中种植作物的具体数量了#xff0c;他只记得一些含糊的信息#xff08;共 m m m 个#xff09;#xff0c;以下列三种形式描述#xff1a;…小 K 的农场
题目描述
小 K 在 MC 里面建立很多很多的农场总共 n n n 个以至于他自己都忘记了每个农场中种植作物的具体数量了他只记得一些含糊的信息共 m m m 个以下列三种形式描述
农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物农场 a a a 与农场 b b b 种植的作物数一样多。
但是由于小 K 的记忆有些偏差所以他想要知道存不存在一种情况使得农场的种植作物数量与他记忆中的所有信息吻合。
输入格式
第一行包括两个整数 n n n 和 m m m分别表示农场数目和小 K 记忆中的信息数目。
接下来 m m m 行
如果每行的第一个数是 1 1 1接下来有三个整数 a , b , c a,b,c a,b,c表示农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物如果每行的第一个数是 2 2 2接下来有三个整数 a , b , c a,b,c a,b,c表示农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物;如果每行的第一个数是 3 3 3接下来有两个整数 a , b a,b a,b表示农场 a a a 种植的的数量和 b b b 一样多。
输出格式
如果存在某种情况与小 K 的记忆吻合输出 Yes否则输出 No。
样例 #1
样例输入 #1
3 3
3 1 2
1 1 3 1
2 2 3 2样例输出 #1
Yes提示
对于 100 % 100\% 100% 的数据保证 1 ≤ n , m , a , b , c ≤ 5 × 1 0 3 1 \le n,m,a,b,c \le 5 \times 10^3 1≤n,m,a,b,c≤5×103。
分析
差分约束模型把每个都分析一下
农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物 x a − c ≥ x b x_a-c \ge x_b xa−c≥xb,构成a,b,-c农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物 x b c ≥ x a x_bc \ge x_a xbc≥xa,构成b,a,c农场 a a a 与农场 b b b 种植的作物数一样多 x a x b → x a ≥ x b , x b ≥ x a x_ax_b \to x_a \ge x_b,x_b \ge x_a xaxb→xa≥xb,xb≥xa构成a,b,0,(b,a,0)
代码
#includebits/stdc.h
using namespace std;
const int MAXN1e85,M1e6;
vectorpairint,int edges[M];
int dis[M];
int n,m,s;
int cnt[M];
bool inQueue[MAXN];
int q[MAXN],f1,t1;
void add(int u,int v,int w){edges[u].emplace_back(v,w);}
void read(){cinnm;for(int i1,u,v,w,opt;im;i) {cinoptuv;if(opt3) cinw;if(opt1) add(u,v,-w);if(opt2) add(v,u,w);if(opt3) {add(u,v,0);add(v,u,0);} }
}
bool spfa(int s0)
{memset(dis,0x3f,sizeof(dis));dis[s]0;q[t]s;inQueue[s]true;while(ft){int xq[f];inQueue[x]false;for(auto edge:edges[x]){if(dis[edge.first]dis[x]edge.second) continue;dis[edge.first]dis[x]edge.second;if(!inQueue[edge.first]){q[t]edge.first;inQueue[edge.first]true;cnt[edge.first];if(cnt[edge.first]n1) return false;}}}return true;
}
void solve(){for(int i1;in;i) add(0,i,0);if(!spfa()) coutNo; else coutYes;
}
int main()
{read();solve();return 0;
}分析
1.超级源点
void solve(){for(int i1;in;i) add(0,i,0);if(!spfa()) coutNo; else coutYes;
}差分约束需要超级源点需要与每个点构成一条边权值为0因为spfa可以有效判断负环if(cnt[edge.first]n1) return false;需要注意此处为n1因为有超级源点
2.效率问题
STL库中的queue效率低下常数较高在不开O2的前提下容易tle推荐手打队
q.push(x) → \to →q[tail]x;q.pop() → \to → head;q.top() → \to → q[head]
