并查集的一个应用,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1984
//并查集合的一个应用
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdio.h>
#include <math.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int p[40005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int x;
int y;
}point;
point dis[40005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void make ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
p[i] = -1;
dis[i].x = dis[i].y = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find ( int pre )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( p[pre] < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return pre;
}
int root = find ( p[pre] );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dis[pre].x += dis[ p[pre] ].x;
dis[pre].y += dis[ p[pre] ].y;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
p[pre] = root;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return root;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void un ( int a, int b, int l, char done )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int ra = find ( a );
int rb = find ( b );
point oldp, newp;
oldp.x = dis[b].x;
oldp.y = dis[b].y;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( done == 'E' )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
newp.x = dis[a].x + l;
newp.y = dis[a].y;
}
else if ( done == 'S' )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
newp.x = dis[a].x;
newp.y = dis[a].y - l;
}
else if ( done == 'W' )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
newp.x = dis[a].x - l;
newp.y = dis[a].y;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
newp.x = dis[a].x;
newp.y = dis[a].y + l;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
p[rb] = ra;
dis[rb].x = newp.x - oldp.x;
dis[rb].y = newp.y - oldp.y;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int a;
int b;
int l;
char done;
}rela[40005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int next;
int last;
}head[40005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int a;
int b;
int addr;
int i;
int next;
}po[10005];
int now;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void inith ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
now = 0;
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head[i].next = head[i].last = -1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void add ( int a, int b, int i, int addr )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
po[now].a = a;
po[now].b = b;
po[now].addr = addr;
po[now].next = -1;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( head[i].next == -1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head[i].next = now;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
po[ head[i].last ].next = now;
}
head[i].last = now ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int que[10005];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n, m;
int a, b, l;
char in[5];
int k;
int f1, f2, di;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d%d", &n, &m ) != EOF )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for ( int i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d%d%d%s", &a, &b, &l, in );
rela[i].a = a-1;
rela[i].b = b-1;
rela[i].l = l;
rela[i].done = in[0];
}
make ( n );
inith ( m );
scanf ( "%d", &k );
for ( i=0; i<k; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d%d%d", &f1, &f2, &di );
add ( f1-1, f2-1, di-1, i );
}
for ( i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( find ( rela[i].a ) != find ( rela[i].b ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
un ( rela[i].a, rela[i].b, rela[i].l, rela[i].done );
}
for ( int j=head[i].next; j!=-1; j=po[j].next )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( find ( po[j].a ) != find ( po[j].b ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
que[po[j].addr] = -1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int ans = abs ( dis[ po[j].a ].x - dis[ po[j].b ].x ) + abs ( dis[ po[j].a ].y - dis[ po[j].b ].y );
que[po[j].addr] = ans;
}
}
}
for ( i=0; i<k; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "%d\n", que[i] );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|