提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

POJ1201基础差分约束

基础 约束 差分
2023-09-11 14:14:00 时间
题意：
      有一条直线，直线上做多有50000个点，然后给你组关系 a b c表明a-b之间最少有c个点，问直线上最少多少个点。


思路：
       a-b最少有c个点可以想象a到b+1的距离是大于等于c的，还有一个隐含条件就是
0<=S[i] - S[i-1]<=1,差分约束的题目记住找隐含条件很重要，这样也就是一共三个条件，建边求最上路，记住查分约束求短要用最长路，求最长要用最短路，最长路的建边是
a      ,b       c
S[i-1] ,S[i]    0

S[i]   ,S[i-1]  -1


#include<queue>
#include<stdio.h>
#include<string.h>

#define N_node 50000 + 100
#define N_edge 150000 + 10000
#define INF 1000000000

using namespace std;

typedef struct
{
    int to ,cost ,next;
}STAR;

STAR E[N_edge];
int list[N_node] ,tot;
int s_x[N_node] ,mark[N_node] ,mkc[N_node];

void add(int a ,int b ,int c)
{
    E[++tot].to = b;
    E[tot].cost = c;
    E[tot].next = list[a];
    list[a] = tot;
}

bool SPFA(int s ,int n)
{
    for(int i = 0 ;i <= n ;i ++)
    s_x[i] = -INF ,mark[i] = mkc[i] = 0;
    queue<int>q;
    q.push(s);
    mark[s] = mkc[s] = 1;
    s_x[s] = 0;
    while(!q.empty())
    {
        int xin ,tou;
        tou = q.front();
        q.pop();
        mark[tou] = 0;
        for(int k = list[tou] ;k ;k = E[k].next)
        {
            xin = E[k].to;
            if(s_x[xin] < s_x[tou] + E[k].cost)
            {
                s_x[xin] = s_x[tou] + E[k].cost;
                if(!mark[xin])
                {
                    mark[xin] = 1;
                    if(++mkc[xin] > n) return 0;
                    q.push(xin);
                }
            }
        }
    }
    return 1;
}

int main ()
{
    int t ,i ,a ,b ,c ,m ,min ,max;
    while(~scanf("%d" ,&m))
    {
        memset(list ,0 ,sizeof(list));
        tot = 1;
        min = INF ,max = 0;
        for(i = 1 ;i <= m ;i ++)
        {
            scanf("%d %d %d" ,&a ,&b ,&c);
            add(a ,++b ,c);
            if(min > a) min = a;
            if(max < b) max = b;
        }
        for(i = min + 1 ;i <= max ;i ++)
        {
            add(i-1 ,i ,0);
            add(i ,i-1 ,-1);
        }
        SPFA(min ,max);
        printf("%d\n" ,s_x[max]);
    }
    return 0;
}


相关文章