HDU 3316 My Brute（二维费用流）经典
My Brute
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 941 Accepted Submission(s): 372
Problem 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
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!
Author starvae
Source HDU “Valentines Day” Open Programming Contest 2010-02-14 题意：两个团队打比赛，每一个团队有n个人，第一个团队每一个人相应的有：生命值:Hi。攻击值：Ai。每一个团队相应的有：生命值：Pi，攻击值：Bi。第一个团队的每一个人能够随意在第二个团队选一个作为对手。进行比赛。每一个人仅仅能比一次，假设第一个团队的第i个人赢则加Vi分，反之减Vi。全部的人比赛完后有n个比赛对，比赛对为原序列第一个团队的第i人与第二队的第i人比赛的最大比例是多少？前提：最大得分。
输出最大得分和比例。
假设分数<=0则输出Oh, I lose my dear seaco!
#include
#include
#include
using namespace std;
const int MAXN = 1010;
const int MAXM = 100100;
const int INF = 1<<29;
struct EDG{int to,next,cap;int cost,flag;
}edg[MAXM];
int head[MAXN],eid;
int pre[MAXN], cost[MAXN] ; //点0~(n-1)void init(){eid=0;memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,int cap,int cst,int flag){edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;edg[eid].cap=cap; edg[eid].flag=flag; head[u]=eid++;edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;edg[eid].cap=0; edg[eid].flag=-flag; head[v]=eid++;
}bool inq[MAXN];
int q[MAXN],flg[MAXN];
bool spfa(int sNode,int eNode,int n){int l=0 , r=0;for(int i=0; i0&&n){for(int i=1; i<=n; i++)scanf("%d",&valu[i]);for(int i=1; i<=n; i++)scanf("%d",&H[i]);for(int i=1; i<=n; i++)scanf("%d",&P[i]);for(int i=1; i<=n; i++)scanf("%d",&A[i]);for(int i=1; i<=n; i++)scanf("%d",&B[i]);init();int s=0 , t= 2*n+1;for(int i=1; i<=n; i++){addEdg(s , i , 1 , 0 , 0);addEdg(i+n, t , 1 , 0 , 0);}for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(P[j]/A[i]+(P[j]%A[i]!=0? 1:0)<=H[i]/B[j]+(H[i]%B[j]!=0?
1:0)){ if(i==j) addEdg(i,j+n,1,valu[i],1); else addEdg(i,j+n,1,valu[i],0); } else{ if(i==j) addEdg(i,j+n,1,-valu[i],1); else addEdg(i,j+n,1,-valu[i],0); } int maxcost=0; int ans=minCost_maxFlow(s , t , maxcost, t+1); if(maxcost<=0) printf("Oh, I lose my dear seaco!\n"); else printf("%d %.3f%%\n",maxcost,100.0*ans/n); } }
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！