投稿
  1. 高性能架构探索首页
  2. C/C++

差分约束的几道简单例题(糖果，layout，狡猾的商人，小k的农场）

admin • • C/C++ • 阅读 132

模板传送门

糖果（SCOI2011, luoguP3275）

差分约束的几道简单例题(糖果，layout，狡猾的商人，小k的农场）

  输入 
  5 7
  1 1 2
  2 3 2
  4 4 1
  3 4 5
  5 4 5
  2 3 5
  4 5 1
  输出 
  11

简单的解释：

依然是分析建边：

  • (X=1)，有(A=B)，因为我们要建立不等关系，所以转化一下变成(B geq A+0) (and) (B geq A+0)，这里因为要求最小值所以转化为 (geq) 跑最长路。

  • (X=2)，有(A<B)，转化得(B geq A+1)

  • (X=3)，有(A geq B)，转化得(A geq B+0)（不要吐槽这是废话qwq）

  • (X=4)，有(A>B)，转化得(A geq B+1)

  • (X=5)，有(A leq B)，转化得(B geq A+0)

因为要求分发的总量，搞一个超级源点向各点连边，边权为1，最后累加dis即可

PS:这道题有一个地方是第二条和第四条可以在读入时直接判掉一部分非法情况，因为同一个人糖果数不可能不同。如果不这样剪枝的会T掉两个点，当然你也可以选择最后0到各点加边时倒着来，至于为什么能行咱也不知道。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 100000 + 10;
#define ll long long
#define rint register int

int n, m, len = 0;
int head[maxn], dis[maxn], cnt[maxn];
bool vis[maxn];

struct edge{
    int nex, to, w;
}e[maxn << 2];

void Add(int u, int v, int w){
    e[++len].to = v;
    e[len].nex = head[u];
    e[len].w = w;
    head[u] = len;
}

bool Spfa(int u){
    queue<int> q;
    for(int i = 1; i <= n; i++)
        dis[i] = -1;
    dis[u] = 0;
    vis[u] = 1;
    q.push(u);
    while(!q.empty()){
        int x = q.front();q.pop();
        vis[x] = 0;
        for(rint i = head[x]; i; i = e[i].nex){
            int v = e[i].to;
            if(dis[v] < dis[x] + e[i].w){
                dis[v] = dis[x] + e[i].w;
                if(!vis[v]){
                    if(++cnt[v] >= n) return 0;
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}

int main(){
    cin >> n >> m;
    int x, u, v;
    for(rint i = 1; i <= m; i++){
        scanf("%d %d %d", &x, &u, &v);
        if(x == 1) Add(u, v, 0), Add(v, u, 0);
        else if(x == 2){ 
            if(u == v){
                cout << -1 << endl;
                return 0;
            }
            Add(u, v, 1);
        }
        else if(x == 3) Add(v, u, 0);
        else if(x == 4) {
            if(u == v){
                cout << -1 << endl;
                return 0;
            }
            Add(v, u, 1);
        }
        else if(x == 5) Add(u, v, 0);
    }
    for(rint i = n; i >= 1; i--) Add(0, i, 1);//超级源点倒序加边，为什么会快呢
    if(!Spfa(0)) printf("-1n");
    else{
        ll ans = 0;
        for(rint i = 1; i <= n; i++)
            ans += dis[i];
        cout << ans << endl;
    }
    return 0;
}

Layout

咱考试时的一道水题，明明第一遍敲对了最后还是脑抽改错了，简直。
差分约束的几道简单例题(糖果，layout，狡猾的商人，小k的农场）

差分约束的几道简单例题(糖果，layout，狡猾的商人，小k的农场）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define ll long long
const int maxn = 1000 + 10;
const int maxm = 5000 + 10;
struct node{
    int x, y, dis;
}a[5000<<2], b[5000<<2];

int head[maxn], len = 0, dis[maxn];
int n, M, K;

struct edge{
    int to, nex, w;
}e[maxm << 2];

void Add(int u, int v, int w){
    e[++len].to = v;
    e[len].nex = head[u];
    e[len].w = w;
    head[u] = len;
}

int cnt[maxn];
bool vis[maxn];

void Spfa(int u){
    queue<int> q;
    for(int i = 1; i <= n; i++)
        dis[i] = 0x3f3f3f3f;
    q.push(u);
    vis[u] = 1;
    dis[u] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop();
        vis[x] = 0;
        for(int i = head[x]; i; i = e[i].nex){
            int v = e[i].to;
            if(dis[v] > dis[x] + e[i].w){
                dis[v] = dis[x] + e[i].w;
                if(!vis[v]){
                    cnt[v]++;
                    if(cnt[v] >= n){
                        dis[n] = -1;
                        return ;
                    }
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

bool Cmp(node w, node p){
    return w.x == p.x ? w.y < p.x : w.x < p.x;
}

int main(){
    cin >> n >> M >> K;
    /*for(int i = 1; i <= M; i++)
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].dis);
    for(int i = 1; i <= K; i++)
        scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].dis);
    sort(a + 1, a + 1 + M, Cmp);
    sort(b + 1, b + 1 + K, Cmp);*/
    int u, v, w;
    for(int i = 1; i <= M; i++){
        scanf("%d %d %d", &u, &v, &w);
        Add(u, v, w);
    }
    for(int i = 1; i <= K; i++){
        scanf("%d %d %d", &u, &v, &w);
        Add(v, u, -w);
    }
    for(int i = 1; i <= n; i++){
        Add(0, i, 0);
    }
    Spfa(0);
    if(dis[n] == -1){
        printf("-1n");
        return 0;
    }
    Spfa(1);
    if(dis[n] == 0x3f3f3f3f){
        printf("-2n");
        return 0;
    }
    printf("%dn", dis[n]);
    return 0;
}

狡猾的商人

我已经懒得粘题了qwq，传送门：https://www.luogu.com.cn/problem/P2294

这道题要用到一点前缀和的思想qwq，将(U->V=C)理解为(sum[V]-sum[U-1] geq C) && (sum[U-1]-sum[V] geq C)，然后就是最长路板子了qwq

记得图不一定连通，最后记得每个点都要跑一下。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define ll long long
#define inf 9999997
const int maxn = 100000 + 10;
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

struct edge{
    int nex, to, w;
}e[maxn << 2];

int n, m;
int head[maxn], len = 0;
int dis[maxn], cnt[maxn];
bool vis[maxn];

void Add(int u, int v, int w){
    e[++len].to = v;
    e[len].nex = head[u];
    e[len].w = w;
    head[u] = len;
}

bool Spfa(int s){
    queue<int> q;
    for(int i = 1; i <= n; i++) dis[i] = -inf;
    q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        cnt[u]++;
        if(cnt[u] >= n) return 0;
        for(int i = head[u]; i; i = e[i].nex){
            int v = e[i].to;
            if(dis[v] < dis[u] + e[i].w){
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}

void Init(){
    memset(head, 0, sizeof head);
    memset(vis, 0, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    len = 0;
}

int main(){
    int t = read();
    while(t--){
        Init(); 
        n = read(), m = read();
        int u, v, w;
        for(int i = 1; i <= m; i++){
            u = read(), v = read(), w = read();
            Add(v, u - 1, -w);
            Add(u - 1, v, w);
        }
        int flag = 1;
        for(int i = 0; i <= n; i++){
            if(!cnt[i]){
                if(!Spfa(i)){
                    flag = 0;
                    break;
                }
            }
        }
        if(flag) cout << "true" << endl;
        else cout << "false" << endl;
    }
    return 0;
}

小K的农场

传送门：https://www.luogu.com.cn/problem/P1993

比前面的题都要裸的题qwq，直接看代码吧

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define ll long long
const int maxn = 10000 + 10;
inline int read(){
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

struct edge{
    int nex, to, w;
}e[maxn << 2];

int n, m;
int head[maxn], len = 0;
int dis[maxn], cnt[maxn];
bool vis[maxn];

void Add(int u, int v, int w){
    e[++len].to = v;
    e[len].nex = head[u];
    e[len].w = w;
    head[u] = len;
}

void Spfa(int u){
    queue<int> q;
    for(int i = 1; i <= n; i++)
        dis[i] = 0x3f3f3f3f;
    dis[u] = 0;
    vis[u] = 1;
    q.push(u);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = head[x]; i; i = e[i].nex){
            int v = e[i].to;
            if(dis[v] > dis[x] + e[i].w){
                dis[v] = dis[x] + e[i].w;
                if(!vis[v]){
                    if(++cnt[v] >= n){printf("Non"); return ;}
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    printf("Yesn");
    return ;
}

int main(){
    n = read(), m = read();
    int x, a, b, c;
    for(int i = 1; i <= m; i++){
        x = read();
        if(x == 1){
            a = read(); b = read(); c = read();
            Add(a, b, -c);
        }
        else if(x == 2){
            a = read(); b = read(); c = read();
            Add(b, a, c);
        }
        else{
            a = read(); b = read();
            Add(a, b, 0), Add(b, a, 0);
        }
    }
    for(int i = 1; i <= n; i++) Add(0 , i, 0);
    Spfa(0);
    return 0;
}

原文链接: https://www.cnblogs.com/Zfio/p/13332732.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    差分约束的几道简单例题(糖果，layout，狡猾的商人，小k的农场）

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367660

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午5:54
下一篇 2023年3月2日 下午5:54

相关推荐