P2128 赤壁之战

admin

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。

【注意】

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

黄煦喆

这题先还以为是并查集
有一个点TLE

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m,v[500],x,y,c[500],ans,sum;
   
4. bool b[500][500],bb;
   
5. bool ch(int p,int l)
   
6. {
   
7.     for(int i=1;i<=l;i++)if(!b[c[i]][p])return 0;
   
8.     return 1;
   
9. }
   
10. void dfs(int x,int i)
    
11. {
    
12.     if(x>n)return;
    
13.     ans=max(ans,sum);
    
14.     dfs(x+1,i);
    
15.     for(int j=x+1;j<=n;j++)
    
16.     {
    
17.         if(ch(j,i))
    
18.         {
    
19.             c[++i]=j;
    
20.             sum+=v[j];
    
21.             dfs(j,i);
    
22.             sum-=v[j];
    
23.         }
    
24.     }
    
25. }
    
26. int main()
    
27. {
    
28.     cin>>n>>m;
    
29.     for(int i=1;i<=n;i++)cin>>v[i];
    
30.     for(int i=1;i<=m;i++)
    
31.     {
    
32.         cin>>x>>y;
    
33.         b[x][y]=1;
    
34.     }
    
35.     dfs(0,0);
    
36.     cout<<ans;
    
37.     return 0;
    
38. }
    

复制代码