网络宣传网站建设价格,做黑网站赚钱吗,app网站开发培训,网络营销的特点有哪些题目
幼儿园里有 N 个小朋友#xff0c;老师现在想要给这些小朋友们分配糖果#xff0c;要求每个小朋友都要分到糖果。
但是小朋友们也有嫉妒心#xff0c;总是会提出一些要求#xff0c;比如小明不希望小红分到的糖果比他的多#xff0c;于是在分配糖果的时候#xff…题目
幼儿园里有 N 个小朋友老师现在想要给这些小朋友们分配糖果要求每个小朋友都要分到糖果。
但是小朋友们也有嫉妒心总是会提出一些要求比如小明不希望小红分到的糖果比他的多于是在分配糖果的时候 老师需要满足小朋友们的 K 个要求。
幼儿园的糖果总是有限的老师想知道他至少需要准备多少个糖果才能使得每个小朋友都能够分到糖果并且满足小朋友们所有的要求。
输入格式
输入的第一行是两个整数 N,K。
接下来 K 行表示分配糖果时需要满足的关系每行 3 个数字 X,A,B。
如果 X1表示第 A 个小朋友分到的糖果必须和第 B 个小朋友分到的糖果一样多。如果 X2表示第 A 个小朋友分到的糖果必须少于第 B 个小朋友分到的糖果。如果 X3表示第 A 个小朋友分到的糖果必须不少于第 B 个小朋友分到的糖果。如果 X4表示第 A 个小朋友分到的糖果必须多于第 B 个小朋友分到的糖果。如果 X5表示第 A 个小朋友分到的糖果必须不多于第 B 个小朋友分到的糖果。
小朋友编号从 1 到 N。
输出格式
输出一行表示老师至少需要准备的糖果数如果不能满足小朋友们的所有要求就输出 −1−1。
数据范围
1≤N≤1e5 1≤K≤1e5 1≤X≤5 1≤AB≤N 输入数据完全随机。
输入样例
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1输出样例
11
思路
一、 求不等式组的可行解 建立超级源点需要满足的条件从源点出发一定可以走到所有的边。
步骤 1. 先将每个不等式 xi≤xjck转化成一条从 xj 走到 xi 长度为 ck 的边。 2. 找到一个超级源点使得该源点一定可以遍历到所有边 3. 从源点求一遍单源最短路
结果1如果存在负环则原不等式组一定无解。 结果2如果没有负环则 dist[i] 就是原不等式组的一个可行解。
二、 如何求最大值或者最小值这里的最值指的是每个变量的最值 结论如果求的是最小值则应该求最长路如果求的是最大值则应该求最短路。
问题如何转化 xi≤c 其中 c 是一个常数这类的不等式。
方法建立一个超级源点0然后建立 0 - i 的边长度是 c 即可。
以求 xi 的最大值为例
求所有从 xi 出发构成的多个形如如下的不等式 xi≤xjc1≤xkc2c1≤⋅⋅⋅≤x0c1c2⋅⋅⋅cm(x00)
所计算出的上界最终 xi 的最大值等于所有上界的最小值。
求 xi 的最小值 时则完全相反求一个形如如下不等式链所计算出的下界最终在所有下界里取最大值 xi≥xjc1≥xkc2c1≥⋅⋅⋅≥x0c1c2⋅⋅⋅cm(x00)
转换成图论的问题就是求 dist[i].
本题样例得到的图为 代码
#includebits/stdc.h
#define int long long
using namespace std;
const int N 1e5 10;
int n,k;
int h[N],ne[N * 3],e[N * 3],w[N * 3],idx;
int dist[N];
bool st[N];
int cnt[N];void add(int a,int b,int c)
{ne[idx] h[a],e[idx] b,w[idx] c,h[a] idx ;
}bool spfa()
{stackint q;for(int i 1; i n; i ) add(0,i,1);q.push(0);st[0] true;while(!q.empty()){int t q.top();q.pop();st[t] false;for(int i h[t]; ~i; i ne[i]){int j e[i];if(dist[j] dist[t] w[i]){dist[j] dist[t] w[i];cnt[j] cnt[t] 1;if(cnt[j] n 1) return true;if(st[j]) continue;st[j] true;q.push(j);}}}return false;
}int32_t main()
{cin n k;memset(h,-1,sizeof h);while(k --){int op,a,b;cin op a b;if(op 1) add(b,a,0),add(a,b,0);if(op 2) add(a,b,1);if(op 3) add(b,a,0);if(op 4) add(b,a,1);if(op 5) add(a,b,0);}if(spfa()) cout -1 endl;else{int ans 0;for(int i 1; i n; i ) ans dist[i];cout ans endl;}return 0;
}
难度中等时/空限制1s / 64MB总通过数7228总尝试数25419来源《信息学奥赛一本通》 , SCOI2011算法标签 图论Tarjan算法有向图的强连通分量SPFA差分约束
题目来自AcWing 1169. 糖果 - AcWing
