Candies （POJ3159) 線性限制差分+堆優化Dijkstra 最短路專題

題目描述

During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had flymouse distribute them. All the kids loved candies very much and often compared the numbers of candies they got with others. A kid A could had the idea that though it might be the case that another kid B was better than him in some aspect and therefore had a reason for deserving more candies than he did, he should never get a certain number of candies fewer than B did no matter how many candies he actually got, otherwise he would feel dissatisfied and go to the head-teacher to complain about flymouse’s biased distribution.

snoopy shared class with flymouse at that time. flymouse always compared the number of his candies with that of snoopy’s. He wanted to make the difference between the numbers as large as possible while keeping every kid satisfied. Now he had just got another bag of candies from the head-teacher, what was the largest difference he could make out of it?

題目大意：有n個小朋友，給每個小朋友分糖果，給你m種關系，即輸入 a b c，意味着b孩子最多比a孩子的糖果數量多c，即x[ a ] - x[ b ] >=c，給你m種這些關系，問你第n個孩子最多比第1個孩子的糖果數量多多少。

思路：這一類問題可以差分限制算法解決。

          差分限制算法：如果一個系統由n個變量和m個限制條件組成，形成m個形如ai-aj≤k的不等式(i,j∈[1,n],k為常數),則稱其為差分            限制系統。

          過程：把每個不等式都化為形如  X [ i ] - X [ j ]<= a [ k ] 的形式，如 

        （1）方程給出：X[n-1]-X[0]>=T ,可以進行移項轉化為： X[0]-X[n-1]<=-T。

        （2）方程給出：X[n-1]-X[0]<T, 可以轉化為X[n-1]-X[0]<=T-1。

        （3）方程給出：X[n-1]-X[0]=T，可以轉化為X[n-1]-X[0]<=T&&X[n-1]-X[0]>=T，再利用（1）進行轉化即可

          最後進行建圖，即每個公式都可以變成 一條  j -> i  權值為a[k] 的有向邊。

          最後，如該題要求 X[ n ] - X[ 1 ] 的最大值，隻需要以 1 為源點，跑一邊最短路，在求與 點 n 的最短路即可。

          另外，由于該題資料較大，就需要采用 堆優化的Dijkstra。

代碼：

#include<bits/stdc++.h>

#define ll long long
#define ull unsigned long long 
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int NUM = 30005;
int n,m,len=1;
int head[NUM];
struct edge{
   int from,to,w;
}e[150005];   //邊數
struct s_node{
   int id,n_dis;
   s_node(int a,int b){id=a;n_dis=b;}
   bool operator < (const s_node &a) const
   {return n_dis>a.n_dis;}
};
void add(int u,int v,int w)
{ 
    e[len].from=v;
    e[len].w=w;
    e[len].to=head[u];
    head[u]=len++;
}
int Dijkstra(int s)
{
    int dis[NUM];
    bool vis[NUM];
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        vis[i]=0;
    }
    dis[s]=0;
    priority_queue<s_node>Q;
    Q.push(s_node(s,dis[s]));
    while(!Q.empty())
    {
        int u=Q.top().id;
        Q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].to){
            int v=e[i].from;
            //if(vis[v])continue;
            if(dis[v]>dis[u]+e[i].w){
               dis[v]=dis[u]+e[i].w;
               Q.push(s_node(v,dis[v]));
            }
        }
    }
    return dis[n];
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
       int a,b,c;
       scanf("%d %d %d",&a,&b,&c);
       add(a,b,c);
    }
    printf("%d",Dijkstra(1));
    return 0;
}