http://acm.hdu.edu.cn/showproblem.php?pid=3315
题意:
有S1到Sn这n个勇士要和X1到Xn这n个勇士决斗,初始时,Si的决斗对象是Xi. 如果Si赢了Xi,那么你将获得Vi分,否则你将获得-Vi分. Si和Xi对决时,Si有初始生命Hi,初始攻击Ai, Xi有初始生命Pi,初始攻击Bi. 且Si先出手,然后Xi失去Ai生命,之后如果Xi没死,那么Xi出手,Si失去Bi生命. 直到有一方的生命值<=0时,决斗结束.
现在要你重新安排S和X的决斗顺序,使得你能获得的分最多.如果有多个最优解,你要选取那个维持初始决斗顺序最多的解。
思路:
这道题目就是一个二分图的最佳完美匹配。
对于题目要求的维持初始决斗顺序最多的解,先将每条边的权值扩大1000倍,如果该边是原来的匹配的话,则在自加1。扩大这么多倍的原因是为了维持原先的大小关系。这样一来就会优先选择原先匹配。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 500 + 5; 17 18 struct Max_Match 19 { 20 int n; 21 int W[maxn][maxn]; 22 int Lx[maxn],Ly[maxn]; //顶标 23 bool S[maxn],T[maxn]; //S[i]和T[i]左/右第i个点是否已标记 24 int left[maxn]; //left[i]为右边第i个点的编号 25 26 bool match(int i) 27 { 28 S[i]=true; 29 for(int j=1;j<=n;j++) if(Lx[i]+Ly[j]==W[i][j] && !T[j]) 30 { 31 T[j]=true; 32 if(left[j]==-1 || match(left[j])) 33 { 34 left[j]=i; 35 return true; 36 } 37 } 38 return false; 39 } 40 41 void update() 42 { 43 int a=1<<30; 44 for(int i=1;i<=n;i++)if(S[i]) 45 for(int j=1;j<=n;j++)if(!T[j]) 46 a=min(a, Lx[i]+Ly[j]-W[i][j]); 47 for(int i=1;i<=n;i++) 48 { 49 if(S[i]) Lx[i] -=a; 50 if(T[i]) Ly[i] +=a; 51 } 52 } 53 54 int solve(int n) 55 { 56 this->n=n; 57 memset(left,-1,sizeof(left)); 58 for(int i=1;i<=n;i++) 59 { 60 Lx[i]=Ly[i]=0; 61 for(int j=1;j<=n;j++) 62 Lx[i]=max(Lx[i], W[i][j]); 63 } 64 65 for(int i=1;i<=n;i++) 66 { 67 while(true) 68 { 69 memset(S,0,sizeof(S)); 70 memset(T,0,sizeof(T)); 71 if(match(i)) break; 72 else update(); 73 } 74 } 75 //计算最大权值和 76 int ans=0; 77 for(int i=1;i<=n;i++) ans+=W[left[i]][i]; 78 return ans; 79 } 80 }KM; 81 82 int n; 83 int v[maxn]; 84 int h[maxn],p[maxn]; 85 int a[maxn],b[maxn]; 86 87 int judge(int i,int j) 88 { 89 int hpi=h[i],hpj=p[j]; 90 while(hpi && hpj) 91 { 92 hpj-=a[i]; 93 if(hpj<=0) return v[i]; 94 hpi-=b[j]; 95 if(hpi<=0) return -v[i]; 96 } 97 } 98 99 int main() 100 { 101 //freopen("in.txt","r",stdin); 102 while(~scanf("%d",&n) && n) 103 { 104 for(int i=1;i<=n;i++) scanf("%d",&v[i]); 105 for(int i=1;i<=n;i++) scanf("%d",&h[i]); 106 for(int i=1;i<=n;i++) scanf("%d",&p[i]); 107 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 108 for(int i=1;i<=n;i++) scanf("%d",&b[i]); 109 110 for(int i=1;i<=n;i++) 111 for(int j=1;j<=n;j++) 112 { 113 KM.W[i][j]=judge(i,j); 114 KM.W[i][j]*=1000; 115 if(i==j) KM.W[i][j]+=1; 116 } 117 118 int ans = KM.solve(n); 119 if(ans/1000<=0) puts("Oh, I lose my dear seaco!"); 120 else 121 { 122 printf("%d %.3f%% ",ans/1000,100.*(ans%1000)/n); 123 } 124 } 125 return 0; 126 }