文档章节

【scoi 2011】糖果 差分约束

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 582
阅读 22
收藏 0

点击就送屠龙宝刀
简单的差分约束
其实差分约束这东西吧,日本白上讲的挺好的
就一句话
dis[from] + l[i].v <= dis[to](最长路性质)
然后看到不等式什么的往上套就是了
如下图……(字不好,见谅)
字好丑啊……好丑啊……丑啊……啊……
总之就是这样了
然后
差分约束的话不知道起点是谁
麻烦了
我的解决办法是建立超级源点(@网络流)
边权的话,保证不影响结果就是了
然后
跑什么路就看题了
他想最少就跑最长路,想最大就跑最短路

引用
比如给出三个不等式,b-a<=k1,c-b<=k2,c-a<=k3,求出c-a的最大值
由题b-a<=k1,c-b<=k2,得出c-a<=k1+k2,因此比较k1+k2和k3的大小,求出最小的就是c-a的最大值了

我习惯怎样都建正权
(负权好讨厌……)
还有啥来着……
差不多了吧

对了
顺带一提
差分约束东西,边表示的是满足条件,也就是说边是条件……(好晕)
总之就是这样了
上代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const long long MAXN = 100000 + 5;
const long long MAXM = 200000 + 5;
struct edge
{
    long long f,t,v;
}l[MAXM << 1];
long long first[MAXN],next[MAXM << 1],tot;
void init()
{
    memset(first,0xfff,sizeof(first));
    tot = 0;
    return;
}
void build(long long f,long long t,long long v)
{
    l[++tot] = (edge){f,t,v};
    next[tot] = first[f];
    first[f] = tot;
    return;
}
long long dis[MAXN],use[MAXN];
long long vis[MAXN];
deque <int> q;
long long n;
long long spfa_slf(long long s)
{
    memset(dis,0x80,sizeof(dis));
    memset(use,0,sizeof(use));
    q.push_back(s);
    use[s] = true;
    dis[s] = 0;
    q.push_back(0);
    while(!q.empty())
    {
        long long u = q.front();
        q.pop_front();
        use[u] = false;
        if(vis[u] > n)
            return -1;
        for(long long i = first[u];i != -1;i = next[i])
        {
            long long v = l[i].t;
            if(dis[v] < dis[u] + l[i].v)
            {
                dis[v] = dis[u] + l[i].v;
                if(!use[v])
                {
                    vis[v] ++;
                    dis[v] > dis[q.front()] ? q.push_front(v) : q.push_back(v);
                }
            }
        }
    }
    long long ans = 0;
    for(long long i = 1;i <= n;i ++)
        ans += dis[i];
    ans += n;
    return ans;
}
long long k,x,a,b;
int main()
{
    init();
    scanf("%lld %lld",&n,&k);
    for(long long i = 1;i <= k;i ++)
    {
        scanf("%lld %lld %lld",&x,&a,&b);
        switch(x)
        {
            case 1:build(a,b,0);build(b,a,0);break;
            case 2:build(a,b,1);break;
            case 3:build(b,a,0);break;
            case 4:build(b,a,1);break;
            case 5:build(a,b,0);break;
        }
    }
    for(long long i = n;i >= 1;i --)
        build(n + 1,i,0);
    spfa_slf(0);
    printf("%lld\n",spfa_slf(n + 1));
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
POJ 3159 Candies 【差分约束】

传送门 题意: 给定n个限制关系u v w表示u认为v的糖果数量最多比它多w个. 问在满足这些的条件下, 1与n的糖果数量最大的差是多少. 思路: 知道差分约束的很容易可以判断出这个是差分约束, 我们用...

Anxdada
2018/02/13
0
0
POJ ~ 3159 ~ Candies (Dijkstra + 优先队列 + 链式前向星 or 栈式SPFA)(差分约束)

推荐一片入门博客:夜深人静写算法(四) - 差分约束 个人感觉很有用的地方,暂存一下,备查: 4、最大值 => 最小值 然后,我们将问题进行一个简单的转化,将原先的"<="变成">=",转化后的不...

ZscDst
2018/01/31
0
0
Candies POJ - 3159

题目链接:https://vjudge.net/problem/POJ-3159 思路: 能看出是差分约束的题, 我们想假设一个人是 p(1),另一个人是p(2),他们之间糖果差为w, 那么需要满足的是 : p(2) - p(1) <= w, 为...

SSummerZzz
08/18
0
0
练手Android开发的糖果RSS阅读器 内置了开源中国的全部RSS订阅,欢迎提出修改意见!

练手Android开发的糖果RSS阅读器 内置了开源中国的全部RSS订阅 用它你可以订阅你喜欢的新闻,订阅你喜欢的名人博客,你也可以关注你身边亲友的博客。让获得资讯变得轻松便捷 发布地址及截图:...

Zee
2011/06/10
728
2
差分约束算法————洛谷P4878 [USACO05DEC] 布局

题目: 不难看出题意主要是给出ml+md个格式为xi-xj<=ak的不等式,xi-xj为i,j俩头牛的距离,要我们求x1-xn的最大值。 经过上下加减我们可以将这几个不等式化成x1-xn<=a1+a2+a3+a4+....+ak,在...

嘤嘤狂吠OVO
10/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

设计模式之建造者模式、模版方法

一、建造者模式 建造者模式:是将一个复杂的对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。 工厂类模式提供的是创建单个类的模式,而建造者模式则是将各种产品集中起来进...

codeobj
14分钟前
3
0
puppeteer踩坑记录

错误代码1: error while loading shared libraries: libXcomposite.so.1: cannot open shared 解决方案: 在项目Chrome所在的目录例如:/home/code/puppeteer/node_modules/puppeteer/.local......

JamesView
14分钟前
4
0
Dojo 样式简介

翻译自:https://github.com/dojo/framework/blob/master/docs/en/styling/introduction.md 介绍 Dojo 是基于 HTML 的技术,使用 CSS 为框架中的元素和用它开发的应用程序设置样式。 Dojo 鼓...

blocklang
14分钟前
5
0
装饰器

装饰器 装饰器:装饰器是一种特殊类型的声明,它能够被附加到类声明,方法,属性或参数上,可以修改类的行为。 通俗的讲装饰器就是一个方法,可以注入到类、方法、属性参数上来扩展类、属性、...

不负好时光
15分钟前
5
0
java值传递和引用传递

先写三个例子把。 1、这个例子很简单,估计都知道,是值类型,按照值类型传递,传递是副本。所以结果依旧是20。 static void change(int age) { age = 10;}public static void ma...

朝如青丝暮成雪
18分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部