あの変な式から二分探索を察する。
無駄に要素詰め込み感が満載だけど、影の秘密を解く足がかりにはなると思います。Time Limitが改善されるのを願ってやまない。
#include<stdio.h> #include<algorithm> #include<queue> #include<vector> #include<string.h> using namespace std; namespace MCF { } int x[110]; int y[110]; int p[10]; int f[10]; int X[10]; int Y[10]; int ABS(int i){return max(i,-i);} int a,b,c; int calc(int d,int i){ int ret=999999999; //for(int i=0;i<(1<<b);i++){ int hu=0; int tmp=0; for(int j=0;j<b;j++)if(i&(1<<j)){ hu+=p[j]; tmp+=f[j]+d*c; } if(hu<a)return ret; MCF::init(a+b+2); int s=a+b; int t=a+b+1; for(int j=0;j<a;j++){ MCF::ae(s,j,1,0); for(int k=0;k<b;k++){ if(i&(1<<k)) MCF::ae(j,a+k,1,max(0,ABS(x[j]-X[k])+ABS(y[j]-Y[k])-d)); } } for(int j=0;j<b;j++)if(i&(1<<j))MCF::ae(a+j,t,p[j],0); MCF::solve(s,t,a); tmp+=MCF::toc; ret=min(ret,tmp); //} return ret; } int main(){ while(scanf("%d%d%d",&a,&b,&c),a){ for(int i=0;i<a;i++){ scanf("%d%d",x+i,y+i); } for(int i=0;i<b;i++){ scanf("%d%d%d%d",X+i,Y+i,p+i,f+i); } int ret=999999999; for(int k=0;k<(1<<b);k++){ int L=-1; int R=4010; while(L+1<R){ int M=(L+R)/2; int v1=calc(M,k); int v2=calc(M+1,k); ret=min(ret,min(v1,v2)); if(v1>v2){ L=M; }else{ R=M; } } } printf("%d\n",ret); } }