zoj 1508 poj 1201 Intervals

差分约束系统。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 55;

map<int, int> jz[maxn];
vector<int>ljb[maxn];
int dist[maxn],flag[maxn];
int mm, mx;

void spfa()
{
    int ii;
    queue<int>Q;
    memset(flag, 0, sizeof(flag));
    flag[mx] = 1; 
    for (ii = 0; ii <= mx; ii++) dist[ii] = ;
    dist[mx] = 0; Q.push(mx);
    while (!Q.empty())
    {
        int hh = Q.front(); Q.pop(); flag[hh] = 0;
        for (ii = 0; ii < ljb[hh].size(); ii++)
        {
            if (jz[hh][ljb[hh][ii]] != )
            {
                if (dist[hh] + jz[hh][ljb[hh][ii]] < dist[ljb[hh][ii]])
                {
                    dist[ljb[hh][ii]] = dist[hh] + jz[hh][ljb[hh][ii]];
                    if (flag[ljb[hh][ii]] == 0)
                    {
                        Q.push(ljb[hh][ii]);
                        flag[ljb[hh][ii]] = 1;                    
                    }
                }
            }
        }
        
    }
}

int main()
{
    int i, n, a, b, c;
    while (~scanf("%d", &n))
    {
        for (i = 0; i <= 50; i++) jz[i].clear();
        for (i = 0; i <= 50; i++) ljb[i].clear();
        mx = -, mm = ;
        for (i = 0; i < n; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            ljb[b].push_back(a - 1);
            jz[b][a - 1] = -c;
            if (a < mm) mm = a;
            if (b > mx) mx = b;
        }
        for (i = 1; i <= mx; i++)
        {
            ljb[i - 1].push_back(i);
            jz[i - 1][i] = 1;
            ljb[i].push_back(i - 1);
            jz[i][i - 1] = 0;
        }    
        spfa();
        printf("%d\n", dist[mx] - dist[mm - 1]);
    }
    return 0;
}  

 

更多相关文章
  •                                                                                               IntervalsTime Limit: 2MSMemory Limit: 65536KTotal Submis ...
  • 职务地址:POJ 1201   HDU 1384 依据题目意思.能够列出不等式例如以下: Sj-Si>=c; Si-S(i-1)>=0; S(i-1)-Si>=-1; 然后用最短路spfa来解决这个不等式.用max来当源点,0为终点.终于的-d[0]就是答案. 代码例如以下: #i ...
  •   // 思路 : // 图建好后 剩下的就和上一篇的 火烧连营那题一样了 求得解都是一样的 // 所以稍微改了就过了 // 最下面还有更快的算法 速度是这个算法的2倍#include <iostream> #include <map> #include <algori ...
  • zoj 1508 Intervals (差分约束)
    IntervalsTime Limit: 10 Seconds      Memory Limit: 32768 KB You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.Write a prog ...
  • http://poj.org/problem?id=1089 Intervals Time Limit: 1MS   Memory Limit: 10K Total Submissions: 7214   Accepted: 2862 Description There is given the s ...
  • poj 3680 Intervals(費用流)
    http://poj.org/problem?id=3680 巧妙的构图. 题目:给定N个区间(ai,bi)权值wi,求最大权和且每个点最多覆盖K次. 构图:将区间端点离散化,将第i个点连第i+1个点花费为0,容量为INF,即addedge(i,i+1,0,INF)(可用来跳过一些区间); 再处理N
  • 最小生成树,用了Kruskal算法.POJ上C++能过,G++不能过... 算出每两个圆心之间的距离,如果距离小于两半径之和,那么这两个圆心之间的距离直接等于0,否则等于距离-R[i]-R[j].   #includ
  • 差分約束(poj 1201
    这里简要记一下差分约束. 所谓差分约束,指的是由a-b>=c这种不等式组组成的约束系统.一
一周排行