2019最新【幸运飞艇赛车规律公式】567码计划技巧公式实践技巧稳赢不输9

# 差分约束系统

 

目录

• 差分约束系统2904628156
  
  • 水题（bzoj 1731）
  • 最短路算法
  • 差分约束系统
  • 差分约束详解及金典模型

差分约束系统

---

水题（bzoj 1731）

• 裸差分约束，n头牛【1，n】，(ml条这样的信息)对于两头有好感的牛距离不超过w,(md条这样的信息)对于两头有反感的牛距离至少w,且多头牛可以共享一个点，求最后一头牛和第一头牛距离最大是多少

• 按要求建图，使用bellman或者spfa

/*
4 2 1
1 3 10
2 4 20
2 3 3

Sample Output
27
四只牛分别在0，7，10，27.

*/
#include <bits/stdc++.h>
using namespace std;
struct edge{
    int from,cost,to;
}e[100000];
int k=0;
void build(int x,int y,int w){
    //e[k].from=x,e[k].to=y,e[k].cost=w;
    e[k]=edge{x,w,y};
    k++;
}
int d[1005];
int n;
const int inf=0x7f7f7f7f;
bool bellman(int s){
    memset(d,0x7f,sizeof(d));
    d[s]=0;
    bool update=0;

    for(int i=1;i<=n;i++){
        update=0;

        for(int j=0;j<k;j++){
            edge& es=e[j];
            if(es.from!=inf&&d[es.from]+es.cost<d[es.to]){
                d[es.to]=d[es.from]+es.cost;
                update=1;
                if(i==n)return 0;
            }
        }
        if(!update)return 1;
    }
    return 1;
}
int main(){
    int ml,md;
    scanf("%d %d %d",&n,&ml,&md);
    int x,y,w;
    while(ml--){
        scanf("%d %d %d",&x,&y,&w);//y-x<=w;建有向边x->y,
        build(x,y,w);
    }
    while(md--