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