1.并查集求最小生成树
Code：
#include <stdio.h>
#include <stdlib.h>
struct node
{
long x,y,c;
}road[];
long fa[];
int cmp(const void *a,const void *b)
{
if ((*(struct node *)a).c < (*(struct node *)b).c)
return -;
else
return ;
}
long getfather(long d)
{
if (fa[d]==d)
return d;
fa[d]=getfather(fa[d]);
return fa[d];
}
int main()
{
long n,m,t,xx,yy,x,y,i,cnt;
long long cost=;
scanf("%ld%ld",&n,&m);
cnt=n-;
for (i=;i<=n;i++)
fa[i]=i;
for (i=;i<=m;i++)
{
scanf("%ld%ld",&x,&y);
xx=getfather(x);
yy=getfather(y);
if (xx!=yy)
{
fa[xx]=yy;
cnt--;
if (cnt==)
{
printf("0\n");
return ;
}
}
}
scanf("%ld",&t);
for (i=;i<t;i++)
scanf("%ld%ld%ld",&road[i].x,&road[i].y,&road[i].c);
qsort(road,t,sizeof(struct node),cmp);
for (i=;i<t;i++)
{
xx=getfather(road[i].x);
yy=getfather(road[i].y);
if (xx!=yy)
{
fa[xx]=yy;
cost+=road[i].c;
cnt--;
if (cnt==)
{
printf("%lld\n",cost);
return ;
}
}
}
printf("-1\n");
return ;
}
2.点有权值，spfa
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node
{
long c;
struct node *next;
}*city[];
long q[],pre[],m;
long min(long a,long b)
{
if (a>b)
return b;
else
return a;
}
void print(long d)
{
if (d!=m)
print(pre[d]);
printf("%ld",d);
if (d!=)
printf("->");
else
printf("\n");
}
int main()
{
long i,j,s,t,b,e,n,ren,g[],head,tail,sum[];
bool vis[];
struct node *p;
scanf("%ld%ld%ld",&n,&m,&ren);
for (i=;i<=n;i++)
{
scanf("%ld",&g[i]);
scanf("%ld",&s);
for (j=;j<=s;j++)
{
scanf("%ld",&t);
p=(struct node *) malloc (sizeof(struct node));
p->c=t;
p->next=city[i];
city[i]=p;
}
}
for (i=;i<=n;i++)
{
vis[i]=true;
sum[i]=;
}
sum[m]=g[m];
head=;
tail=;
q[]=m;
do
{
head=(head+)%;
// head++;
b=q[head];
p=city[b];
while (p)
{
e=p->c;
if (sum[b]+g[e]<sum[e])
{
sum[e]=sum[b]+g[e];
pre[e]=b;
if (vis[e])
{
tail=(tail+)%;
// tail++;
q[tail]=e;
vis[e]=false;
}
}
p=p->next;
}
vis[b]=true;
}
while (head!=tail);
if (sum[]<=ren*)
{
print();
printf("%ld\n",ren-sum[]/);
}
else
printf("No way!");
return ;
}
3.
地图bfs
U10278 Cx的金字塔 _ 落谷1126机器人搬重物 解题报告
I.哪个是行，哪个是列，行列从哪边开始
II.一次操作
1.前移1,2,3！步
2.转90度
III.边界范围 1~n-1 1~m-1
IV.起始点不可用
V.起始点=终止点
Code：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct node
{
long x,y,c,step;
}q[];
bool vis[][][];
long head,tail,s,t;
void add(long x,long y,long c)
{
tail++;
q[tail].x=x;
q[tail].y=y;
q[tail].c=c;
q[tail].step=q[head].step+;
vis[x][y][c]=false;
if (x==s && y==t)
{
printf("%ld\n",q[tail].step);
exit();
}
}
int main()
{
long n,m,i,j,k,x,y,c;
long map[][];
char ccs,cs;
scanf("%ld%ld",&n,&m);
for (i=;i<=n;i++)
for (j=;j<=m;j++)
for (k=;k<;k++)
vis[i][j][k]=true;
for (i=;i<=n;i++)
for (j=;j<=m;j++)
scanf("%ld",&map[i][j]);
scanf("%ld%ld%ld%ld%c%c",&x,&y,&s,&t,&ccs,&cs);
if (x== || x==n || y== || y==m || map[x][y]== || map[x+][y]== || map[x][y+]== || map[x+][y+]==)
{
printf("-1");
return ;
}
if (x==s && y==t)
{
printf("0\n");
return ;
}
head=;
tail=;
q[].x=x;
q[].y=y;
if (cs=='E')
c=;
else if (cs=='S')
c=;
else if (cs=='W')
c=;
else
c=;
q[].c=c;
q[].step=;
vis[x][y][c]=false;
//上：0 下：1 左：2 右：3
head=;
tail=;
do
{
head++;
x=q[head].x;
y=q[head].y;
c=q[head].c;
//上
if (c==)
{
if (x> && map[x-][y]== && map[x-][y+]==)
{
if (vis[x-][y][c])
add(x-,y,c);
if (x> && map[x-][y]== && map[x-][y+]==)
{
if (vis[x-][y][c])
add(x-,y,c);
if (x> && map[x-][y]== && map[x-][y+]== && vis[x-][y][c])
add(x-,y,c);
}
}
}
//下
else if (c==)
{
if (x<n- && map[x+][y]== && map[x+][y+]==)
{
if (vis[x+][y][c])
add(x+,y,c);
if (x<n- && map[x+][y]== && map[x+][y+]==)
{
if (vis[x+][y][c])
add(x+,y,c);
if (x<n- && map[x+][y]== && map[x+][y+]== && vis[x+][y][c])
add(x+,y,c);
}
}
}
//左
else if (c==)
{
if (y> && map[x][y-]== && map[x+][y-]==)
{
if (vis[x][y-][c])
add(x,y-,c);
if (y> && map[x][y-]== && map[x+][y-]==)
{
if (vis[x][y-][c])
add(x,y-,c);
if (y> && map[x][y-]== && map[x+][y-]== && vis[x][y-][c])
add(x,y-,c);
}
}
}
//右
else
{
if (y<m- && map[x][y+]== && map[x+][y+]==)
{
if (vis[x][y+][c])
add(x,y+,c);
if (y<m- && map[x][y+]== && map[x+][y+]==)
{
if (vis[x][y+][c])
add(x,y+,c);
if (y<m- && map[x][y+]== && map[x+][y+]== && vis[x][y+][c])
add(x,y+,c);
}
}
}
if (c== || c==)
{
if (vis[x][y][])
add(x,y,);
if (vis[x][y][])
add(x,y,);
}
else
{
if (vis[x][y][])
add(x,y,);
if (vis[x][y][])
add(x,y,);
}
}
while (head<tail);
printf("-1\n");
return ;
}
4.
对于70%的数据：
2<=a<=250
对于100%的数据：
2<=a<=2^60
对于70%的数据：
初始：
现有一个花坛（A坛）装满了白蛇根草，还有两个空花坛（B坛，C坛），
三个花坛共有250*250*250=15625000种
(x,y,z)->其它状态
当有其中两个花坛的数目为|A|/2时结束
by lzu_cgb
share & spread ideas