Guapi

最短路/最小生成树

C - Borg Maze POJ - 3026

BFS+最小生成树

比赛的时候想到了用 bfs求出每个点之间的最短距离，然后跑一遍MST。

可是想想复杂度高达 $O(n^2m^2)$ ,然后放弃了。赛后看题解，确实是这种做法，比赛的时候还是要大胆一些

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<map>
    using namespace std;
    const int N = 50 + 10;
    const int inf = 0x3f3f3f3f;
    int n, m;
    int fa[N*N];
    int a[N][N];
    int get(int x)
    {
    	if (x == fa[x])  return x;
    	return fa[x] = get(fa[x]);
    }
    struct E
    {
    	int u, v, w;
    	bool operator<(const E &other){
    		return w < other.w;
    	}
    }edge[N*N*N*N];
    int tot,cas;
    int d[N][N];
    const int dx[4] = { 0, 0, -1, 1 }, dy[4] = { 1, -1, 0, 0 };
    typedef pair<int, int > P;
    void bfs(int x,int y)
    {
    	memset(d, -1, sizeof(d));
    	d[x][y] =0;
    	queue<P> q;
    	q.push(P(x, y));
    	int cnt = 1;
    	while (!q.empty())
    	{
    		P cur = q.front();
    		q.pop();
    		for (int i = 0; i < 4; i++)
    		{
    			int nx = cur.first+ dx[i], ny = cur.second + dy[i];
    			if (nx >= 1 && nx <= n&&ny >= 1 && ny <= m&&d[nx][ny] == -1&&a[nx][ny]>=0)
    			{
    				d[nx][ny] = d[cur.first][cur.second] + 1;
    				q.push(P(nx, ny));
    				if (a[nx][ny]>0)
    				{
    					edge[tot].u = a[x][y];
    					edge[tot].v = a[nx][ny];
    					edge[tot].w = d[nx][ny];
    					tot++;
    					cnt++;
    					if (cnt >= cas) return;
    				}
    			}
    		}
    	}
    }
    void kru()
    {
    	sort(edge, edge + tot);
    	for (int i = 1; i <= cas; i++)
    		fa[i] = i;
    	int ans = 0;
    	int k = 0;
    	for (int i = 0; i < tot; i++)
    	{
    		int u = edge[i].u, v = edge[i].v;
    		if (get(u) != get(v))
    		{
    			fa[get(u)] = get(v);
    			ans += edge[i].w;
    		}
    	}
    	cout << ans << endl;
    
    }
    int main()
    {
    	int t;
    	cin >> t;
    	while (t--)
    	{
    		tot = 0;
    		cas = 0;
    		cin >> m >> n;
    		char s[N];
    		gets(s);
    		for (int i = 1; i <= n; i++)
    		{
    			for (int j = 1; j<= m; j++)
    			{
    				char c = getchar();
    				if (c == ' ') a[i][j] = 0;
    				else if (c == '#') a[i][j] = -1;
    				else a[i][j] = ++cas;
    			}
    			getchar();
    		}
    		for (int i = 1; i <= n; i++)
    		{
    			for (int j = 1; j <= m; j++)
    			{
    				if (a[i][j] > 0)
    					bfs(i, j);
    			}
    		}
    		kru();
    	}
    	return 0;
    }

[========]

D - 0 or 1 HDU - 4370

比赛的时候不会，赛后看题解也是挺懵的。
这题把C矩阵看成邻接表， $C_{ij}$ 表示 i到j之间的距离，把 $X_{ij}$ 看成 i到j之间的关系， $X_{ij}$ 为1则表示i和j之间有一条路，并且权值为 $C_{ij}$
这样我们求从1到n的最短路就可以得到 $\sum C{ij} * X{ij}$ ，为什么这样是正确的呢？
我们把每行每列(邻接表) 看成是图的一个顶点，我们可以观察到第一行的出度就是1，最后一列的入度是1，其他点的出度和入度均为1

表示点 1 的出度为 1
表示点 n 的入度为 1
除了点 1 和点 n 外的其他点出入度相等

可以画一下，发现从一个点u到另一个点v就是邻接表 C[u][v] ,这样会使第V列多一个1，然后我们下次再从第V行出发在找下一个点，这样第V行也就多一个1，这样就满足了题目要求的关系。
然后还有一种情况，那就是可以从点 1 出发到达其他点然后又回到点 1 形成一个环，同样也可以从点 n 出发回到点 n。这样也是符合条件的，答案为从 1 出发的最小权值环和从 n 出发的最小权值环之和。
最后比较两种情况的最小值
求环，注意最开始不是将起点 s 入队，而是把与起点相连的点加入队列，将 dis[s] 设为 inf 这样可以求得从 s 出发回到 s 的最小环，具体参考代码。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 310;
const int inf = 0x3f3f3f3f;
int dis[N];
bool vis[N];
int a[N][N],n;
void spfa(int st)
{
	queue<int> q;
	memset(vis, false, sizeof(vis));
	memset(dis, inf, sizeof(dis));
	for (int i = 1; i <= n; i++)
	{
		if (i == st)
		{
			dis[i] = inf;
		}
		else
		{
			q.push(i);
			vis[1] = true;
			dis[i] = c[st][i];
		}
	}
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for (int v = 1; v <= n; v++)
		{
			if (dis[v] > dis[u] + c[u][v])
			{
				dis[v] = dis[u] +c[u][v];
				if (!vis[v])
				{
					vis[v] = true;
					q.push(v);
				}
			}

		}


	}
}
int main()
{
	while (scanf("%d", &n)!=EOF)
	{
		
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				scanf("%d", &c[i][j]);
		}
		spfa(1);
		int c1 = dis[1], ans = dis[n];
		spfa(n);
		int c2 = dis[n];
		ans = min(ans, c1 + c2);
		cout << ans << endl;

	}
	return 0;
}

E - Extended Traffic LightOJ - 1074

spfa判负环，把负环上的点标记一下，不要想当然的认为有负环所有点都要被标记，负环只是所有点形成的图的一部分，还有就是不要忘了in[v]++,赛场上这个地方没写超时了，也没来得及发现

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 2e5 + 10;
const int N = 2e2 + 10;
const int inf = 0x3f3f3f3f;
struct E{
	int to, next, w;
}edge[M];
int head1[N], tot;
int dis1[N], in[N];
bool vis[N], vis1[N];
int n, m, cas;
int a[N];
void addedge(int from, int to, int w)
{
	edge[++tot].to = to;
	edge[tot].w = w;
	edge[tot].next = head1[from];
	head1[from] = tot;
}
void dfs(int u)
{
	vis1[u] = true;
	for (int i = head1[u]; i != -1; i = edge[i].next)
	{
		if (!vis1[edge[i].to])
			dfs(edge[i].to);
	}
}
bool spfa1()
{
	int h = 0, t = 0;
	queue<int> q;
	memset(dis1, inf, sizeof(dis1));
	memset(vis, false, sizeof(vis));
	memset(vis1, false, sizeof(vis1));
	memset(in, 0, sizeof(in));
	dis1[1] = 0;
	q.push(1);
	in[1]++;
	vis[1] = true;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		if (vis1[u]) continue;
		for (int i = head1[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			
			int w = edge[i].w;
			if (dis1[v]> dis1[u] + w)
			{
				dis1[v] = dis1[u] + w;
				if (!vis[v])
				{
					vis[v] = true;
					q.push(v);
					in[v]++;
					if (in[v] > n) vis1[v]=true;
				}
			}
		}
	}
	return true;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tot = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			head1[i] = -1;
		}
		cin >> m;
		while (m--)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			int w = (a[v] - a[u])*(a[v] - a[u])*(a[v] - a[u]);
			addedge(u, v, w);
		}
		bool f=spfa1();
		printf("Case %d:\n", ++cas);
		int q;
		scanf("%d", &q);
		while (q--)
		{
			int vv;
			scanf("%d", &vv);
			if (vis1[vv] || dis1[vv] == inf || dis1[vv] < 3)
			{
				puts("?");
			}
			else
			{
				printf("%d\n", dis1[vv]);
			}


		}
	}


	return 0;
}

F - The Unique MST POJ - 1679

这题判断最小生成树是否唯一，用kruskal 加边的时候如果两个顶点在一个集合中了，判断已加入的顶点集合中是否存在和当前边权值相同的边，有就是不唯一。可以把加入集合中的点建一颗树，然后搜索进行判断。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
const int N = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int fa[N];
int get(int x)
{
	if (x == fa[x])  return x;
	return fa[x] = get(fa[x]);
}
struct E
{
	int u, v, w;
	bool operator<(const E &other){
		return w < other.w;
	}
}edge[N*N];
int tot;
int a[N];
typedef pair<int, int> P;
vector<P> g[N];
bool dfs(int v, int u,int pre, int c,bool f)
{
	for (int i = 0; i < g[v].size(); i++)
	{
		if (g[v][i].first == pre) continue;
		if (g[v][i].second == c)  f = true;
		if (f&&g[v][i].first == u) return true;
		if	(dfs(g[v][i].first, u, v, c, f)) return true;
	}
	return false;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
			g[i].clear();
		cin >> m;
		tot = 0;
		bool f = true;
		while (m--)
		{
			int i, j, w;
			cin >> i >> j >> w;
			edge[tot].w = w;
			edge[tot].u = i;
			edge[tot].v = j;
			tot++;
		}
		sort(edge, edge + tot);
		for (int i = 1; i <= n; i++)
			fa[i] = i;
		int ans = 0;
		int k = 0;
		for (int i = 0; i < tot; i++)
		{
			if (k >= n - 1) break;
			int u = edge[i].u, v = edge[i].v;
			if (get(u) != get(v))
			{
				g[u].push_back(P(v, edge[i].w));
				g[v].push_back(P(u, edge[i].w));
				fa[get(u)] = get(v);
				ans += edge[i].w;
			}
			else
			{
				
				if (dfs(u, v, -1, edge[i].w, false)) {
					f = false;
					break;
				}
				
			}
		}
		if (f)
			printf("%d\n", ans);
		else
			printf("Not Unique!\n");
	}
	return 0;
}

总结:比赛的时候一定要细心，有思路的时候要尝试去实现它！！！多刷题。

最短路/最小生成树

评论