| ||||||||||
| 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<algorithm>
#include<queue>
#include<cstring>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define fo(i,a,x) for(int i=a[x];i;i=e[i].next)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;queue<int>q;const int N=50010;
struct E{int v,next,w;}e[N*4];bool inq[N];
int n,a,b,c,k=1,head[N],start=N*10,end=-1,dis[N];
void ADD(int u,int v,int w){e[k]=(E){v,head[u],w};head[u]=k++;}
int main()
{
____scanf("%d",&n);go(i,1,n){scanf("%d%d%d",&a,&b,&c);
____ADD(a,b+1,c);start=min(start,a);end=max(end,b+1);}
____go(i,start,end-1){ADD(i,i+1,0);ADD(i+1,i,-1);dis[i]=-111111111;
____}dis[end]=-111111111;dis[start]=0;q.push(start);
____while(!q.empty()){int u=q.front();q.pop();inq[u]=0;fo(i,head,u)
____{int v=e[i].v;if(dis[u]+e[i].w>dis[v])
____{dis[v]=dis[u]+e[i].w;if(!inq[v])q.push(v),inq[v]=1;}
____}}printf("%d\n",dis[end]);return 0;
}//Paul_Guderian
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator