Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

【差分约束小题】

Posted by 843040610 at 2017-03-10 11:11:20 on Problem 1201
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator