题解 P2128 【赤壁之战】

06ray · 2017-08-28 11:57:45 · 题解

这道题用搜索与回溯的方法AC。思路是枚举第i艘船并判断是否与前面选的船都有铁索相连。如果都有，就把这艘船的编号放进一个数组里。最后用一个max1的数存最大值，输出max1。

代码如下(*^▽^*)

#include <bits/stdc++.h>//懒人喜欢的万能头文件
using namespace std;
int a[1000],b[5000][5000],c[10000],used[100000];//a数组存的是每艘船的价值，b数组是与每两艘船的关系，c是存放选中的船的价值，used是判断i艘船是否被选过
int n,m,n1,max1=0;
bool pd(int x,int n1)//判断第i艘船是否与前面选的船都有铁索相连
{
    for(int i=1; i<=n1; i++)
    if(b[c[i]][x]==false) 
    {
        return false;
    }
    return true;
}
int search(int t,int s)//搜索函数
{
        if(s>max1) max1=s;//如果当前累加的价值大于目前最大值，就刷新最大值。
    for(int i=1; i<=n; i++)
    if(t==1||!used[i]&&pd(i,n1))//如果第i艘船没使用过且第i艘船与前面选的船都有铁索相连（搜索第一个数除外）
    {
        used[i]=true;//标记第i艘船使用过
        c[++n1]=i;//将第i艘船的编号放进c数组
        search(t+1,s+a[i]);//搜索一步
        used[i]=false;//回溯一步
        n1--;
    }
}
int main()
{
    cin>>n>>m;//读入
    for(int i=1; i<=n; i++)
    cin>>a[i];//读入
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;//读入
        b[x][y]=true;//将x,y建立有铁索的关系
        b[y][x]=true;//将x,y建立有铁索的关系
    }
    search(1,0);//搜索
    cout<<max1;//输出
}
本人蒟蒻一枚，望各位大佬，大神们多多指教。