| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
发帖纪念第一道差分约束!!!附代码!!#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#define inf 0x7FFFFFFF
#define M 500000
using namespace std;
int edge_num,minnum,maxnum,head[M],end[M],cost[M],nxt[M],n;
inline void Init(){
edge_num=0;
memset(head,-1,M);
}
inline void add_edge(int u,int v,int w){
end[edge_num]=v;
cost[edge_num]=w;
nxt[edge_num]=head[u];
head[u]=edge_num++;
}
int vis[M],d[M];
int spfa(){
memset(vis,0,maxnum+3);
for(int i=minnum;i<=maxnum;i++) d[i]=-inf;
queue<int> Q;int u;
Q.push(minnum),vis[minnum]=true,d[minnum]=0;
while(!Q.empty()){
u=Q.front(),Q.pop(),vis[u]=0;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=end[i];int w=cost[i];
if(d[u]+w>d[v]){
d[v]=d[u]+w;
if(!vis[v]){
Q.push(v),vis[v]=1;
}
}
}
}
return d[maxnum];
}
int main(){
scanf("%d",&n);
minnum=inf,maxnum=-inf;
Init();
while(n--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
minnum=min(minnum,u);
maxnum=max(maxnum,v+1);
add_edge(u,v+1,w);
}
for(int i=minnum;i<=maxnum;i++){
add_edge(i,i+1,0);
add_edge(i+1,i,-1);
}
printf("%d\n",spfa());
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator