差分约束系统

不是很想单独开一个版面,可是觉得图论基础快要撑爆了还是多开一个吧(=゚ω゚)=

偶然发现的学长的资料:http://972169909-qq-com.iteye.com/blog/1185527
http://whiteath.weebly.com/blog/2
http://blog.csdn.net/morgan_xww/article/details/6359229

结论:

  • a-b<=c,建边b->a,权重c,求最短路,得到满足条件的最大值
  • a-b>=c,建边b->a,权重c,求最长路,得到满足条件的最小值
  • d[]没更新则为任意解

HDU1384
练手题,没想到触及到自己的知识华点了
对于线段,最好使用左闭右开,如{i}则用结点i i+1,[L,R]用结点L R+1来表示可避免边界条件BUG
最长路并不好用,以后一致使用最短路表示方法来表示不等式,结果可能取反
起点用权重为0的边连接其它边是为了联通,虽然在这题上并无卵用
解题思路是区间[L,R+1)>=C,既(R+1,L]<=-C,最短路中可表示为add(L,R+1,-C)
r不确定边界的话取大一点应该没关系?这题只要保证r覆盖到的地方有01约束就AC了

网上流行的写法思路是这样的,看着没差但好像和自己认为的区间表示意义相差甚远:
Sbi - Sai >= ci
Si - Si-1 >= 0
Si-1 - Si >= -1

        int r=0;
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d",&u,&v,&w);
            if(u>v)swap(u,v);
            add(u,v+1,-w);r=max(r,max(u,v+1));
        }
        for(int i = 0; i < r; i++){
            add(i,i+1,0);add(i+1,i,1);
        }
        for(int i = 1; i <= r; i++){
            add(0,i,0);
        } 
        spfa(0);//SSSP版本
        printf("%d\n",-d[r]);

HDU3592

int main(){
    int T; scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d%d",&n,&x,&y);
        for(int i = 0; i < x; i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        for(int i = 0; i < y; i++){
            scanf("%d%d%d",&u,&v,&w);
            add(v,u,-w);
        }
        for(int i = 2; i <= n; i++){
            add(1,i,0);
        }
        if(!spfa(1)){
            if(d[n]!=oo) printf("%d\n",d[n]);
            else printf("-2\n");
        }
        else printf("-1\n"); 
    }
    return 0;
}

HDU1534
隐式图

int main(){
    int kase=0;
    while(scanf("%d",&n)!=EOF){
        if(n==0) break;
        init(); 
        for(int i = 1; i <= n; i++) {scanf("%d",&w[i]);add(0,i,-w[i]);}//
        while(scanf("%s",str)){
            if(str[0]=='#')break;
            scanf("%d%d",&u,&v);
            if(strcmp(str,"FAS")==0){//d[u]+w[u]>=d[v]  d[v]<=d[u]+w[u]
                add(u,v,w[u]); 
            }
            else if(strcmp(str,"FAF")==0){//d[u]+w[u]>=d[v]+w[v]  d[v]<=d[u]+w[u]-w[v]
                add(u,v,w[u]-w[v]);
            }
            else if(strcmp(str,"SAF")==0){//d[u]>=d[v]+w[v]  d[v]<=d[u]-w[v]
                add(u,v,-w[v]);
            }
            else{//SAS d[u]>=d[v] d[v]<=d[u]
                add(u,v,0);
            }
        }
        printf("Case %d:\n",++kase);
        if(spfa(0)) printf("impossible\n");
        else{
            int mn=oo;
            for(int i = 1; i <= n; i++) mn=min(mn,d[i]);
            for(int i = 1; i <= n; i++) printf("%d %d\n",i,d[i]-mn);//
        }
        printf("\n");
    }
    return 0; 
}

标签: 算法, 学习

添加新评论