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系统配置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不兼容的问题关键实现流程总结前言作为

SSID究竟是什么? WiFi网络名称及工作方式解析

《SSID究竟是什么?WiFi网络名称及工作方式解析》SID可以看作是无线网络的名称,类似于有线网络中的网络名称或者路由器的名称,在无线网络中,设备通过SSID来识别和连接到特定的无线网络... 当提到 Wi-Fi 网络时,就避不开「SSID」这个术语。简单来说,SSID 就是 Wi-Fi 网络的名称。比如

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c