43 条题解
-
0curimit LV 10 @ 2009-05-16 17:52:21
哦,对的。
-
-12017-09-29 19:43:22@
吉儿小朋友,你会分我一点钱吗?
月亮之眼价值连城吧……
我帮你修好了……
记得给钱啊……
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;
} -
-12016-08-16 11:25:42@
###U43君又来水题解啦!
pascal
var
r1,r2,l,h:array[0..501]of longint;
flag:array[0..501]of boolean;//记录有没有被搜到
i,n,p,min:longint;
procedure search(step:longint);
var
i,x,tall:longint;
begin
flag[step]:=true;
for i:=1 to p do
if (r1[i]=step)or(r2[i]=step) then begin
x:=r1[i]+r2[i]-step;
if r1[i]=step then tall:=h[step]+l[i] else tall:=h[step]-l[i];计算另一个珠子的高度
if (flag[x]=true)and(h[x]<>tall) then begin//如果两个珠子间连接了不止一条线,那么一定无解,原因自己思考
write(-1);
halt;
end;
h[x]:=tall;
if not flag[x] then search(x);//搜下一个没有被搜到的珠子
end;
end;
begin
readln(n,p);
for i:=1 to p do readln(r1[i],r2[i],l[i]);
h[1]:=0;
search(1);
min:=maxlongint;
for i:=1 to n do
if h[i]<min then min:=h[i];
if min<0 then
for i:=1 to n do h[i]:=h[i]-min;//防止珠子掉到海平面下面去了
for i:=1 to n do writeln(h[i]);
end.
其实用并查集也可以的。
下面是搜索的评分:
测试数据 #0: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 816 KiB, score = 10
Accepted, time = 0 ms, mem = 820 KiB, score = 100
#搜索是可以0ms通过的!!!!
###输出-1能得20分,也是0ms,但是我的搜索0ms满分呵呵呵~