2012天津网络赛的1004
本来以为有什么好方法的，初看感觉是网络流可是不知道怎么建图，然后sphinx和我说可能是状态压缩，但是我状态压缩的复杂度有点高，是2的30次方，绝对超时，然后觉得这题实在想不出来去网上搜了一下发现真的有人用状态压缩过了，觉得有点不可思议，我敲了一下没想到也过了。。。c++的输入输出无任何优化156ms1y，有点假，这难道就是昨天那么多队水过这题的原因吗。。。
#include<iostream>#include<vector>#include<algorithm>#include<cstdio>#include<queue>#include<stack>#include<string>#include<map>#include<set>#include<cmath>#include<cassert>#include<cstring>#include<iomanip>using namespace std;#ifdef _WIN32#define i64 __int64#define out64 "%I64d\n"#define in64 "%I64d"#else#define i64 long long#define out64 "%lld\n"#define in64 "%lld"#endif/************ for topcoder by zz1215 *******************/#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)#define FFF(i,a) for( int i = 0 ; i < (a) ; i ++)#define FFD(i,a,b) for( int i = (a) ; i >= (b) ; i --)#define S64(a) scanf(in64,&a)#define SS(a) scanf("%d",&a)#define LL(a) ((a)<<1)#define RR(a) (((a)<<1)+1)#define pb push_back#define MAX(a,b) ((a)>(b)?(a):(b))#define MIN(a,b) ((a)<(b)?(a):(b))#define CL(Q) while(!Q.empty())Q.pop()#define MM(name,what) memset(name,what,sizeof(name))#define read freopen("in.txt","r",stdin)#define write freopen("out.txt","w",stdout)const int inf = 0x3f3f3f3f;const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;const double oo = 10e9;const double eps = 10e-9;const double pi = acos(-1.0);const int maxn = 22;const int maxs = 1<<16;int w[maxs+1];int f[maxs+1];int n,m;int way[maxn][maxn];int x[maxn];int y[maxn];int c[maxn];int dp[maxs+1];vector<int>v;int bt(int x){return x&(-x);}int getway(int a,int b){int re;re = ceil(sqrt(double((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))));return re;}void dfs(int tot,int s,int now=0,int cost=0,int x=0,int step=0){if(cost >= dp[s]) return ;if(x == s){dp[s] = min(dp[s],cost);return ;}else{if(step==tot-1){dfs(tot,s,0,cost+way[now][0],s,step+1);}else{for(int i=1;i<n;i++){if(s&(1<<i) && !(x&(1<<i))){dfs(tot,s,i,cost+way[now][i],x|(1<<i),step+1);}}}}}void floyd(){for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){way[i][j] = min(way[i][j],way[i][k]+way[k][j]);}}}return ;}void start(){f[0]=0;w[0]=0;v.clear(); for(int i=0;i<n;i++) { f[1<<i]=c[i]; }for(int i=1;i<(1<<n);i++){f[i]=f[i-bt(i)]+f[bt(i)];if(f[i]<=m){w[i]=1;v.pb(i);}else{w[i]=inf;}}int now,temp;for(int i=1;i<(1<<n);i++){for(int u=0;u<v.size();u++){now = v[u];if(!(~i & now) ){temp = i-now;w[i] = min(w[i],w[temp]+1);}}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){way[i][j] = getway(i,j);}}floyd();dp[0]=0;for(int i=1;i<(1<<n);i++){dp[i]=inf;}for(int i=0;i<v.size();i++){now = v[i] | 1;temp = 0;for(int j=1;j<=now;j<<=1){if(now&j){temp++;}}dfs(temp,now);}int seed = (1<<n)-2;for(int i=1;i<(1<<n);i++){if(!(i&1)) continue;for(int u=0;u<v.size();u++){now = v[u] | 1;if(!(~i & now)){temp = i - now + 1;dp[i] = min(dp[i],dp[temp]+dp[now]);}}}return ;}int main(){bool ok;while(cin>>n>>m){ok = true;for(int i=0;i<n;i++){cin>>x[i]>>y[i];}for(int i=0;i<n;i++){cin>>c[i];if(c[i]>m){ok = false;}}if(ok == false){cout<<"-1 -1"<<endl;}else{start();cout<<w[(1<<n)-1]<<" "<<dp[(1<<n)-1]<<endl;}} return 0;}