一个并查集题目,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1988
#include <stdio.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <string.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int num[30005];/**//*路径*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int c[30005];/**//*集合中比C大的数的数量*/
![](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) {
num[i] = -1;
c[i] = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find ( int a )
![](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 ( num[a] < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return a;
}
int r = find ( num[a] );
c[a] += c[ num[a] ];
num[a] = r;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return r;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void un ( int a, int b )
![](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 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
c[rb] += -num[ra];
num[ra] += num[rb];
num[rb] = ra;
}
![](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 p;
char in[5];
int a, b;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d", &p ) != EOF )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
make ( 30000 );
for ( int i=0; i<p; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%s", in );
if ( ! strcmp ( in, "M" ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d%d", &a, &b );
if ( find ( a-1 ) != find ( b-1 ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
un ( a-1, b-1 );
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%d", &a );
int ra = find ( a-1 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "%d\n", -num[ra]-c[a-1]-1 );
}
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
摘要: 路径归并,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1986
#include <stdio.h>const int LEN = 40005;int p[LEN];void make ( int n ){ &nb... 阅读全文
摘要: 并查集的一个应用,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1984
//并查集合的一个应用#include <stdio.h>#include <math.h>int p[40005];typedef struct{ int&nbs... 阅读全文
摘要: 排序+HASH,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1974
#include <stdio.h>#include <stdlib.h>const int MAX = 131075;typedef struct{ &nbs... 阅读全文
数平行四边形,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1971
#include <iostream>
#include <algorithm>
#include <memory>
using namespace std;
struct point
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int x,y;
};
struct seg
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int a,b;
point v;
};
bool operator <(seg a,seg b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
return (a.v.x<b.v.x)||(a.v.x==b.v.x&&a.v.y<b.v.y);
}
seg tmp, vs[500500];
point p[1000];
bool commen(int i,int j);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int i,j,k,n, t;
cin>>t;
for(k = 0 ; k < t ;k ++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
memset(vs,0,sizeof(vs));
cin>>n;
for(i = 0 ;i < n ; i ++) cin>>p[i].x>>p[i].y;
int num=0;
for(i = 0 ;i < n-1 ; i ++)
for(j = i +1 ;j < n ;j ++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tmp.a = i; tmp.b = j;
tmp.v.x = p[i].x-p[j].x; tmp.v.y = p[i].y-p[j].y;
if(tmp.v.x<=0&&tmp.v.y<=0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tmp.v.x=-tmp.v.x; tmp.v.y=-tmp.v.y;
}
if(tmp.v.x<=0&&tmp.v.y>=0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
tmp.v.x=-tmp.v.x; tmp.v.y=-tmp.v.y;
}
vs[num++]=tmp;
}
sort(vs,vs+num);
int sum = 0;
int beg = 0;
while(beg < num)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(i = beg; vs[i].v.x==vs[beg].v.x&&vs[i].v.y==vs[beg].v.y;i++)
for(j = i+1;vs[j].v.x==vs[beg].v.x&&vs[j].v.y==vs[beg].v.y;j++ )
if(!commen(i,j))sum++;
beg = i;
}
cout<<sum/2<<endl;
}
return 0;
}
bool commen(int i,int j)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if((p[vs[j].b].x-p[vs[i].a].x)*vs[i].v.y==(p[vs[j].b].y-p[vs[i].a].y)*vs[i].v.x)
return 1;
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
摘要: 本来不想写的,但是这个题目可以用双向广搜来做,所以也就写写吧。地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1915
#include < stdio.h >#include < stdlib.h >int hash[301][301][2];typed... 阅读全文
最小生成树中的最长边,地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1861
#include <stdio.h>
#include <stdlib.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 15005;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
struct segment
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int b;
int e;
int len;
}seg[LEN];//线段
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int used[LEN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
used[i] = 0;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//并查集部分
int fa[LEN/10];
![](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) {
fa[i] = -1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find ( int a )
![](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 ( fa[a]<0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return a;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int r = find ( fa[a] );
fa[a] = r;
return r;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void un ( int a, int b )
![](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 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( fa[ra]<fa[rb] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
fa[ra] += fa[rb];
fa[rb] = ra;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
fa[rb] += fa[ra];
fa[ra] = rb;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//主要处理部分
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp ( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return ( (segment *)a )->len - ( (segment *)b )->len;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void kul ( int n, int m )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort ( seg, m, sizeof ( segment ), cmp );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int max = -1;
int count = 0;
init ( n );
make ( n );
for ( int i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( find ( seg[i].b )!=find ( seg[i].e ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
un ( seg[i].b, seg[i].e );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
used[i] = 1;
count ++;
if ( max < seg[i].len )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
max = seg[i].len;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "%d\n%d\n", max, count );
for ( int i=0; i<m; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( used[i] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "%d %d\n", seg[i].b+1, seg[i].e+1 );
}
}
}
![](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 b, e, len;
![](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", &b, &e, &len );
seg[i].b = b-1<e-1 ? b-1:e-1;
seg[i].e = b-1>e-1 ? b-1:e-1;
seg[i].len = len;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
kul ( n, m );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
28 | 29 | 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 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|