挖雷问题

[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;
}