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.起始点=终止点

洛谷_Cx的故事_解题报告_第四题70-LMLPHP

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

04-30 19:08