一个并查集题目，地址： http://acm.pku.edu.cn/JudgeOnline/problem?id=1988
 #include <stdio.h>
#include <string.h>
  int num[30005];/**//*路径*/
int c[30005];/**//*集合中比C大的数的数量*/
void make ( int n )
 {
for ( int i=0; i<n; i++ )
  {
num[i] = -1;
c[i] = 0;
 }
 }
int find ( int a )
{
if ( num[a] < 0 )
{
return a;
}
int r = find ( num[a] );
c[a] += c[ num[a] ];
num[a] = r;
return r;
}
void un ( int a, int b )
{
int ra = find ( a );
int rb = find ( b );
c[rb] += -num[ra];
num[ra] += num[rb];
num[rb] = ra;
}
int main ()
{
int p;
char in[5];
int a, b;
while ( scanf ( "%d", &p ) != EOF )
{
make ( 30000 );
for ( int i=0; i<p; i++ )
{
scanf ( "%s", in );
if ( ! strcmp ( in, "M" ) )
{
scanf ( "%d%d", &a, &b );
if ( find ( a-1 ) != find ( b-1 ) )
{
un ( a-1, b-1 );
}
}
else
{
scanf ( "%d", &a );
int ra = find ( a-1 );
printf ( "%d\n", -num[ra]-c[a-1]-1 );
}
}
}
return 0;
}
摘要: 路径归并，地址：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
{
int x,y;
};
struct seg
{
int a,b;
point v;
};
bool operator <(seg a,seg b)
{
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);
int main(){
int i,j,k,n, t;
cin>>t;
for(k = 0 ; k < t ;k ++)
{
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 ++)
{
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)
{
tmp.v.x=-tmp.v.x; tmp.v.y=-tmp.v.y;
}
if(tmp.v.x<=0&&tmp.v.y>=0)
{
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)
{
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)
{
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://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>
const int LEN = 15005;
struct segment
{
int b;
int e;
int len;
}seg[LEN];//线段
int used[LEN];
void init ( int n )
{
for ( int i=0; i<n; i++ )
{
used[i] = 0;
}
}
//并查集部分
int fa[LEN/10];
void make ( int n )
{
for ( int i=0; i<n; i++ )
{
fa[i] = -1;
}
}
int find ( int a )
{
if ( fa[a]<0 )
{
return a;
}
int r = find ( fa[a] );
fa[a] = r;
return r;
}
void un ( int a, int b )
{
int ra = find ( a );
int rb = find ( b );
if ( fa[ra]<fa[rb] )
{
fa[ra] += fa[rb];
fa[rb] = ra;
}
else
{
fa[rb] += fa[ra];
fa[ra] = rb;
}
}
//主要处理部分
int cmp ( const void *a, const void *b )
{
return ( (segment *)a )->len - ( (segment *)b )->len;
}
void kul ( int n, int m )
{
qsort ( seg, m, sizeof ( segment ), cmp );
int max = -1;
int count = 0;
init ( n );
make ( n );
for ( int i=0; i<m; i++ )
{
if ( find ( seg[i].b )!=find ( seg[i].e ) )
{
un ( seg[i].b, seg[i].e );
used[i] = 1;
count ++;
if ( max < seg[i].len )
{
max = seg[i].len;
}
}
}
printf ( "%d\n%d\n", max, count );
for ( int i=0; i<m; i++ )
{
if ( used[i] )
{
printf ( "%d %d\n", seg[i].b+1, seg[i].e+1 );
}
}
}
int main ()
{
int n, m;
int b, e, len;
while ( scanf ( "%d%d", &n, &m ) != EOF )
{
for ( int i=0; i<m; i++ )
{
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;
}
kul ( n, m );
}
return 0;
}
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|