题解 | lxy的通风报信

lxy的通风报信：原题链接。

题意：

     给你n*m的地图，地图上有a个军队和b个敌人，求怎么样花费最少的总路径，将地图上所有的军队连接，如果能的话，输出最小花费，不能则输出No。

注：题目只给出n*m的地图，a和b均未给出

做题思路：

     本题的数据很小加上要求最短路径总量，解决方法很显然是生成最小树，但用二维做最小生成树很麻烦，所以先找出军队并给予每个军队编号，转为一维。

定义和查找编号：

//定义二维矩阵中军队的编号和查找
int getid(int x,int y){
	//当有值时返回编号 
	if (g.count({x,y}))return g[{x,y}];
	//没有说明还在查找阶段，给予点编号并返回 
	int id=g.size()+1;
	g[{x,y}]=id;
	return id;
}

读取地图，判断地图上军队的个数：

	/*
        记录军队的坐标 
		vector<pair<int,int>>a;
    */
	cin >>n>>m;
	for (int i=1;i<=n;i++)
	{
		cin >>mp[i]+1;
		for (int j=1;j<=m;j++)
		{
			if (mp[i][j]=='*')
			{
            	//记录军队总量 
				a.push_back({i,j});
				getid(i,j);
				++top;
			}
		}
	}

     由此我们可以得到给个军队的坐标，并给予编号，此时生成最小数的编号有了，但点到点之间的距离还不知道，要找到一个军队到其他军队的最小路径，本文采用bfs进行查找。

//bfs部分 
//创建数据类型 
struct Index{
	int x,y,step;
};
//移动方式 
int dir[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
//判断点是否在图内,是否碰壁,是否经过 
bool ismp(int x,int y){
	return x<1 || y<1 || x>n || y>m || mp[x][y]=='#' || vis[x][y]; 
}
//经典bfs，找当前点到每个军队之间的距离 
void bfs(int sx,int sy){
	//每次查找重新初始话化vis 
	for (int i=1;i<=n;i++)
	{
        for (int j=1;j<=m;j++)vis[i][j] = 0;
    }
    //以下套用bfs模板
	queue<Index>q;
	q.push({sx,sy});
	vis[sx][sy]=1;
	while(q.size())
	{
        Index now,next;
		now=q.front();
		q.pop();
		for (int i=0;i<4;i++)
		{
			next.x=now.x+dir[i][0];
			next.y=now.y+dir[i][1];
            next.step=now.step+1; 
			if (ismp(next.x,next.y))continue;
			vis[next.x][next.y]=1;
			//是否为军队的点，是的话加入待生成边 
			if (mp[next.x][next.y]=='*')
			{
                //添加的边为起始点到该点的距离
				add(getid(sx,sy),getid(next.x,next.y),next.step);
			} 
			q.push(next);
		}
	}
} 

     经过上述代码，即可得到每个点之间的最小距离，之后代入最小生成树的模板即可得到答案。

函数代码：

//生成最小树部分 
//定义数据类型 
struct Edge{
	int from,to,w;
	bool operator <(const Edge &t) const
	{
		return w<t.w;
	}
}edges[N*N];
//父类节点 
int f[N*N];
//建立连接边 
void add(int from, int to, int w) {
    edges[edge_cnt].from=from;
    edges[edge_cnt].to=to;
    edges[edge_cnt].w=w;
    ++edge_cnt;
}
//查找父类 
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
//连接边 
void merge(int x,int y){
	int a=find(x);
	int b=find(y);
	if (a!=b)f[b]=a;
}

主代码部分：

	//最小生成树部分 
	sort(edges,edges+edge_cnt);
	//初始化节点 
	for (int i=1;i<=top;i++)f[i]=i;
	//cnt记录建立边的总数
	//ans记录花费的总数 
	int cnt=0,ans=0;
    //经典最小生成树
	for (int i=0;i<edge_cnt && cnt<top-1;i++)
	{
		if (find(edges[i].from)!=find(edges[i].to))
		{
			merge(edges[i].from,edges[i].to);
			ans+=edges[i].w;
			cnt++;
		}
	}

     本题其实不难，主要考点在于bfs和最小生成树的综合应用，但问题是代码很长，在写的时候思路很可能被扰乱，而一旦出错要耗很长时间去修改排查，以下是AC代码。

#include <bits/stdc++.h>
using namespace std; 

const int N=1e3+10;
int n,m;
//记录边的总数 
int edge_cnt=0;
//记录军队的总数 
int top=0;
//记录军队的编号 
map<pair<int,int>,int>g;
//记录军队的坐标 
vector<pair<int,int>>a;
char mp[N][N];
int vis[N][N];

//定义二维矩阵中军队的编号和查找
int getid(int x,int y){
	//当有值时返回编号 
	if (g.count({x,y}))return g[{x,y}];
	//没有说明还在查找阶段，给予点编号并返回 
	int id=g.size()+1;
	g[{x,y}]=id;
	return id;
}
//生成最小树部分 
//定义数据类型 
struct Edge{
	int from,to,w;
	bool operator <(const Edge &t) const
	{
		return w<t.w;
	}
}edges[N*N];
//父类节点 
int f[N*N];
//建立连接边 
void add(int from, int to, int w) {
    edges[edge_cnt].from=from;
    edges[edge_cnt].to=to;
    edges[edge_cnt].w=w;
    ++edge_cnt;
}
//查找父类 
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
//连接边 
void merge(int x,int y){
	int a=find(x);
	int b=find(y);
	if (a!=b)f[b]=a;
}
//bfs部分 
//创建数据类型 
struct Index{
	int x,y,step;
};
//移动方式 
int dir[5][2]={{1,0},{-1,0},{0,1},{0,-1}};
//判断点是否在图内,是否碰壁,是否经过 
bool ismp(int x,int y){
	return x<1 || y<1 || x>n || y>m || mp[x][y]=='#' || vis[x][y]; 
}
//经典bfs，找当前点到每个军队之间的距离 
void bfs(int sx,int sy){
	//每次查找重新初始话化vis 
	for (int i=1;i<=n;i++)
	{
        for (int j=1;j<=m;j++)vis[i][j] = 0;
    }
	queue<Index>q;
	q.push({sx,sy});
	vis[sx][sy]=1;
	while(q.size())
	{
        Index now,next;
		now=q.front();
		q.pop();
		for (int i=0;i<4;i++)
		{
			next.x=now.x+dir[i][0];
			next.y=now.y+dir[i][1];
            next.step=now.step+1;
			//是的话跳过 
			if (ismp(next.x,next.y))continue;
			vis[next.x][next.y]=1;
			//是否为军队的点，是的话加入待生成边 
			if (mp[next.x][next.y]=='*')
			{
                //添加的边为起始点到该点的距离
				add(getid(sx,sy),getid(next.x,next.y),next.step);
			} 
			q.push(next);
		}
	}
} 

int main(){
	cin >>n>>m;
	for (int i=1;i<=n;i++)
	{
		//记录军队有几个 
		cin >>mp[i]+1;
		for (int j=1;j<=m;j++)
		{
			if (mp[i][j]=='*')
			{
				a.push_back({i,j});
				getid(i,j);
				++top;
			}
		}
	}
	//将军队的每个点放入bfs查找该点到其余点的距离 
	for (auto &i:a)bfs(i.first,i.second);
	//最小生成树部分 
	sort(edges,edges+edge_cnt);
	//初始化节点 
	for (int i=1;i<=top;i++)f[i]=i;
	//cnt记录建立边的总数
	//ans记录花费的总数 
	int cnt=0,ans=0;
    //经典最小生成树
	for (int i=0;i<edge_cnt && cnt<top-1;i++)
	{
		if (find(edges[i].from)!=find(edges[i].to))
		{
			merge(edges[i].from,edges[i].to);
			ans+=edges[i].w;
			cnt++;
		}
	}
	if (cnt<top-1)cout <<"No\n";
	else cout <<ans<<"\n";
    return 0;
}