HDU 4281 Judges' response（12年天津 MTSP问题）
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：给出N个人，其中0号是裁判的位置，剩下有N-1的人提问，裁判需要去回答问题，每个人有一个val，每个裁判能拿到的val的上限为K。问题最少需要几个裁判，以及最少时间
http://acm.hdu.edu.cn/showproblem.php?pid=4281
第一问可以状态压缩DP解决，dp[i]表示状态i需要几个裁判，也可以排序之后贪心。从大到小，尽可能地装入一个盒子。
第二问就是多个TSP问题，dp[i][j]表示当前位置 在i，可行状态为j的最小费用，best[i]表示对于状态i的最小费用（而且是一个完整状态，裁判都回到原点），因为之前TSP中是求的可行状态，也就是每个裁判的上限不能超过K。之后就是枚举所有状态，对于一个状态，枚举他的所有子集，见代码中的位运算部分。而且两个子集中必须要包含0号结点，因为每个裁判都是从0出发的
可以看这个博客：http://blog.csdn.net/woshi250hua/article/details/7961869
#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<algorithm>#include<set>#define inf 1<<28#define M 100005#define N 55#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define MOD 1000000007using namespace std;struct Point{int x,y;}p[20];int n,m,val[20],path[20][20];int dp[16][1<<16];int best[1<<16],ok[1<<16];int dist(Point p1,Point p2){return ceil(sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));}void Get_dist(){for(int i=0;i<n;i++) for(int j=0;j<n;j++) path[i][j]=dist(p[i],p[j]);}void Init(){for(int i=0;i<n;i++)for(int j=0;j<(1<<n);j++)dp[i][j]=inf;for(int i=0;i<(1<<n);i++)best[i]=inf;dp[0][1]=0;}int check(int state){int sum=0;for(int i=0;i<n;i++)if(state&(1<<i))sum+=val[i];return sum<=m;}bool cmp(int a,int b){return a>b;}int slove(){int v[20];memcpy(v,val,sizeof(val));sort(v,v+n,cmp);if(v[0]>m) return -1;int flag[20];mem(flag,0);int cnt=0;for(int i=0;i<n;i++){if(flag[i]) continue;int tmp=0;for(int j=i;j<n;j++){if(flag[j]==0){if(tmp+v[j]<=m){flag[j]=1;tmp+=v[j];}}}cnt++;}return cnt;}int TSP(){for(int i=0;i<(1<<n);i++){if(ok[i])for(int j=0;j<n;j++)if(i&(1<<j)){best[i]=min(best[i],dp[j][i]+path[j][0]);for(int k=0;k<n;k++)if(!(i&(1<<k)))dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+path[j][k]);}}for(int i=0;i<(1<<n);i++)if(i&1)for(int j=i&(i-1);j;j=i&(j-1))best[i]=min(best[i],best[j]+best[(i-j)|1]);return best[(1<<n)-1];}int main(){while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);for(int i=0;i<n;i++) scanf("%d",&val[i]);for(int i=0;i<(1<<n);i++) ok[i]=check(i);Get_dist();Init();int ans1=slove();if(ans1==-1) {printf("-1 -1\n");continue;}printf("%d %d\n",ans1,TSP());}return 0;}