某国家一共有 n 座城市，有的城市与城市与城市之间有路相连，所有的路都是无向的， n 个城市可以通过道理相互达到，其中 2k 座城市是重要城市，国王希望把这 2k 座城市两两配对，形成 k 对友好城市。
友好城市之间常常需要进行交流，因此国王希望友好城市之间的距离不要太长，于是他定义两个城市 u，v 配对的代价为 u，v 之间最短路的长度，2k 座城市配对的总代价为 k 对城市配对的代价和。
国王想知道配对的最小代价。
数据范围： 
， 
或 
， 
， 
[编程题]友好城市
- 热度指数：851 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行输入一个数 n ，表示城市个数。 接下来输入一个 n*n 的邻接矩阵 A ， A[i][j] 表示城市 i 和 城市 j 之间边的长度，如果 A[i][j] = -1，表示 i 和 j 之间没有直接相连的边，输入保证 A[i][j] = A[j][i] ，A[i][i] = -1 ，且 n 个城市相互连通。 最后输入一个数 k ，接下来一行 2k 个数，这 2k 个重要城市的编号
输出描述:
输出一个数，最小匹配代价
示例1
输入
4 -1 2 -1 10 2 -1 3 -1 -1 3 -1 1 10 -1 1 -1 2 1 2 3 4
输出
3
// 弗洛伊德求最短路径,回溯法遍历所有可能
import java.io.*;
public class Main{
private static int res = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] graph = new int[n][n];
String[] strs;
for(int i = 0; i < n; i++){
strs = br.readLine().split(" ");
for(int j = 0; j < n; j++)
graph[i][j] = Integer.parseInt(strs[j]);
}
int k = Integer.parseInt(br.readLine());
strs = br.readLine().split(" ");
int[] cities = new int[k<<1];
for(int i = 0; i < (k<<1); i++)
cities[i] = Integer.parseInt(strs[i])-1;
br.close(); strs = null;
floyd(graph,n);
backTrace(graph,cities,0,0,k);
System.out.println(res);
}
private static void floyd(int[][] graph, int n){
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
// 注意更新后对角线仍然为-1
// graph[i][j] == -1的时候无条件更新
if(graph[i][k] != -1 && graph[k][j] != -1 && ( graph[i][j] == -1 || graph[i][k] + graph[k][j] < graph[i][j]))
graph[i][j] = graph[i][k] + graph[k][j];
}
private static void backTrace(int[][] graph, int[] cities, int index, int tmp, int k){
if(index == (k<<1) && res > tmp) {res = tmp; return;}
// 从index+1开始遍历
int temp;
for(int i = index+1; i < (k<<1); i++){
// swap(index+1,i)
temp = cities[index+1];
cities[index+1] = cities[i];
cities[i] = temp;
if(graph[cities[index]][cities[index+1]] != -1) // 可以相同的时候才回溯
backTrace(graph,cities,index+2,tmp+graph[cities[index]][cities[index+1]],k);
// swap换回来
temp = cities[index+1];
cities[index+1] = cities[i];
cities[i] = temp;
}
}
}
发表于 2019-05-26 20:57:51
回复(0)
#include <bits/stdc++.h>
using namespace std;
int n, k, a[101][101], b[101], Min=INT_MAX;
void DFS(int cnt, int s){
if(cnt==2*k){
Min = min(Min, s);
return;
}
for(int i=cnt+1;i<2*k;i++){
swap(b[i], b[cnt+1]);
DFS(cnt+2, s+a[b[cnt]][b[cnt+1]]);
swap(b[i], b[cnt+1]);
}
}
int main(){
scanf("%d", &n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d", &a[i][j]);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j && a[i][k]!=-1 && a[k][j]!=-1){
if(a[i][j]==-1)
a[i][j] = a[i][k] + a[k][j];
else
a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
}
scanf("%d", &k);
for(int i=0;i<2*k;i++)
scanf("%d", &b[i]);
DFS(0, 0);
printf("%d\n", Min);
return 0;
}
发表于 2020-09-15 00:12:03
回复(0)
/**
floyd完后，需要枚举这2k个点的k种边的组合。
对每条边，只需要固定起点，枚举终点即可。
因为起点和终点互换后还是相同的边。
注释部分掉的部分写的比较啰嗦，因为对全排列不太熟悉。
**/
/**
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static int[][] A;
private static int[] cities;
private static int result = Integer.MAX_VALUE;
private static int k;
static boolean[] vis;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
A = new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
A[i][j] = in.nextInt();
if(A[i][j] == -1)A[i][j] = 0x3f3f3f3f;
}
}
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
A[i][j] = Math.min(A[i][j],A[i][k]+A[k][j]);
}
}
}
k = in.nextInt();
cities = new int[2*k];
for(int i=0;i<2*k;i++)cities[i] = in.nextInt()-1;
vis = new boolean[16];
dfs(0,new ArrayList<>());
System.out.println(result);
}
//枚举第k条边时，所选的边集为t
static void dfs(int i,ArrayList<Integer> t){
if(i==k){
int cur = 0;
for(int s=0;s<2*k;s+=2){//计算答案
cur+=A[t.get(s)][t.get(s+1)];
}
result = Math.min(cur,result);
return;
}
int s = 0; //找到一个没使用过的作为起点
for(;s<2*k;s++){
if(!vis[s])break;//边的起点
}
vis[s]=true;
t.add(cities[s]);
for(int j=0;j<2*k;j++){//枚举边的终点
if(vis[j])continue;
vis[j] = true;
t.add(cities[j]);
dfs(i+1,t);//枚举下一条边。
vis[j]=false;
t.remove(t.size()-1);
}
vis[s] = false;
t.remove(t.size()-1);
}
}
**/
import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static int[][] A;
private static int[] cities;
private static int result = Integer.MAX_VALUE;
private static int k;
static int vis;
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strs;
A = new int[n][n];
for (int i = 0; i < n; i++) {
strs = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
A[i][j]=Integer.parseInt(strs[j]);
if (A[i][j] == -1)A[i][j] = 0x3f3f3f3f;
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][j] = Math.min(A[i][j], A[i][k] + A[k][j]);
}
}
}
k = Integer.parseInt(br.readLine());
strs = br.readLine().split(" ");
cities = new int[k<<1];
for (int i = 0; i < 2 * k; i++)cities[i] = Integer.parseInt(strs[i])-1;
vis = (1<<2*k)-1;
dfs(0, 0);
System.out.println(result);
}
/**
枚举k条边,vis 0代表访问过 1 代表没访问过
*/
static void dfs(int i, int cur) {
if (cur >= result) return;
if (i == k) {
result = Math.min(cur, result);
return;
}
int s = 0;
//vis 最近的1
s = Integer.numberOfTrailingZeros(vis);
vis-=(1<<s);
for (int j = s+1; j < 2 * k; j++) {
if (((vis>>j)&1)==0)continue;
vis-=(1<<j);
cur += A[cities[s]][cities[j]];
dfs(i + 1, cur); //枚举下一条边。
vis+=(1<<j);
cur -= A[cities[s]][cities[j]];
}
vis+=(1<<s);
}
}
编辑于 2024-03-05 01:17:26
回复(0)
#include<bits/stdc++.h>
using namespace std;
int getDis(vector<int>& tmp,int k,vector<vector<int>>& graph){
int ans = 0;
for(int i=0;i<2*k;i+=2){
ans+=graph[tmp[i]][tmp[i+1]];
}
return ans;
}
void dfs(int cur,vector<int>& vis,vector<int>& tmp,int& dis,int k,vector<vector<int>>& graph,vector<int>& v){
if(cur>=2*k){
int r = getDis(tmp,k,graph);
if(r<dis)
dis = r;
return;
}
for(int i=0;i<2*k;++i){
if(!vis[i])
{
vis[i]=1;
tmp.push_back(v[i]);
dfs(cur+1,vis,tmp,dis,k,graph,v);
vis[i]=0;
tmp.pop_back();
}
}
}
void DFS(int s,int cost,vector<int>& v,int k,int& dis,vector<vector<int>>& graph){
if(s==2*k){
dis = min(dis,cost);
return;
}
for(int i=s+1;i<2*k;++i)
{
swap(v[i],v[s+1]);
DFS(s+2,cost+graph[v[s]][v[s+1]],v,k,dis,graph);
swap(v[i],v[s+1]);
}
}
int main(){
int n;
cin>>n;
vector<vector<int>>graph(n+1,vector<int>(n+1,0));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
cin>>graph[i][j];
int k;
cin>>k;
vector<int>v(2*k,0);
for(int i=0;i<2*k;++i) cin>>v[i];
// Floyd多源最短路径
for(int K=1;K<=n;++K)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
if(graph[i][K]!=-1&&graph[K][j]!=-1){
if(graph[i][j]==-1)
graph[i][j]=graph[i][K]+graph[K][j];
else graph[i][j]=min(graph[i][j],graph[i][K]+graph[K][j]);
}
}
// dfs遍历这2k个城市 相当于求2k个城市的全排列
// 将相邻的两个城市进行两两配对
int dis = INT_MAX;
vector<int>vis(2*k,0);
vector<int>tmp;
//dfs(0,vis,tmp,dis,k,graph,v);
DFS(0,0,v,k,dis,graph);
cout<<dis<<endl;
return 0;
}
发表于 2020-06-19 21:11:33
回复(0)
/*思想就是：先BFS求出友好城市到达各个城市的最短距离，然后DFS搜索k对城市的最短距离*/
#include<iostream>
#include<queue>
#include<math.h>
#include<vector>
#include<algorithm>
#include<limits.h>
using namespace std;
int n,k;
long int A[103][103];
long long int path[103][103]={0};
int friends[103];
int result1 =INT_MAX;
void BFS(int ***r /> {
queue<pair<int,int> > q;
pair<int ,int> b(0,s);
q.push(b);
while(!q.empty())
{
int p=q.front().second;
int l=q.front().first; //记录上一次查询的路径和
q.pop();
for(int i=1;i<=n;i++)
{
if(A[p][i] == -1 ||s ==i)
continue;
if(path[s][i] >l+ A[p][i])
{
path[s][i] =path[s][p]+A[p][i];
pair<int ,int> bc(l+ A[p][i],i);
q.push(bc);
}
}
}
};
void DFS(int s,int sum)
{
if(s == 2*k+1)
{
if(sum<result1)
result1=sum;
}
else
{
for(int i=s+1;i<=2*k;i++)
{
swap(friends[i],friends[s+1]); //这是比较简单的方式，通过循环交换的形式，实现不同点的相加
DFS(s+2,sum+path[friends[s]][friends[s+1]]);
swap(friends[i],friends[s+1]);
}
}
};
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cin>>A[i][j];
}
cin>>k;
for(int i=1;i<=2*k;i++)
{
cin>>friends[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
path[i][j]=INT_MAX;
}
}
for(int i=1;i<=2*k;i++)
{
path[friends[i]][friends[i]]=0;
BFS(friends[i]);
}
DFS(1,0);
cout<<result1;
return 0;
}
发表于 2019-05-21 21:23:21
回复(0)
问题信息
难度：
5条回答
24收藏
2366浏览
通过挑战的用户
查看代码-
2022-09-01 10:14:59
-
2022-08-26 10:52:08
-
2022-08-23 15:48:29 -
2022-08-16 21:55:57 -
2022-07-24 21:04:24
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
