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 wocha at 2012-08-17 16:28:53 on Problem 1201
#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:
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