摘要: 大数问题，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1306
/** *//***********************************************************************************************无符号大整数类，包括了*和+法，类可以用小整数或者字符串输入，储存方... 阅读全文
摘要: 最大流问题，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1274
/**//*距离标号的最大流*/#include <stdio.h>const int LEN = 500;const int MAX = 0x7fffffff;struct{&... 阅读全文
摘要: 最大流问题，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
/**//*距离标号的最大流*/#include <stdio.h>const int LEN = 201;const int MAX = 0x7fffffff;struct{&... 阅读全文
最小生成树。地址： http://acm.pku.edu.cn/JudgeOnline/problem?id=1251
 #include <stdio.h>
#include <stdlib.h>
const int LEN = 1000;
typedef struct
   {
 int b;
int e;
int length;
 }type;
type seg[LEN];
int next;
void init ()
{
next = 0;
}
int point[LEN];
void make ( int n )
{
for ( int i=0; i<n; i++ )
  {
point[i] = -1;
 }
}
int find ( int a )
{
if ( point[a] < 0 )
{
return a;
}
int r = find ( point[a] );
point[a] = r;
return r;
}
void un ( int a, int b )
{
int ra = find ( a );
int rb = find ( b );
if ( point[ra] < point[rb] )
{
point[ra] += point[rb];
point[rb] = ra;
}
else
{
point[rb] += point[ra];
point[ra] = rb;
}
}
int cmp ( const void *a, const void *b )
{
return ( ( type * )a )->length - ( ( type * )b )->length;
}
int kul ( int n )
{
int ans = 0;
qsort ( seg, next, sizeof ( type ), cmp );
make ( n );
for ( int i=0; i< next; i++ )
{
if ( find ( seg[i].b ) != find ( seg[i].e ) )
{
ans += seg[i].length;
un ( seg[i].b, seg[i].e );
}
}
return ans;
}
int main ()
{
int n;
char chi[5], chj[5];
int len;
int in;
while ( scanf ( "%d", &n ) != EOF && n )
{
init ();
for ( int i=0; i<n-1; i++ )
{
scanf ( "%s%d", &chi, &len );
for ( int j=0; j<len; j++ )
{
scanf ( "%s%d", &chj, &in );
seg[next].b = chi[0] - 'A';
seg[next].e = chj[0] - 'A';
seg[next++].length = in;
}
}
printf ( "%d\n", kul ( n ) );
}
return 0;
}
摘要: 凸包问题的一个应用，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1228
#include < stdio.h >#include < stdlib.h >typedef struct{ int ... 阅读全文
摘要: 昨天晚上太卡了，竟然没有全部发完，今天早上早早起来发一下，1113是一个计算几何的题目，求得是凸包问题，就是在二维平面上给定一系列的点，求一个最小的凸包将它们全部覆盖，所谓凸包就是一个多边形，在这个多边形内的任意两点间的连线都在多边形内。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
#include < std... 阅读全文
NOI的题目，并查集的高级应用，很好玩的一个题目。题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
#include "stdio.h"
int num[50005];
int dis[50005];
int relation1[3]={0,1,2}; /**//*正权*/
int relation2[3]={0,2,1}; /**//*负权*/
void make(int p)
{
int i;
for(i=0;i<p;i++)
{
num[i]=-1;
dis[i]=0;
}
}
int find(int p)
{
int i;
if(num[p]<0)return p;
i=find(num[p]);
dis[p]=dis[p]+dis[num[p]];
num[p]=i;
return i;
}
void un(int a,int b,int len)
{
int ra=find(a);
int rb=find(b);
num[rb]=ra;
dis[rb]=dis[a]+len-dis[b];
}
int main()
{
int n,k,i;
int x,y,d;
int rx,ry;
int dx,dy;
int count;
scanf("%d%d",&n,&k);
make(n);count=0;
for(i=0;i<k;i++)
{
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n)count++;
else
{
rx=find(x-1);
ry=find(y-1);
if(d==1)
{
if(rx!=ry)un(x-1,y-1,0);
else
{
if(dis[x-1]<0)dx=relation2[(-dis[x-1])%3];
else dx=relation1[dis[x-1]%3];
if(dis[y-1]<0)dy=relation2[(-dis[y-1])%3];
else dy=relation1[dis[y-1]%3];
if(dx!=dy)count++;
}
}
else
{
if(rx!=ry)un(x-1,y-1,1);
else
{
if(dis[x-1]<0)dx=relation2[(-dis[x-1])%3];
else dx=relation1[dis[x-1]%3];
if(dis[y-1]<0)dy=relation2[(-dis[y-1])%3];
else dy=relation1[dis[y-1]%3];
if((dx+1)%3!=dy)count++;
}
}
}
}
printf("%d\n",count);
return 0;
}
摘要: 一个计算机和的题目，要做的事最多有多少个点共线，做法是对线段进行排序，然后查找。注意HASH。
#include < stdio.h >#include < stdlib.h >typedef struct{ int x; &... 阅读全文
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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)
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|