[Acwing] 1169. 糖果 差分约束

前言

这才多久,作业就这么多了 传送门 :

思路

差分约束 :

X i > = X j + C 1 那 么 我 们 可 以 建 立 一 条 从 i 到 j 的 边 边 权 为 C i X_i >= X_j+C_1那么我们可以建立一条从i到j的边边权为C_i Xi​>=Xj​+C1​那么我们可以建立一条从i到j的边边权为Ci​

根据这个性质我们只需要提炼出 题目中的不等式最后建图跑 SPFA或者DIJ即可

如果是答案的最小值那么我们需要跑一遍最长路

否则我们需要跑一遍最短路

CODE

// Problem: 糖果
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/1171/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Problem: String
// Contest: HDOJ
// URL: http://acm.hdu.edu.cn/showproblem.php?pid=4821
// Memory Limit: 32 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

// Problem: P2738 [USACO4.1]���ʻ�·Fence Loops
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2738
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define px first
#define py second
#define pb push_back
typedef pair pii;
int dxy[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
const int N  = 1e5+10;


struct union_find_set{
    int n,p[N];
    void init(int N)
    {
        n = N;
        for(int i=1;i