828
poj 1201/ZOJ 1508 Intervals 差分約束
典型差分約束，注意一點是可以不把與前後相連的固定邊加到圖中，直接spfa時判斷即可，這樣可以節省很多時間空間
差分約束的關鍵就在於要寫清楚不等式
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int W[50005],U[50005],next[50005];
int first[50005],Dis[50005];
int cnt;
void add(int v,int u,int w)
{
next[cnt]=first[v];
first[v]=cnt;
U[cnt]=u;
W[cnt]=w;
cnt++;
}
queue<int> q;
bool inq[50005];
void insert(int u,int v,int w)
{
if(Dis[u]>(w=Dis[v]+w))
{
Dis[u]=w;
if(!inq[u])
{
inq[u]=1;
q.push(u);
}
}
}
int spfa(int b,int e)
{
memset(inq,0,sizeof(inq));
memset(Dis,63,sizeof(Dis));
Dis[b]=0;
q.push(b);
int i,v,u,t;
while(!q.empty())
{
v=q.front();q.pop();
inq[v]=0;
for(i=first[v];~i;i=next[i]) //標準spfa
insert(U[i],v,W[i]);
if(v-1>=e)insert(v-1,v,0); //後麵的邊
if(v+1<=b)insert(v+1,v,1);//前麵的邊
}
return Dis[e];
}
int main()
{
int n;
while(~scanf("%d",&n))
{
cnt=0;
memset(first,-1,sizeof(first));
int i,v,u,w,b=INF,e=-1;
for(i=0;i<n;i++)
{
scanf("%d%d%d",&v,&u,&w);
v--;
add(u,v,-w);
b=min(b,v);
e=max(e,u);
}
printf("%d\n",-spfa(e,b));
}
}
最後更新：2017-04-03 18:51:58