DFS，向上负边，向下正边，注意检查组成的环满不满足条件。数据量不大，O(NP)也过了。

#include <iostream>

using namespace std;

typedef struct
{
    int h,l,d;
}edge;

edge e[500];
int high[501]={0};
bool vis[501]={0};
int n,p;
bool check=true;

void dfs(int x)
{
    if(!vis[x])
    {
        vis[x]=true;
        int i;
        for(i=0;i<p;i++)
        {
            if(e[i].h==x)
            {
                if(vis[e[i].l])
                {
                    check=check&&(high[e[i].l]==high[x]+e[i].d);
                }
                else
                {
                    high[e[i].l]=high[x]+e[i].d;
                    dfs(e[i].l);
                }
            }
            if(e[i].l==x)
            {
                if(vis[e[i].h])
                {
                    check=check&&(high[e[i].h]==high[x]-e[i].d);
                }
                else
                {
                    high[e[i].h]=high[x]-e[i].d;
                    dfs(e[i].h);
                }
            }
        }
    }
}

int main()
{
    int i;
    cin>>n>>p;
    for(i=0;i<p;i++)
    {
        cin>>e[i].h>>e[i].l>>e[i].d;
    }
    dfs(1);
    if(!check)
    {
        cout<<-1<<endl;
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    int hist=0;
    for(i=1;i<=n;i++)
    {
        hist=min(hist,high[i]);
    }
    if(hist<0)
    {
        for(i=1;i<=n;i++)
        {
            high[i]-=hist;
        }
    }
    for(i=1;i<=n;i++)
    {
        cout<<high[i]<<endl;
    }
    return 0;
}

U41君也来啦！

var
n,m,x,y,z,k,i,j:longint;
a,b,a1:array [0..501,0..501] of longint;
ok:boolean;
begin
readln(n,m);
filldword(a,sizeof(a) div 3,maxint);
for i:=1 to m do
begin
readln(x,y,z);
a[y,x]:=-z;a[x,y]:=z;
b[y,x]:=1;b[x,y]:=1;
end;

a1:=a;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if (i<>j) and (j<>k) and (k<>i) then
begin
b[i,j]:=b[i,j] or (b[i,k] and b[k,j]);
if (a[i,k]<>maxint) and (a[k,j]<>maxint)then
a[i,j]:=a[i,k]+a[k,j];
end;

for i:=1 to n do
for j:=1 to n do
if (a[i,j]<>a1[i,j]) and (a1[i,j]<>maxint) then begin writeln(-1);exit;end;
for i:=1 to n do
begin
ok:=true;
for j:=1 to n do if (a[i,j]<=0) and (j<>i) then begin ok:=false;break;end;
if ok then
begin
a[i,i]:=0;
for j:=1 to n do writeln(abs(a[i,j]));
exit;
end;
end;
end.

SPFA秒杀
var n,p,i,j,x,y,z,min:longint;
f,t:array[0..501,0..501] of longint;
q:array[0..100001] of longint;
v:array[0..100001] of boolean;
d,times:array[0..501] of longint;
flag:boolean;
procedure spfa;
var i,x,head,tail:longint;
begin
fillchar(q,sizeof(q),0);
head:=0; tail:=1;
fillchar(v,sizeof(v),false);
for i:=1 to n do d[i]:=maxlongint div 3;
q[1]:=1; v[1]:=true; d[1]:=0;
while head<>tail do
begin
head:=head+1; x:=q[head]; v[x]:=false;
for i:=1 to n do
if (t[x,i]=1)and(d[x]+f[x,i]<d[i]) then
begin
d[i]:=d[x]+f[x,i];
inc(times[i]);
if times[i]>=2 then
begin
writeln('-1');
halt;
end;
if not(v[i]) then
begin
tail:=tail+1;
q[tail]:=i;
v[i]:=true;
end;
end;
end;
end;
begin
readln(n,p);
for i:=1 to p do
begin
readln(x,y,z);
f[x,y]:=z; f[y,x]:=-z;
t[x,y]:=1; t[y,x]:=1;
end;
spfa; flag:=true;
min:=maxlongint div 3;
for i:=1 to n do
begin
if min>d[i] then min:=d[i];
if d[i]=maxlongint div 3 then flag:=false;
end;
if not flag then
begin
writeln('-1');
halt;
end;
for i:=1 to n do d[i]:=d[i]-min;
for i:=1 to n do writeln(d[i]);
end.

并查集
A是B的双亲就表示A的位置比B的高，对于每个节点保存当前到双亲节点的距离（为正值），这样在并查集的树中，根节点与一个孩子的孩子的孩子.....的孩子的距离就可以在路径压缩的过程中计算出来：
对于两个不同集合的合并，由于在找集合的过程中使用了find函数，所以相关节点一定直接和集合树的根节点连接。设现在要连接的节点是a、b，它们的根节点分别是roota和rootb, a与b的距离为c, a在b的上面。集合的合并是集合根节点之间的连接，所以需要计算出根节点之间的距离P，b到roota的距离应为d[a]+c, b到rootb的距离为d[b] ,假设rootb成为roota的孩子，着P+d[b]=d[a]+c => P=d[a]+c-d[b].若P为负，则roota应成为roota的孩子，距离为P的绝对值。
//转载于http://www.cnblogs.com/wuminye/p/3182467.html
c++
#include<iostream>
#include<cstdio>
#define maxn 505
using namespace std;
int p[maxn],v[maxn],N,M;
int find(int x){
int t=p[x];
if(t==x) return x;
v[x]+=v[t];
return p[x]=find(t);
}
int merg(int x,int y,int l){
int fx=find(x),fy=find(y),d;
d=v[x]+l-v[y];
if(fx!=fy){
if(d>=0) p[fy]=fx, v[fy]=d;
else p[fx]=fy, v[fx]=-d;
}
else if(v[x]+l != v[y]) return -1;
return 1;
}
int main(){
int a,b,c,tmp;
for(int i=0;i<=maxn-2;i++) v[i]=0, p[i]=i;
scanf("%d%d",&M,&N);
for(int i=0;i<N;i++){
scanf("%d%d%d",&a,&b,&c);
if(merg(a,b,c)==-1){printf("-1\n"); return 0;}
}
for(int i=1;i<=M;i++) find(i);
for(int i=1;i<=M;i++) printf("%d\n",v[i]);
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 560 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 556 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 560 KiB, score = 10

program a03;
type
re=^pp;
pp=record
a,b:longint;
d:re;
end;
var
i,j,k,l,n,m,g,h:longint;
pa:array[0..1000]of re;
dis,dui,diss:array[0..1000]of longint;
vis:array[0..1000]of boolean;

procedure he(x,y,z:longint);
var
p:re;
begin
p:=pa[x];
new(pa[x]);
pa[x]^.a:=y;
pa[x]^.b:=z;
pa[x]^.d:=p;
end;

procedure spfa(x:longint);
var
i,k,l,r:longint; p:re;
begin
for i:=1 to n do
begin
dis[i]:=maxlongint div 3;
vis[i]:=false;
end;
vis[x]:=true; dis[x]:=0;
l:=0; r:=1; dui[r]:=x;
while l<r do
begin
if l>1000 then begin writeln(-1); halt; end;
inc(l);
k:=dui[l];
p:=pa[k];
while p<>nil do
begin
if dis[p^.a]>dis[k]+p^.b then
begin
dis[p^.a]:=dis[k]+p^.b;
if vis[p^.a]=false then
begin
vis[p^.a]:=true;
inc(r);
dui[r]:=p^.a;
end;
end;
p:=p^.d;
end;
vis[k]:=false;
end;
end;

begin
readln(n,m);
for i:=1 to m do
begin
readln(k,l,g);
he(k,l,g);
he(l,k,-g);
end;
spfa(1);
k:=maxlongint; l:=0;
for i:=1 to n do
if dis[i]<k then
begin
k:=dis[i];
l:=i;
end;

for i:=1 to n do
if i=l then
writeln(0) else
writeln(dis[i]-dis[l]);
end.

上->下正权边
下->上负权边
即可
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAXN 5000
#define INF 10000000
int n,p,highest,ans;
int f[MAXN],dis[505][MAXN],rdis[505][MAXN];
struct Node
{
int a,b,w;
}road[MAXN];
int cmp(Node x,Node y)
{
return x.a<y.a;
}
void init()
{
int i,ri1,ri2,li;
scanf("%d %d",&n,&p);
for(i=1;i<=p;i++)
{
scanf("%d %d %d",&ri1,&ri2,&li);
road[2*i-1].a=ri1; road[2*i].a=ri2;
road[2*i-1].b=ri2; road[2*i].b=ri1;
road[2*i-1].w=li; road[2*i].w=-li;
}
sort(road+1,road+2*p+1,cmp);
for(i=1;i<=2*p;i++) if(!f[road[i].a]) f[road[i].a]=i;
f[n+1]=2*p+1;
for(i=n;i>=1;i--) if(!f[i]) f[i]=f[i+1];
}
int spfa(int s)
{
int q[MAXN],v[MAXN];
int maxn,h,t,i,x,y;
for(i=1;i<=n;i++)
{
v[i]=0;
dis[s][i]=INF;
}
dis[s][s]=0;
h=0;
t=1;
q[t]=s;
v[s]=1;
while(h!=t)
{
h=(h+1)%(n+1);
x=q[h];
v[x]=0;
for(i=f[x];i<f[x+1];i++)
{
y=road[i].b;
if(dis[s][y]!=INF && dis[s][x]+road[i].w!=dis[s][y]) return -1;
if(dis[s][x]+road[i].w<dis[s][y])
{
dis[s][y]=dis[s][x]+road[i].w;
if(!v[y])
{
t=(t+1)%(n+1);
q[t]=y;
v[y]=1;
}
}
}
}
for(i=1;i<=n;i++) if(dis[s][i]<0) return 0;
return 1;
}
void work()
{
int i,t;
ans=0;
for(i=1;i<=n;i++)
{
t=spfa(i);
if(t==-1)
{
printf("-1\n");
return;
}
else if(t)
{
highest=i;
break;
}
}
//cout<<highest<<endl;
for(i=1;i<=n;i++) printf("%d\n",dis[highest][i]);
}
int main()
{
init();
work();
return 0;
}

感觉这题分类弄错了。\(O(n+m)\) 的搜索即可完成任务。因为数据量小所以写了个\(O(n^2)\)的也能秒杀。
方法：若 u 和 v 通过一条长为 L 的线连在一起且 u 在 v 上方，则连边 u->v、v->u，边权分别为 L 和 -L。设数组 height，令 height[i] 代表 i 号珍珠的高度，越靠上值越小。然后假定 height[1] = 0，从 1 号点开始搜索，把所有点遍历一次并得到每个点的 height ，若有后向边则判断是否合法。跑完搜索后，height 数组存储的是每个点**相对于 1 号点**的高度。根据题目要求，需要令最高点高度为零。所以只需找出 height 数组的最小值 min，然后把每个点的高度减去 min 即可。

编译成功

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(6,28) Note: Local variable "k" is assigned but never used
Linking foo.exe
82 lines compiled, 0.0 sec, 28160 bytes code, 1268 bytes data
1 note(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 824 KiB, score = 10
Accepted, time = 0 ms, mem = 828 KiB, score = 100
返回代码界面 | 关闭
program p1540;
type tnode=record
long,next,go:longint;
end;

var n,m,x,y,z,i,etree,temp,k:longint;
dis,h,change:array [0..505] of longint;
exist:array [0..505] of boolean;
team:array [0..1050] of longint;
e:array [0..1050] of tnode;

procedure ins(a,b,c:longint);
begin
inc(etree);
e[etree].long:=c;
e[etree].next:=h[a];
e[etree].go:=b;
h[a]:=etree;
end;

procedure print;
begin
writeln(-1);
halt;
end;

procedure spfa;
var head,tail,f:longint;
begin
head:=0; tail:=1; team[1]:=1; exist[1]:=true; dis[1]:=0;
while head<tail do
begin
inc(head); head:=((head-1) mod 1001)+1;
f:=h[team[head]]; exist[team[head]]:=false;
while f<>0 do
begin
if dis[e[f].go]>dis[team[head]]+e[f].long then
begin
dis[e[f].go]:=dis[team[head]]+e[f].long;
inc(change[e[f].go]); //important
if change[e[f].go]>=2 then print; //important
if not exist[e[f].go] then
begin
inc(tail); tail:=((tail-1) mod 1001)+1;
team[tail]:=e[f].go;
exist[e[f].go]:=true;
end;
end;
f:=e[f].next;
end;
end;
end;

begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y,z);
ins(x,y,z);
ins(y,x,-z);
end;

for i:=1 to n do
begin
exist[i]:=false;
dis[i]:=maxlongint div 3;
end;

spfa;

temp:=maxlongint;

for i:=1 to n do
if dis[i]<temp then
begin
temp:=dis[i];
k:=i;
end;

for i:=1 to n do writeln(dis[i]-temp);
end.

想上为负，向下为正，bfs求1号珍珠到每个珍珠的距离(spfa也可以)，找出最小距离，就是最上面的那颗珍珠,设其为k.
那么其他珍珠i到珍珠k的距离为:d[i]-d[k]

差分约束系统比较好写吧。。
记得要建负权边。

设f[i]表示i的位置
定义f[x[1]]=5000
那么f[x[2]]=f[X[1]]+l[1]
然后每次找到其中有一个f知道的条件进行处理
若找不到或矛盾则无解
答案就是f[i]-min(f[i])

想了半个小时，弱弱地用递推过了……
var
dis,mark,max,i,j,k,l,m,n,u:longint;
map,a:array[0..500,0..500] of longint;
h:array[0..10000] of longint;
b:array[0..500] of boolean;
bo:boolean;

begin
max:=-maxlongint;
readln(n,m);
for i:=1 to m do
begin
readln(l,k,u);
map[l,k]:=u;
map[k,l]:=-u;
inc(a[l,0]);
a[l,a[l,0]]:=k;
inc(a[k,0]);
a[k,a[k,0]]:=l;
end;
b[1]:=true;
h[1]:=0;
repeat
bo:=true;
for i:=1 to n do
if b[i] then begin
for j:=1 to a[i,0] do
if not b[a[i,j]] then
begin
h[a[i,j]]:=h[i]-map[i,a[i,j]];
b[a[i,j]]:=true;
bo:=false;
if h[a[i,j]]>max then
begin
mark:=a[i,j];
max:=h[a[i,j]];
end;
end else
begin
l:=h[i]-map[i,a[i,j]];
if h[a[i,j]]<>l then
begin
writeln('-1');
halt;
end;
end;
end;
until bo;
dis:=h[mark];
for i:=1 to n do
writeln(dis-h[i]);
end.

floyed 0.00s 全部秒过=-=

明显是模拟啊。。。

一次过。。

说说无解的条件吧：

1.p

floyed能oms？怎么可能，最后一个点floyed应该会超时的

　　用并查集的同学注意下，两点间构正边。

通过 100人

哈哈...庆祝一下...

注意一个问题，就是在dfs时：

if (h[a]

bfs...就对付这数据了

可是 请教大牛们 用并查集的话 要怎么做呢？或者说要合并两个集的时候怎么处理高度

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

膜拜雪牛！