家访（图论建模）

第1题     家访 查看测评数据信息

小明的老师应为小明平时的表现，要去小明家家访，小明所住的城市可看做一个二维网格，其中字符#表示障碍，‘.’表示空地。小明的老师住在左上角(1,1)，小明住在右下角(n,m)。小明的老师要去小明家玩。小明的老师如果走到空地侧不需要任何代价，但是如果要走到障碍点则他需要先摧毁该障碍。每次可以走到相邻的四个方向之一，即从(x,y)可以走到(x+1,y),(x-1,y),(x,y+1),(x,y-1)。小明的老师可以花费C[i]的代价将第i列的所有障碍都消灭。请帮小明的老师计算她去小明家最少需要多少代价。

输入格式

第一行两个正整数n,m,表示网格图的大小

接下来n行，每行m个字符，描述网格图，字符仅由‘.’和‘#’组成，保证起点一定是空地

接下来一行m个数，表示C[i]

1<=n,m<=100,1<=C[i]<=1e5

输出格式

输出一个整数

输入/输出例子1

输入：

4 4

.##.

.#.#

.###

..#.

5 3 9 4

输出：

7

样例解释

消除第2列和第4列的障碍，总代价为7

建模：要如何抽象的变成图论，如何建图

可以借助虚拟点（代表某些特定的点，比如代表指定一列的点）完成一些复杂度较高的操作。

方法1：

建完图之后跑个最短路就好了

建图：
对于每一个非障碍点，可以向四周连边，没障碍边权就是0，有障碍边权是a[到四周的那一列]，因为你想要从上一个点到达四周的新点，且新点这里有障碍，你就得先破除新点的障碍，所以破除花费就是新点处在的列。

但是我们发现，对于同一列，如果相邻三个点都有障碍，这个时候从第一个点到第二个点，然后从第二个点到第三个点，就会花费两倍破这一列墙的花费，但是实际上只用花费一次这一列的破墙操作，这样可以把整列破掉。我们想要处理一下怎么防止重复算。

我们可以对于每一列，每个点都向每个点连一条边权是a[这一列]的边，但这样复杂度就超限了

我们想，能不能用一个点，代表这一列的所有点，我们称为特殊点，然后这样就只需要这个特殊的点和这一列的点有关系就行了。

对每一列建立一个虚拟点，虚拟点向这一列连边，边权0，就可以有效解决。

但是虚拟点不能只有出度，什么点可以进入虚拟点？

前一列向虚拟点连边，边权a[这一列]，这样也同时确保了不会算多破墙操作的花费

但是注意一下，第一列前面没有列了，那只能是第一列每个点向虚拟点连边了。

#include <bits/stdc++.h>
using namespace std;
const int N=505, M=101, M2=250000;

struct node
{
	int v, w;
	bool operator <(const node &A) const
	{
		return w>A.w;
	};
};
int n, m, w[N], dis[N*N], vis[N*N];
int dx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0};
char c[N][N];
vector<node> a[N*N*2];
priority_queue<node> q;
void dij()
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[1*M+1]=0;
	q.push({1*M+1, 0});
	
	while (!q.empty())
	{
		int u=q.top().v;
		q.pop();
		
		if (vis[u]) continue;
		vis[u]=1;
		
		for (int i=0; i<a[u].size(); i++)
		{
			int v=a[u][i].v, w=a[u][i].w;
			if (dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({v, dis[v]});
			}
		}
	}
}
int main()
{
//	freopen("1.in", "r", stdin);
	
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++) cin>>c[i][j];
	
	for (int i=1; i<=m; i++) scanf("%d", &w[i]);
	
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			for (int k=0; k<4; k++)
			{
				int nx=i+dx[k], ny=j+dy[k];
				if (nx>=1 && nx<=n && ny>=1 && ny<=m)
				{
					if (c[nx][ny]=='.') a[i*M+j].push_back({nx*M+ny, 0});
					else a[i*M+j].push_back({nx*M+ny, w[ny]});
				}
			}
	
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
		{
			if (j==1) a[i*M+j].push_back({j+M2, w[j]});
		    else a[i*M+j-1].push_back({j+M2, w[j]});
			a[j+M2].push_back({i*M+j, 0});
		}
	
	//for (int i=1; i<=n; i++) a[i*m+1].push_back({1+M2, w[1]});
	dij();
	
	printf("%d", dis[n*M+m]);
	return 0; 
} 
/*
4 3
.##
#..
##. 
...
1 2 3
*/

方法2：
贪心思想
破这一列的障碍后，肯定不会往回走，因为可以直接到这一列的任意位置
建一个大点，代表这列的所有点

入度：这一列全部点，上一列全部点，边权a[这一列]
出度：下一列可走点，边权0

两个差不多了，看懂方法一这个就ok了