题意:给矩阵,ij表示i-j的距离是c,现问0-n个点怎么分配到两个集合中使A集合到B集合的总距离最大
分析,搜索DFS
#include<stdio.h>
#include<string.h>
const int MAXN=30;
int map[MAXN][MAXN];
int n,ans;
int vis[MAXN];
void DFS(int cur)//搜n次,挨个点枚举
{
int i,j;
int sum=0;
if(cur==n)
{
return ;
}
for(i=0;i<n;i++)
{
if(vis[i])
{
for(j=0;j<n;j++)
{
if(!vis[j])
{
sum+=map[i][j];
}
}
}
}
if(sum>ans) ans=sum;
vis[cur]=1;
DFS(cur+1);
vis[cur]=0;
DFS(cur+1);
}
int main()
{
int T,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&map[i][j]);
}
}
memset(vis,0,sizeof(vis));
ans=0;
DFS(0);
printf("%d\n",ans);
}
return 0;
}
#include<stdio.h>
#include<string.h>
const int MAXN=30;
int map[MAXN][MAXN];
int vis[MAXN];
int n;
int ans;
int total;
void DFS(int cur)//已点进入A或B集合进行搜索
{
int i;
if(cur==n)
{
if(ans<total)
{
ans=total;
}
return ;
}
int sum=0;
for(i=0;i<cur;i++)//当cur在false集合中
{
if(vis[i]==true)
{
sum+=map[cur][i];
}
}
total+=sum;
DFS(cur+1);
total-=sum;
vis[cur]=true;
sum=0;
for(i=0;i<cur;i++)//当cur在true集合中
{
if(vis[i]==false)
{
sum+=map[cur][i];
}
}
total+=sum;
DFS(cur+1);
vis[cur]=false;
total-=sum;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
ans=0;
total=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&map[i][j]);
}
}
memset(vis,0,sizeof(vis));
DFS(0);
printf("%d\n",ans);
}
return 0;
}