洛谷——P2128 赤壁之战
2024-08-27 17:40:41
P2128 赤壁之战
题目描述
赤壁之战,黄盖率舰满载薪草膏油诈降曹军。
受庞统所授的连环计,曹军战船之间由铁索相连,没有两艘战船在同一位置,也没有铁索两两相交或穿过战船。每艘船都有其一定的战略价值。
为了保证达到破坏效果,黄盖需要保证被点燃的曹军船只两两之间都有铁索连接。他希望找到一种方案点燃总价值尽可能大的战船。
输入输出格式
输入格式:
第一行包含数字 N; M ,表示战船的数量和铁索的数量。
接下来包含 N 行,每 i 行包含 1 个数字 Vi ,表示第 i 艘战船的战略价值。
接下来包含 M 行,每 i 行包含 2 个数字 Si; Ti ,表示铁索连接的两艘船只。
数据保证这是一个可行的舰队安排。
输出格式:
输出一个数字,表示最多摧毁总价值多少的战船。
输入输出样例
说明
【数据规模】
对于50%的数据,保证 N,M ≤ 10。
对于100%数据,保证 N ≤ 450; M ≤ 900; Vi ≤ 6000。
【注意】
题目中的每句话(除了第一段)都有作用。
搜索
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 5010 using namespace std; bool vis[N]; ],edge[N][N]; int read() { ,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f; } int pd(int x) { ;i<=sum;i++) ; ; } int dfs(int x,int s) { if(s>ans) ans=s; ;i<=n;i++) ) { vis[i]=true; q[++sum]=i; dfs(x+,s+v[i]); vis[i]=false; sum--; } } int main() { n=read(),m=read(); ;i<=n;i++) v[i]=read(); ;i<=m;i++) { x=read(),y=read(); edge[x][y]=; edge[y][x]=; } dfs(,); printf("%d",ans); ; }
最新文章
- 如何为datagridview加上序号
- php+mysql
- 浏览器缓存详解:expires,cache-control,last-modified,etag详细说明
- HTML 父窗口打开子窗口,并从子窗口返回值
- RPM包制作最简单样例
- 安卓模拟器还是";genymotion";最靠谱.
- 关于CSS选择器的效率问题
- POJ 1562(L - 暴力求解、DFS)
- C++编程练习(12)----“有向图的拓扑排序“
- 事务的特性(ACID)
- 【bzoj 1407】【Noi2002】Savage
- redis cluster最简配置
- linux 安装ssh以及ssh用法与免密登录
- Redis缓存设计及常见问题
- Android项目实战(三十二):圆角对话框Dialog
- Java Calendar,Date,DateFormat,TimeZone,Locale等时间相关内容的认知和使用(1) Calendar
- CASE (Transact-SQL)
- ubuntu 14.04 将窗体button移到右边
- vxer
- 用e2fsck修复受损的linux文件系统