# 43 条题解

• @ 2019-05-07 19:05:12

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;
}
``````
• @ 2016-08-28 22:47:43

U41君也来啦！

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

• @ 2016-07-18 19:50:39

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;
begin
fillchar(q,sizeof(q),0);
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;
begin
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
for i:=1 to p do
begin
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.

• @ 2016-05-31 19:57:43

并查集
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

• @ 2015-10-13 20:53:55

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
for i:=1 to m do
begin
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.

• @ 2017-11-20 21:59:27

上->下正权边
下->上负权边
即可
#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;
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);
}
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++)
{
{
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;
}

• @ 2016-08-06 19:51:51

感觉这题分类弄错了。`\(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 即可。

• @ 2019-01-07 22:08:33

帮忙看看这个为什么第一组和最后一组数据一直是runtime error
#include<stdio.h>

struct Line
{
int r1,r2,l;
}line[10000];

int main()
{
int INF=100000000;
int max,i,j,h[10000]={0},pos,flag=0,flag1=0,t,m;
int n,p;
scanf("%d%d",&n,&p);
for(i=1;i<=n;i++)
{
h[i]=INF;
}
for(i=0;i<p;i++)
{
scanf("%d%d%d",&line[i].r1,&line[i].r2,&line[i].l);
}
h[1]=0;
max=0;
pos=1;

for(i=0;i<p;i++)
{
if(line[i].r1==1)
{
t=line[i].r2;
if(h[t]!=INF&&h[t]!=h[1]-line[i].l)
{
flag=1;
break;
}
h[t]=h[1]-line[i].l;
if(max<h[t])
{
max=h[t];
pos=t;
}
}
else if(line[i].r2==1)
{
t=line[i].r1;
if(h[t]!=INF&&h[t]!=h[1]+line[i].l)
{
flag=1;
break;
}
h[t]=h[1]+line[i].l;
if(max<h[t])
{
max=h[t];
pos=t;
}
}
}
if(flag==1)
{
printf("-1\n");
return 0;
}
for(j=2;j<=n;j++)
{
// flag=0;
for(i=0;i<p;i++)
{

t=line[i].r1;
m=line[i].r2;
if(h[t]!=INF&&h[m]!=INF&&h[m]!=h[t]-line[i].l)
{
printf("-1");
return;
}
if(h[m]==INF&&h[t]!=INF)
{
h[m]=h[t]-line[i].l;
if(max<h[m])
{
max=h[m];
pos=m;
}
}
else if(h[m]!=INF&&h[t]==INF)
{
h[t]=h[m]+line[i].l;
if(max<h[t])
{
max=h[t];
pos=t;
}
}
}
}
for(i=1;i<=n;i++)
{
if(h[i]==INF)
{
printf("-1");
return;
}
}
for(i=1;i<=n;i++)
{
h[i]=max-h[i];
printf("%d\n",h[i]);
}
return 0;
}

• @ 2016-05-22 21:39:57

编译成功

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
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;
begin
begin
while f<>0 do
begin
begin
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
for i:=1 to m do
begin
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.

• @ 2016-04-03 20:04:41

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

• @ 2015-03-17 15:39:57

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

• @ 2013-10-04 16:49:42

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

• @ 2013-10-05 10:16:43

缔结

• @ 2013-10-04 15:17:59

想了半个小时，弱弱地用递推过了……
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;
for i:=1 to m do
begin
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.

• @ 2013-10-05 10:16:16

好棒啊 大神啊 加我为好友吧

• @ 2012-10-25 12:32:52

floyed 0.00s 全部秒过=-=

• @ 2012-08-14 16:21:20

明显是模拟啊。。。

一次过。。

说说无解的条件吧：

1.p

• @ 2010-03-12 21:08:02

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

• @ 2009-11-03 20:26:42

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

• @ 2009-10-30 20:48:20

通过 100人

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

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

if (h[a]

• @ 2009-10-30 09:46:16

bfs...就对付这数据了

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

• @ 2009-10-28 20:06:54

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2009-10-05 21:55:41

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

膜拜雪牛！

ID
1540

5

1349

424

31%

1