挖地雷（动态规划输出路径）

小咪咪 2022-06-08 08:41 187阅读 0赞

### 【例9.6】挖地雷 ###

时间限制: 1000 ms 内存限制: 65536 KB

### 【题目描述】 ###

在一个地图上有n个地窖（n<=200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向在序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

### 【输入】 ###

第一行：地窖的个数；

第二行为依次每个地窖地雷的个数；

下面若干行：

xi yi //表示从xi可到yi，xi<yi。

最后一行为"0 0"表示结束。

### 【输出】 ###

k1-k2-…-kv //挖地雷的顺序

挖到最多的雷。

### 【输入样例】 ###

6
    5 10 20 5 4 5
    1 2
    1 4
    2 4
    3 4
    4 5
    4 6
    5 6
    0 0

### 【输出样例】 ###

3-4-5-6
    34

### 【来源】 ###

[No][]

![20170920152838976][]

错误的代码：

/*
    6
    5 10 20 5 4 5
    1 2
    1 4
    2 4
    3 4
    4 5
    4 6
    5 6
    0 0
    */
    #include<iostream>
    #include<cstring>
    #define MAXN 200
    using namespace std;
    bool a[MAXN][MAXN];//a[i][j]表示第i个地窖和第j个地窖是否是通路 
    int w[MAXN];//每个地窖的地雷数 
    int f[MAXN];//f[i]表示从第i个地窖开始挖的最多地雷数 
    int suf[MAXN];
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(w,0,sizeof(w));
    	memset(f,0,sizeof(f));
    	long n,i,j,x,y,l,k,maxn;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>w[i];
    	}
    	while(cin>>x>>y)
    	{
    		if(x==0&&y==0) break;
    		a[x][y]=true;
    	}
    	f[n]=w[n];//初始状态
    	for(i=n-1;i>=1;i--)
    	{		 
    		for(j=i+1;j<=n;j++)
    		{
    			if((a[i][j])&&f[i]<w[i]+f[j])
    			{
    				f[i]=w[i]+f[j];
    				suf[i]=j;
    			}
    		}
    	} 
    	k=1;
    	for(i=1;i<=n;i++)//从n个数中找最大值 
    	{
    		if(f[i]>f[k]) k=i;
    	}
    	maxn=f[k];
    	cout<<k;//先输出起始点 
    	k=suf[k];
    	while(k!=0)//向后的链表 
    	{
    		cout<<"-"<<k;
    		k=suf[k];
    	}
    	cout<<endl;
    	cout<<maxn<<endl;
    	return 0;
    }

正确的代码：

/*
    6
    5 10 20 5 4 5
    1 2
    1 4
    2 4
    3 4
    4 5
    4 6
    5 6
    0 0
    */
    #include<iostream>
    #include<cstring>
    #define MAXN 200
    using namespace std;
    bool a[MAXN][MAXN];//a[i][j]表示第i个地窖和第j个地窖是否是通路 
    int w[MAXN];//每个地窖的地雷数 
    int f[MAXN];//f[i]表示从第i个地窖开始挖的最多地雷数 
    int suf[MAXN];
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(w,0,sizeof(w));
    	memset(f,0,sizeof(f));
    	long n,i,j,x,y,l,k,maxn;
    	cin>>n;
    	for(i=1;i<=n;i++)
    	{
    		cin>>w[i];
    	}
    	while(cin>>x>>y)
    	{
    		if(x==0&&y==0) break;
    		a[x][y]=true;
    	}
    	f[n]=w[n];//初始状态
    	for(i=n-1;i>=1;i--)
    	{
    		l=0,k=0;
    		for(j=i+1;j<=n;j++)
    		{
    			if((a[i][j])&&f[j]>l)
    			{
    				l=f[j];
    				k=j;
    			}
    		}
    		f[i]=w[i]+l;
    		suf[i]=k;
    	} 
    	k=1;
    	for(i=1;i<=n;i++)//从n个数中找最大值 
    	{
    		if(f[i]>f[k]) k=i;
    	}
    	maxn=f[k];
    	cout<<k;//先输出起始点 
    	k=suf[k];
    	while(k!=0)//向后的链表 
    	{
    		cout<<"-"<<k;
    		k=suf[k];
    	}
    	cout<<endl;
    	cout<<maxn<<endl;
    	return 0;
    }

[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No
[20170920152838976]: /images/20220608/8b605fba271d4157ae7e0b0b8dbaed75.png