#include<set> #include<queue> #include<algorithm> #include<cmath> #include<iostream> #include<vector> using namespace std; const int INF = 0xFFFFFFF; const int maxn = 51; int n,m,k; struct Node{ int x,y; Node(){ x=y=0;} Node(int _x,int _y){ x=_x,y=_y;} }; set<int>p[26]; Node person[51],post[26]; double d[26]; bool canUse[26]; void test(){ for(int i=0;i<m;i++) if(canUse[i]) { printf("邮局%d的村民有 ：",i+1); for(set<int>::iterator it=p[i].begin();it!=p[i].end();it++) printf("%d ",*it+1); printf(" 总距离%lf ",d[i]); } } double dis(int index1,int index2) { Node house = person[index1]; Node po = post[index2]; int x1=house.x,y1=house.y; int x2=po.x,y2=po.y; double sum = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1); return sqrt(sum); } int findMinPost(int index) //找到最近的邮局的编号（可用的邮局） { Node temp=person[index];//找到这个人的最近可用邮局 double MIN = INF; int u = -1; for(int i=0;i<m;i++) { if(canUse[i]) { if(dis(index,i)<MIN) { u=i; MIN=dis(index,i); } } } return u; } int main(void) { int x,y; cin>>n>>m>>k; for(int i=0;i<n;i++) { cin>>x>>y; person[i].x=x,person[i].y=y; } for(int i=0;i<m;i++) { cin>>x>>y; canUse[i]=true; post[i].x=x,post[i].y=y; } for(int i=0;i<n;i++) { int pos=findMinPost(i); p[pos].insert(i); } for(int i=0;i<m;i++) { d[i]=0; for(set<int>::iterator it=p[i].begin();it!=p[i].end();it++) { d[i]+=dis(*it,i); } } //test test(); for(int i=0;i<m-k;i++)//删除m-k个邮局 { printf("第%d次删除 ",i+1); int u=-1,MIN=INF; for(int j=0;j<m;j++) if(canUse[i]) { if(p[j].size()<MIN) { u=j,MIN=p[j].size(); } else if(p[j].size()==MIN) { if(d[j]>d[u]) { u=j; MIN=p[j].size(); } } } canUse[u]=false; for(set<int>::iterator it=p[u].begin(); it != p[u].end();it++) { int pos=findMinPost(*it); p[pos].insert(*it); d[pos]+=dis(*it,pos); } test(); printf(" "); } for(int i=0;i<m;i++) if(canUse[i]) printf("%d ",i+1); return 0; }
</pre>AC思路（dfs+剪枝）：dfs最重要的就是建立搜索树，这里每个点都有两种状态，如果直接暴力时间肯定很长，所以需要加上剪枝，我们可以将村子的住户还有备用邮局看作是两个集合，就像普利姆的思路一样，总的思路就是更新最短距离数组，我们先将所有的点全部连接在第一个备用邮局，也可以不连第一个，毕竟每个点有两种状态，如果第二个备用邮局到住户的距离足以更新最短距离数组，那就更新之后寻找下一个邮局，如果不足以更新最短距离数组，我们就直接放弃这个点，显然他是没有用的，找到k个邮局之后就判定一下话费，是否更短，如果是，更新序号数组 [cpp] view plaincopyprint? #include<iostream> #include<stdlib.h> #include<math.h> using namespace std; int n,m,k,j,c[55][2],y[27][2],d[12],f1,f2,f[55]={0}; float yc[27][55],s=1000000000; int dfs(int t,int i,int o[12],float w[55],float sum) { if(i<=m+1) { if(t==k) { if(sum<s) { s=sum; for(j=0;j<k;j++) d[j]=o[j]; } } else if(i<=m&&t<k) { float ww[55]; for(j=1;j<=n;j++) ww[j]=w[j]; dfs(t,i+1,o,w,sum); f1=1,f2=0; if(!f[i]) { o[t]=i; if(t>0) { f2=1; for(j=1;j<=n;j++) { if(ww[j]>yc[i][j]) { sum=sum-ww[j]+yc[i][j]; ww[j]=yc[i][j]; f1=0; } } } else { for(j=1;j<=n;j++) { sum+=yc[i][j]; ww[j]=w[j]=yc[i][j]; } } if(f1&&f2) { f[i]=1; dfs(t,i+1,o,w,sum); } else dfs(t+1,i+1,o,ww,sum); } } } } int main() { int i,j,o[12]; float w[55],ww[55]; cin>>n>>m>>k; for(i=1;i<=n;i++) cin>>c[i][0]>>c[i][1]; for(i=1;i<=m;i++) { cin>>y[i][0]>>y[i][1]; for(j=1;j<=n;j++) yc[i][j]=sqrt((c[j][0]-y[i][0])*(c[j][0]-y[i][0])+(c[j][1]-y[i][1])*(c[j][1]-y[i][1])); } dfs(0,1,o,w,0); for(i=0;i<k;i++) cout<<d[i]<<" "; return 0; }
/* #include<iostream> #include<algorithm> using namespace std; int main() { int a[]={1,2,3,4,5,6}; sort(a,a+6); do { for(int i=0;i<6;i++) cout<<a[i]; cout<<endl; }while(next_permutation(a,a+6)); return 0; } */ #include<iostream> #include<algorithm> using namespace std; int main() { int a[]={1,2,3,4,5,6}; sort(a,a+6); reverse(a,a+6); do { for(int i=0;i<6;i++) cout<<a[i]; cout<<endl; }while(prev_permutation(a,a+6)); return 0; }