dfs一直不知道怎么写，可还是要练习。

这道题题意：n台电脑，分成两个集合，不同的集合交流需要时间，求最大的时间。

思想：遍历全部可能，最开始可以把所有电脑看作一个集合，然后一个一个移动到另个集合，试着找到最大时间，dfs最是适合。

#include<cstdio>
#include<cstring>int map[30][30];
int visit[30];
int ans,n;void dfs(int di,int date)
{int temp = date;visit[di] = 1;for(int i = 1;i <= n; i++){if(visit[i] == 0)temp += map[i][di];elsetemp -= map[i][di];}if(temp > ans)ans = temp;for(int i = di + 1;i <= n; i++){dfs(i,temp);visit[i] = 0;}
}int main()
{//  freopen("in.txt","r",stdin);while(scanf("%d",&n) != EOF){memset(visit,0,sizeof(visit)); //初始都在集合0中ans = 0;for(int i = 1;i <= n; i++)for(int j = 1;j <= n; j++)scanf("%d",&map[i][j]);dfs(1,0);printf("%d\n",ans);}return 0;
}

很明显没有减枝的dfs容易超时。

但是减枝需要思考，可以说是需要神来之笔。

减枝：如果某台电脑放入1中，temp(移动某个电脑之后的需要的时间)>date(上一个状态的需要的时间)，那么就默认这台电脑就在1中不再回溯移动它。

#include<cstdio>
#include<cstring>int map[30][30];
int visit[30];
int ans,n;void dfs(int di,int date)
{int temp = date;visit[di] = 1;for(int i = 1;i <= n; i++){if(visit[i] == 0)temp += map[i][di];elsetemp -= map[i][di];}if(temp > ans)ans = temp;for(int i = di + 1;i <= n; i++){if(temp > date){  //减枝dfs(i,temp);visit[i] = 0;}}
}int main()
{
//    freopen("in.txt","r",stdin);while(scanf("%d",&n) != EOF){memset(visit,0,sizeof(visit));ans = 0;for(int i = 1;i <= n; i++)for(int j = 1;j <= n; j++)scanf("%d",&map[i][j]);dfs(1,0);printf("%d\n",ans);}return 0;
}