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