佛山网站改版,中国联通与腾讯设立,国外域名免费注册,开发平台的公司【模板】差分约束算法
题目描述
给出一组包含 m m m 个不等式#xff0c;有 n n n 个未知数的形如#xff1a; { x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c_1}\leq y_1 \\x_{c_2}-x_{c_2} \leq y_2 \\…【模板】差分约束算法
题目描述
给出一组包含 m m m 个不等式有 n n n 个未知数的形如 { x c 1 − x c 1 ′ ≤ y 1 x c 2 − x c 2 ′ ≤ y 2 ⋯ x c m − x c m ′ ≤ y m \begin{cases} x_{c_1}-x_{c_1}\leq y_1 \\x_{c_2}-x_{c_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c_m}\leq y_m\end{cases} ⎩ ⎨ ⎧xc1−xc1′≤y1xc2−xc2′≤y2⋯xcm−xcm′≤ym
的不等式组求任意一组满足这个不等式组的解。
输入格式
第一行为两个正整数 n , m n,m n,m代表未知数的数量和不等式的数量。
接下来 m m m 行每行包含三个整数 c , c ′ , y c,c,y c,c′,y代表一个不等式 x c − x c ′ ≤ y x_c-x_{c}\leq y xc−xc′≤y。
输出格式
一行 n n n 个数表示 x 1 , x 2 ⋯ x n x_1 , x_2 \cdots x_n x1,x2⋯xn 的一组可行解如果有多组解请输出任意一组无解请输出 NO。
样例 #1
样例输入 #1
3 3
1 2 3
2 3 -2
1 3 1样例输出 #1
5 3 5提示
样例解释 { x 1 − x 2 ≤ 3 x 2 − x 3 ≤ − 2 x 1 − x 3 ≤ 1 \begin{cases}x_1-x_2\leq 3 \\ x_2 - x_3 \leq -2 \\ x_1 - x_3 \leq 1 \end{cases} ⎩ ⎨ ⎧x1−x2≤3x2−x3≤−2x1−x3≤1
一种可行的方法是 x 1 5 , x 2 3 , x 3 5 x_1 5, x_2 3, x_3 5 x15,x23,x35。 { 5 − 3 2 ≤ 3 3 − 5 − 2 ≤ − 2 5 − 5 0 ≤ 1 \begin{cases}5-3 2\leq 3 \\ 3 - 5 -2 \leq -2 \\ 5 - 5 0\leq 1 \end{cases} ⎩ ⎨ ⎧5−32≤33−5−2≤−25−50≤1
数据范围
对于 100 % 100\% 100% 的数据 1 ≤ n , m ≤ 5 × 1 0 3 1\leq n,m \leq 5\times 10^3 1≤n,m≤5×103 − 1 0 4 ≤ y ≤ 1 0 4 -10^4\leq y\leq 10^4 −104≤y≤104 1 ≤ c , c ′ ≤ n 1\leq c,c\leq n 1≤c,c′≤n c ≠ c ′ c \neq c cc′。
评分策略
你的答案符合该不等式组即可得分请确保你的答案中的数据在 int 范围内。
如果并没有答案而你的程序给出了答案SPJ 会给出 There is no answer, but you gave it结果为 WA 如果并没有答案而你的程序输出了 NOSPJ 会给出 No answer结果为 AC 如果存在答案而你的答案错误SPJ 会给出 Wrong answer结果为 WA 如果存在答案且你的答案正确SPJ 会给出 The answer is correct结果为 AC。
差分约束模板
我们知道在SPFA中在单源最短路问题中如果存在一条 → 长为 的边在计算1 号点到每个点的最短路后一定有 [] ≥ []。 x i c ≥ x j x_ic \ge x_j xic≥xj 与其相同 所以若存在 x i c ≥ x j x_ic \ge x_j xic≥xj,使用图论便是连边(i,j,c)
代码
#includebits/stdc.h
using namespace std;
const int M1e4;
int dis[M],cnt[M];
bool inQueue[M];
queueint Q;
#define _for(i,a,b) for(int i(a);i(b);i)
#define for_(i,a,b) for(int i(a);i(b);i--)
#define _rep(i,a,b) for(int i(a);i(b);i)
vectorpairint, int edges[M];
void add(int u,int v,int w){edges[u].emplace_back(v, w);
}
bool spfa(int s,int n){memset(dis, 0x3f, sizeof(dis));dis[s] 0;Q.push(s);inQueue[s] true;while (!Q.empty()) {int x Q.front();Q.pop();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.push(edge.first);inQueue[edge.first] true;cnt[edge.first];if (cnt[edge.first]1n) return false;}}}return true;
}
int main(){int n,m;cinnm;_for(i,1,n) add(0,i,0);_for(i,1,m){int u,v,w;cinvuw;add(u,v,w);}if (!spfa(0,n)) {coutNO;return 0;}_for(i,1,n) coutdis[i] ;return 0;
}分析
spfa模板上面的分析这里说下存图
vectorpairint, int edges[M];就是 vectorpairv,w edges[u];
