Judges' response

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 454    Accepted Submission(s): 256

3 3
0 0
0 3
0 1
0
1
2

3 2
0 0
0 3
0 1
0
1
2

3 1
0 0
0 3
0 1
0
1
2
　　
16 35
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11

1 6
2 8
-1 -1
8 467

题意：

给定n个地点的坐标和每个地点的权值，点有点权边有边权。现在裁判在点1，需要分配这些裁判到这些点去，已知每个裁判能够到点权之和不大于m，而且一个点不能由两个裁判访问。现在给出两个问题，1、最少几个裁判可以覆盖所有点 2、给定无数个裁判，怎么样访问这些点使得总边权和最小，裁判访问完必须回到1点，而且一个裁判访问的点权之和不能超过m。

思路:

第一个问题很简单。由于有问题的人最多16个。可以把一个裁判可以解决的问题壮压。对应位置为1表示该裁判会解决对应问题。然后这就抽象成一个物品了。然后背出全为1的状态就行了。比赛时就因为第一问简单就傻乎乎的写了。看懂第二问时就凌乱了。于是参考了下大神的博客，才知道那是MTSP(多旅行商问题)。不过用DP的方法极限数据时用了12s。。。只能说题目数据太水了。。。不过第二问的思路蛮经典的。又一次进行了抽象。把一个裁判从解决完问题到回到1点的最短用时抽象为一个物品。然后一样的背包。对于最短用时可以壮压DP求出。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<time.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
int  n,m,cnt,ans1,ans2,lim;
int x[20],y[20],c[20];
int state[1<<17];//存可行状态
int dp[1<<17],dis[20][20];//dp处理最少的裁判数
int dpp[20][1<<17],mind[1<<17];//dpp[i][j]表示当前在i点。访问状态为j时的最小距离。
//clock_t st,ed;               //mind[i]表示完成访问状态i所走的最少路程
//double dur;
bool isok(int st)//判断一个裁判的可行状态。抽象为一个物品。
{
    int i=0,sum=0;

    while(st)
    {
        if(st&1)
            sum+=c[i];
        st>>=1;
        i++;
    }
    if(sum<=m)
        return true;
    else
        return false;
}
void getDist()//求距离
{
    int i,j,xx,yy;
    for(i=0;i<n;i++)
    {
        dis[i][i]=0;
        for(j=i+1;j<n;j++)
        {
            xx=x[j]-x[i];
            yy=y[j]-y[i];
            dis[i][j]=dis[j][i]=ceil(sqrt((double)(xx*xx+yy*yy)));
        }
    }
}
void TSP()//典型的单旅行商问题
{
    int s,j,ns;
    memset(dp,0x3f,sizeof dp);
    dp[0]=0;
    for(s=0;s<lim;s++)
    {
        if(dp[s]==INF)
            continue;
        for(j=0;j<cnt;j++)
        {
            if(s&state[j])
                continue;
            ns=s|state[j];
            dp[ns]=min(dp[ns],dp[s]+1);
        }
    }
    ans1=dp[lim-1];
}
void MTSP()//多旅行商
{
    int i,j,k,s,ns;
    getDist();
    memset(dpp,0x3f,sizeof dpp);
    memset(mind,0x3f,sizeof mind);
    dpp[0][1]=0;//0必须为起点
    for(i=0;i<cnt;i++)
    {
        s=state[i];
        for(j=0;j<n;j++)
        {
            if(s&(1<<j)&&dpp[j][s]!=INF)//枚举起点
            {
                mind[s]=min(mind[s],dpp[j][s]+dis[j][0]);//把一个裁判完成访问状态再回到0点抽象为一个物品
                for(k=0;k<n;k++)
                {
                    if(s&(1<<k))
                        continue;
                    ns=s|(1<<k);//ns状态不一定有效
                    dpp[k][ns]=min(dpp[k][ns],dpp[j][s]+dis[j][k]);
                }
            }
        }
    }
    for(s=1;s<lim;s++)//大神的方法。感觉(s-1)&比较巧妙。得到的状态一定是1比s少的状态。
    {
        if(s&1)       //递推就是从1少的状态推1多的状态
        {
            for(ns=(s-1)&s;ns;ns=(ns-1)&s)
                mind[s]=min(mind[s],mind[ns|1]+mind[(s-ns)|1]);
        }
    }
    /*这是我的DP方法极限数据18s。。汗。。
    for(s=0;s<lim;s++)//把抽象后的物品直接背包
    {
        if(mind[s]==INF)//由于mind原本的值不会影响后面结果。所以不用初始化
            continue;
        for(i=0;i<cnt;i++)
        {
            if(state[i]&1)
            {
                if((s-1)&(state[i]-1))
                    continue;
                ns=s|state[i];
                mind[ns]=min(mind[ns],mind[s]+mind[state[i]]);
            }
        }
    }
    */
    ans2=mind[lim-1];
}
int main()
{
    int i,ma;

    while(~scanf("%d%d",&n,&m))
    {
        for(i=0;i<n;i++)
            scanf("%d%d",&x[i],&y[i]);
        ma=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&c[i]);
            ma=max(ma,c[i]);
        }
        if(ma>m)
        {
            printf("-1 -1\n");
            continue;
        }
        //st=clock();
        cnt=0,lim=1<<n;
        for(i=0;i<lim;i++)
            if(isok(i))
                state[cnt++]=i;
        TSP();
        MTSP();
        //ed=clock();
        //dur=(double)(ed-st)/CLOCKS_PER_SEC;
        //printf("time: %.2lf\n",dur);
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}
/*
3 3
0 0
0 3
0 4
0
2
2
3 2
0 0
0 3
1 0
0
1
2
3 1
0 0
0 3
0 1
0
1
2
4 9
1 2
1 3
2 1
3 1
0
5
6
4
16 3500
30 40
37 52
49 49
52 64
31 62
52 33
42 41
52 41
57 58
62 42
42 57
27 68
43 67
58 48
58 27
37 69
0
19
30
16
23
11
31
15
28
8
8
7
14
6
19
11

output:
2 14
2 8
-1 -1
2 11
1 164
*/