摘要: 大数问题,地址: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>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int LEN = 1000;
![](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 b;
int e;
int length;
}type;
type seg[LEN];
int next;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
next = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int point[LEN];
![](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) {
point[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 ( point[a] < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return a;
}
int r = find ( point[a] );
point[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)
if ( point[ra] < point[rb] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
point[ra] += point[rb];
point[rb] = ra;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
point[rb] += point[ra];
point[ra] = rb;
}
}
![](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 ( ( type * )a )->length - ( ( type * )b )->length;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int kul ( 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)
int ans = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort ( seg, next, sizeof ( type ), cmp );
make ( n );
for ( int i=0; i< next; 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) {
ans += seg[i].length;
un ( seg[i].b, seg[i].e );
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return ans;
}
![](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;
char chi[5], chj[5];
int len;
int in;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%d", &n ) != EOF && n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
init ();
for ( int i=0; i<n-1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%s%d", &chi, &len );
for ( int j=0; j<len; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf ( "%s%d", &chj, &in );
seg[next].b = chi[0] - 'A';
seg[next].e = chj[0] - 'A';
seg[next++].length = in;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "%d\n", kul ( n ) );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
摘要: 凸包问题的一个应用,地址: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];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int relation1[3]= {0,1,2}; /**//*正权*/
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int relation2[3]= {0,2,1}; /**//*负权*/
void make(int p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i;
for(i=0;i<p;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
num[i]=-1;
dis[i]=0;
}
}
int find(int p)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int ra=find(a);
int rb=find(b);
num[rb]=ra;
dis[rb]=dis[a]+len-dis[b];
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n)count++;
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
rx=find(x-1);
ry=find(y-1);
if(d==1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(rx!=ry)un(x-1,y-1,0);
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(rx!=ry)un(x-1,y-1,1);
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
摘要: 一个计算机和的题目,要做的事最多有多少个点共线,做法是对线段进行排序,然后查找。注意HASH。
#include < stdio.h >#include < stdlib.h >typedef struct{ int x; &... 阅读全文
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
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)
阅读排行榜
评论排行榜
|
|