1
19
2016
0

【USACO2005 DecGold】【poj3169】【bsoj3558】【差分约束系统】Layout

3558 -- 【USACO 2005 December Gold】Layout

Description

Input

Output

Sample Input

4 2 1 1 3 10 2 4 20 2 3 3

Sample Output

27

Source

root

首先题目中的隐含条件是
d[i] <= d[i + 1] 
即d[i + 1] + 0 >= d[i]
 
然后对那ML个条件
d[y] - d[x] <= w -> d[x] + w >= d[y]
对那MD个条件
d[y] - d[x] >= w -> d[y] + (-w) >= d[x] 
 
然后呢就可以加边了。
对于一个不等式 d[u] + w >= d[v] 我们可以加边(u, v , w)
这是由于在一个图里,从s出发,到各个顶点的v最短距离为d[v],那么对一个边(u, v, w) 必然有d[u] + w >= d[v]
 
我的代码:(18:05-18:32,1A)
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define inf 1<<30
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
using namespace std;
const int M=15000,N=1500;
struct edge{
	int go,next,w;
}e[M];
int n,s,ml,md,d[N],head[N],cnt[N],tot=0;
bool inq[N];
inline void addedge(int x,int y,int z)
{e[++tot]=(edge){y,head[x],z};head[x]=tot;}
#include<queue>
queue<int> q;
inline bool spfa()
{
	s=1;
	F(i,1,n) d[i]=inf;
	d[s]=0;
	memset(inq,false,sizeof(inq));
	memset(cnt,0,sizeof(cnt));
	q.push(s);
	inq[s]=true;
	while(!q.empty()){
		int x=q.front();q.pop();
		inq[x]=false;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].go;
			if(d[y]>d[x]+e[i].w){
				d[y]=d[x]+e[i].w;
				if(!inq[y]){
					q.push(y);
					inq[y]=true;
					if(++cnt[y]>n)
						return false;
				}
			}
		}
	}
	return true;
}
int main()
{
	int a,b,c;
	scanf("%d%d%d",&n,&ml,&md);
	F(i,1,n) addedge(i+1,i,0);
	F(i,1,ml){
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);//a->b 权值为c
	}
	F(i,1,md){
		scanf("%d%d%d",&a,&b,&c);
		addedge(b,a,-c);//b->a 权值为-c
  }
  spfa();
  if(!spfa()) puts("-1");
  else if(d[n]==inf) puts("-2");
  else printf("%d\n",d[n]);
  return 0;
}

 

Category: 差分约束系统 | Tags: | Read Count: 189

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com