|
|
Posted on 2010-08-02 19:12 Uriel 閱讀(444) 評(píng)論(0) 編輯 收藏 引用 所屬分類: POJ 、 數(shù)據(jù)結(jié)構(gòu)
題意：給出點(diǎn)數(shù)和邊數(shù) 已知每一條邊的起點(diǎn)終點(diǎn)編號(hào)和方向 幾個(gè)Query，每個(gè)Query求兩個(gè)編號(hào)的點(diǎn)在第 I 步之后的曼哈頓距離 思路：先將Query按操作步數(shù)的大小排序，從小到大 遍歷每個(gè)操作，執(zhí)行并集函數(shù)，然后如果這步有Query則對(duì)Query的兩個(gè)點(diǎn)執(zhí)行查集函數(shù)，如果在一個(gè)集合當(dāng)中，他們的曼哈頓距離即為他們的父親結(jié)點(diǎn)的曼哈頓距離，否則輸出-1 并集函數(shù)寫法：如果第x條邊(第x 步操作產(chǎn)生的)兩個(gè)端點(diǎn)不在同一集合，則合并，注意合并之后作為兒子的結(jié)點(diǎn)到父親結(jié)點(diǎn)的曼哈頓距離要有變化，要分邊的方向不同考慮，詳見代碼 查集函數(shù)注意x，y 相對(duì)距離的累加 這題G++始終過(guò)不了，開始以為是數(shù)組越界或是浮點(diǎn)誤差，但是都排除了，還懷疑是abs()的問題，手寫了ABS也不行。。有路過(guò)的大牛請(qǐng)不吝賜教~ 另外發(fā)現(xiàn)改手寫ABS()之后從172MS降到125MS，很神奇~~ 代碼如下：
 //Problem: 1984 User: Uriel
//Memory: 1352K Time: 125MS
//Language: C++ Result: Accepted
//Union-Find Set
//2010.08.02
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define MAXN 40010
#define ABS(x) ((x)>=0?(x):(-x))
  struct Edge {
 int a,b,w;
char dir;
 }e[MAXN];
struct query{
int idx,a,b;
}q[10010];
struct node{
int f,a,b;
}v[MAXN];
int n,m,k;
char d[4]={'N','E','S','W'};
int step[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int ex_dir(char c){
for(int i=0;i<4;i++)
if(d[i]==c)return i;
}
bool cmp(query a,query b){
return a.idx<b.idx;
}
int findset(int idx,int &x,int &y){
int t=idx;
x=y=0;
  while(v[t].f!=-1){
x+=v[t].a;
y+=v[t].b;
t=v[t].f;
 }
return t;
}
void unionset(int x){
int x1,x2,y1,y2;
int v1=e[x].a,v2=e[x].b;
int f1=findset(v1,x1,y1),f2=findset(v2,x2,y2);
if(f1==f2)return;
int dd=ex_dir(e[x].dir);
v[f2].f=f1;
v[f2].a=step[dd][0]*e[x].w+x1-x2;
v[f2].b=step[dd][1]*e[x].w+y1-y2;
}
int main(){
int i,j,f1,f2,x1,x2,y1,y2;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++){
scanf("%d %d %d %c",&e[i].a,&e[i].b,&e[i].w,&e[i].dir);
}
scanf("%d",&k);
for(i=0;i<k;i++){
scanf("%d %d %d",&q[i].a,&q[i].b,&q[i].idx);
}
sort(q,q+k,cmp);
for(i=0;i<=n;i++)v[i].f=-1;
for(i=0,j=0;i<m;i++){
unionset(i);
while(j<k && q[j].idx<=i+1){
f1=findset(q[j].a,x1,y1);
f2=findset(q[j].b,x2,y2);
if(f1==f2)printf("%d\n",ABS(x1-x2)+ABS(y1-y2));
else
printf("-1\n");
j++;
}
}
return 0;
}
|