[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;
}
初级程序员
by: 云代码会员 发表于:2015-06-19 15:23:37 顶(1) | 踩(0) 回复
不错
回复评论