用户注册



邮箱:

密码:

用户登录


邮箱:

密码:
记住登录一个月忘记密码?

发表随想


还能输入:200字
云代码 - c代码库

挖雷问题

2015-03-14 作者: 西门春雪举报

[c]代码库

#include <stdio.h>
#include <stdlib.h>

#define MAXNUM 200

int n;//地窖的个数
int w[MAXNUM];//每个地窖中的地雷数
int Sum[MAXNUM];//挖到的地雷总数
int G[MAXNUM][MAXNUM];//形成的图
int next[MAXNUM];//记录路径
int max;//最大值
int start;

//void init(int G[MAXNUM][MAXNUM]);
//void init2(int n[MAXNUM]);

int main()
{
    int i,j,x,y;
    printf("输入地窖的个数n(1-200):\n");
    scanf("%d",&n);
    printf("输入各个地窖中的地雷数:\n");
    for(i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    //init(G);//初始化有向图
    printf("输入各个地窖之间的链接(x,y):\n");
    scanf("%d,%d",&x,&y);
    while(x!=0&&y!=0)
    {
        G[x][y]=1;
        scanf("%d,%d",&x,&y);
    }
    //init2(Sum);

    Sum[n]=w[n];
    for(i=n-1;i>=1;i--)
    {
        for(j=i+1;j<=n;j++)
        {
            if(G[i][j]&&Sum[j]>Sum[i])
            {
                Sum[i]=Sum[j];
                next[i]=j;
            }
        }
        Sum[i] += w[i];
    }
    max = 0;
    for(i=1;i<=n;i++)
    {
        if(Sum[i]>max)
        {
            max=Sum[i];
            start = i;
        }
    }


    printf("最大路径:");
    printf("%d-",start);
    while(next[start]!=0)
    {
        printf("%d-",next[start]);
        start = next[start];
    }
    printf("最大挖雷数:%d\n",max);
    return 0;
}


网友评论    (发表评论)

共2 条评论 1/1页

发表评论:

评论须知:

  • 1、评论每次加2分,每天上限为30;
  • 2、请文明用语,共同创建干净的技术交流环境;
  • 3、若被发现提交非法信息,评论将会被删除,并且给予扣分处理,严重者给予封号处理;
  • 4、请勿发布广告信息或其他无关评论,否则将会删除评论并扣分,严重者给予封号处理。


扫码下载

加载中,请稍后...

输入口令后可复制整站源码

加载中,请稍后...