poj2976
裸。。直接二分
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int k,n;
double A[1010],B[1010],C[1010];
double f(double x){int i;double ans=0;for(i=1;i<=n;i++) C[i]=B[i]*x-A[i];sort(C+1,C+1+n);for(i=1;i<=k;i++) ans+=C[i];return ans;
}
int main(){int i;while(scanf("%d%d",&n,&k)!=EOF){if(n+k==0) break;k=n-k;for(i=1;i<=n;i++) scanf("%lf",&A[i]);for(i=1;i<=n;i++) scanf("%lf",&B[i]);double l=0,r=1e18,mid;while(l+1e-5<r){mid=(l+r)/2;if(f(mid)<0) l=mid;else r=mid;}mid*=100;long long ans=mid+0.5;printf("%lld\n",ans);}return 0;
}
bzoj4819 新生舞会
题面很裸的分数规划。。直接二分，问题就成了求每次二分的最大（小）匹配权值，所以直接km。。
#include<stdio.h>
#include<iostream>
#include<queue>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int N=500;
double inf=1e18;
double e=1e-6;
struct KM{double hl[N],hr[N],slk[N],a[N][N];int fl[N],fr[N],vl[N],vr[N],pre[N],q[N],l,r,n;int check(int i){vl[i]=1;if(fl[i]){q[++r]=fl[i];vr[fl[i]]=1;return 1;}for(;i;swap(i,fr[pre[i]])) fl[i]=pre[i];return 0;}void bfs(int s){int i,j;double d;for(i=1;i<=n;i++){slk[i]=inf;vl[i]=vr[i]=0;}l=r=0;q[r]=s;vr[s]=1;while(1){while(l<=r){j=q[l++];for(i=1;i<=n;i++){d=hl[i]+hr[j]-a[i][j];if(vl[i]==0&&slk[i]>=d){pre[i]=j;if(fabs(d)>e) slk[i]=d;else if(!check(i)) return;}}}d=inf;for(i=1;i<=n;i++)if(!vl[i]&&d>slk[i]) d=slk[i];for(i=1;i<=n;i++){if(vl[i]) hl[i]+=d;else slk[i]-=d;if(vr[i]) hr[i]-=d;}for(i=1;i<=n;i++) if(!vl[i]&&slk[i]==0&&!check(i)) return;}}double ask(){int i,j;for(i=1;i<=n;i++){fl[i]=fr[i]=hr[i]=0;hl[i]=-inf;}for(i=1;i<=n;i++) for(j=1;j<=n;j++) hl[i]=max(a[i][j],hl[i]);for(j=1;j<=n;j++) bfs(j);double ans=0;for(i=1;i<=n;i++) ans+=a[i][fl[i]];return ans;}
}km;int A[110][110],B[110][110];
double f(double x,int n){int i,j;km.n=n;for(i=1;i<=n;i++) for(j=1;j<=n;j++) km.a[i][j]=-B[i][j]*x+A[i][j];return -km.ask();
}int main(){int i,j,n;scanf("%d",&n);for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&A[i][j]);for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&B[i][j]);double l=0,r=1e9,mid;while(l+1e-10<r){mid=(l+r)/2;if(f(mid,n)<0) l=mid;else r=mid;}printf("%.6f\n",mid);return 0;
}