华师一附中OI组

标题: P2128 赤壁之战 [打印本页]

作者: admin 时间: 2018-10-1 10:34
标题: P2128 赤壁之战
https://www.luogu.org/problemnew/show/P2128

题目描述
赤壁之战，黄盖率舰满载薪草膏油诈降曹军。

受庞统所授的连环计，曹军战船之间由铁索相连，没有两艘战船在同一位置，也没有铁索两两相交或穿过战船。每艘船都有其一定的战略价值。

为了保证达到破坏效果，黄盖需要保证被点燃的曹军船只两两之间都有铁索连接。他希望找到一种方案点燃总价值尽可能大的战船。

输入输出格式
输入格式：
第一行包含数字 N; M ，表示战船的数量和铁索的数量。

接下来包含 N 行，每 i 行包含 1 个数字 Vi ，表示第 i 艘战船的战略价值。

接下来包含 M 行，每 i 行包含 2 个数字 Si; Ti ，表示铁索连接的两艘船只。

数据保证这是一个可行的舰队安排。

输出格式：
输出一个数字，表示最多摧毁总价值多少的战船。

输入输出样例
输入样例#1：
4 6
100
5000
1000
2000
1 2
1 3
1 4
2 3
2 4
3 4
输出样例#1：
8100
输入样例#2：
6 8
1500
1000
100
2000
500
300
1 2
1 3
1 4
2 4
3 5
4 5
4 6
5 6
输出样例#2：
4500
说明
【数据规模】

对于50%的数据，保证 N，M ≤ 10。

对于100%数据，保证 N ≤ 450; M ≤ 900; Vi ≤ 6000。

【注意】

题目中的每句话（除了第一段）都有作用。

作者: 黄煦喆 时间: 2018-10-6 11:39
这题先还以为是并查集
有一个点TLE

#include<iostream>
using namespace std;
int n,m,v[500],x,y,c[500],ans,sum;
bool b[500][500],bb;
bool ch(int p,int l)
{
for(int i=1;i<=l;i++)if(!b[c[i]][p])return 0;
return 1;
}
void dfs(int x,int i)
{
if(x>n)return;
ans=max(ans,sum);
dfs(x+1,i);
for(int j=x+1;j<=n;j++)
{
if(ch(j,i))
{
c[++i]=j;
sum+=v[j];
dfs(j,i);
sum-=v[j];
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=m;i++)
{
cin>>x>>y;
b[x][y]=1;
}
dfs(0,0);
cout<<ans;
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)