hdu 3315 My Brute 网络流

2024-08-28 17:18
文章标签 网络 hdu brute 3315

本文主要是介绍hdu 3315 My Brute 网络流,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

Seaco is a beautiful girl and likes play a game called “My Brute”. Before Valentine’s Day, starvae and xingxing ask seaco if she wants to spend the Valentine’s Day with them, but seaco only can spend it with one of them. It’s hard to choose from the two excellent boys. So there will be a competition between starvae and xingxing. The competition is like the game “My Brute”. 


Now starvae have n brutes named from S1 to Sn and xingxing’s brutes are named from X1 to Xn. A competition consists of n games. At the beginning, starvae's brute Si must versus xingxing’s brute Xi. But it’s hard for starvae to win the competition, so starvae can change his brutes’ order to win more games. For the starvae’s brute Si, if it wins the game, starvae can get Vi scores, but if it loses the game, starvae will lose Vi scores. Before the competition, starvae’s score is 0. Each brute can only play one game. After n games, if starvae’s score is larger than 0, we say starvae win the competition, otherwise starvae lose it. 

It’s your time to help starvae change the brutes’ order to make starvae’s final score be the largest. If there are multiple orders, you should choose the one whose order changes the least from the original one. The original order is S1, S2, S3 … Sn-1, Sn, while the final order is up to you. 

For starvae’s brute Si (maybe this brute is not the original brute Si, it is the ith brute after you ordered them) and xingxing’s brute Xi, at first Si has Hi HP and Xi has Pi HP, Si’s damage is Ai and Xi’s is Bi, in other words, if Si attacks, Xi will lose Ai HP and if Xi attacks, Si will lose Bi HP, Si attacks first, then it’s Xi’s turn, then Si… until one of them’s HP is less than 0 or equal to 0, that, it lose the game, and the other win the game. 

Come on, starvae’s happiness is in your hand!

Input

First line is a number n. (1<=n<=90) Then follows a line with n numbers mean V1 to Vn. (0<Vi<1000) Then follows a line with n numbers mean H1 to Hn. (1<=Hi<=100)Then follows a line with n numbers mean P1 to Pn. (1<=Pi<=100) Then follows a line with n numbers mean A1 to An.(1<=Ai<=50) Then follows a line with n numbers mean B1 to Bn. (1<=Bi<=50) A zero signals the end of input and this test case is not to be processed.

Output

For each test case, if starvae can win the competition, print the largest score starvae can get, and then follow a real percentage means the similarity between the original order and the final order you had changed, round it to three digits after the decimal point. If starvae can’t win the competition after changing the order, please just print “Oh, I lose my dear seaco!” Maybe the sample can help you get it.

Sample Input

       
3 4 5 6 6 8 10 12 14 16 7 7 6 7 3 5 3 4 5 6 6 8 10 12 14 16 5 5 5 5 5 5 0

Sample Output

       
7 33.333% Oh, I lose my dear seaco!
读题花费了好长时间,后来发现第二个小知识点不会,看了一下别人的才猛然想起以前鹏哥用过这种方法。。。
不说了都是泪啊。。同样的代码交不同的次数有不同的结果。。。。
题意:


#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define INF 0x3f3f3f3fusing namespace std;
int A[100],B[100],V[100],H[100],P[100];
int head[3000],vis[3000],dis[3000],pre[3000];
int cnt,s,T;
struct node
{int u,v,w,f,next;
} edge[30000];
void add(int u,int v,int w,int f)
{edge[cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].f=f;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].u=v;edge[cnt].v=u;edge[cnt].w=0;edge[cnt].f=-f;edge[cnt].next=head[v];head[v]=cnt++;
}
int SPFA()
{int i;memset(pre,-1,sizeof(pre));memset(vis,0,sizeof(vis));for(i=0; i<=T; i++)dis[i]=-INF;queue<int>q;dis[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();i=head[u];vis[u]=0;while(i!=-1){if(edge[i].w>0&&dis[edge[i].v]<dis[u]+edge[i].f){dis[edge[i].v]=dis[u]+edge[i].f;pre[edge[i].v]=i;if(!vis[edge[i].v]){vis[edge[i].v]=1;q.push(edge[i].v);}}i=edge[i].next;}}if(pre[T]==-1)return 0;return 1;
}
int MincostMaxFlow()
{int ans=0;while(SPFA()){int maxl=INF;int p=pre[T];while(p!=-1){maxl=min(maxl,edge[p].w);p=pre[edge[p].u];}p=pre[T];while(p!=-1){edge[p].w-=maxl;edge[p^1].w+=maxl;p=pre[edge[p].u];}ans+=maxl*dis[T];}return ans;
}
int win(int i,int j)
{int x,y;if(P[j]%A[i]==0)x=P[j]/A[i];elsex=P[j]/A[i]+1;if(H[i]%B[j]==0)y=H[i]/B[j];elsey=H[i]/B[j]+1;if(x<=y)return 1;elsereturn 0;
}
int main()
{int n,i,j;while(~scanf("%d",&n)&&n){cnt=0;memset(head,-1,sizeof(head));for(i=1;i<=n;i++)scanf("%d",&V[i]);for(i=1;i<=n;i++)scanf("%d",&H[i]);for(i=1;i<=n;i++)scanf("%d",&P[i]);for(i=1;i<=n;i++)scanf("%d",&A[i]);for(i=1;i<=n;i++)scanf("%d",&B[i]);s=0,T=2*n+1;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(win(i,j)){if(i==j)add(i,n+j,1,V[i]*100+1);elseadd(i,n+j,1,V[i]*100);}else{if(i==j)add(i,n+j,1,-V[i]*100+1);elseadd(i,n+j,1,-V[i]*100);}}}for(i=1;i<=n;i++){add(0,i,1,0);add(n+i,T,1,0);}int res=MincostMaxFlow();if(res/100<=0)printf("Oh, I lose my dear seaco!\n");elseprintf("%d %.3f%%\n",res/100,100.0*(res%100)/n);}return 0;
}


这篇关于hdu 3315 My Brute 网络流的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1115392

相关文章

Linux网络配置之网桥和虚拟网络的配置指南

《Linux网络配置之网桥和虚拟网络的配置指南》这篇文章主要为大家详细介绍了Linux中配置网桥和虚拟网络的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、网桥的配置在linux系统中配置一个新的网桥主要涉及以下几个步骤:1.为yum仓库做准备,安装组件epel-re

python如何下载网络文件到本地指定文件夹

《python如何下载网络文件到本地指定文件夹》这篇文章主要为大家详细介绍了python如何实现下载网络文件到本地指定文件夹,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...  在python中下载文件到本地指定文件夹可以通过以下步骤实现,使用requests库处理HTTP请求,并结合o

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

《如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解》:本文主要介绍如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别的相关资料,描述了如何使用海康威视设备网络SD... 目录前言开发流程问题和解决方案dll库加载不到的问题老旧版本sdk不兼容的问题关键实现流程总结前言作为