Graph theory

POJ-2195 Going Home

题目传送门: POJ 2195

给一张图,图上标记号小人与房子,小人的数目等于房子的数目,要求每个小人都走入不同的房子,小人能够水平或者竖直移动,每移动一格花费一,可以走过房子而不进入,问最小的花费。

KM模板题,用最大权匹配做,把边权变为负值就变成了最小权匹配。

POJ-3026 Borg Maze

题目传送门: POJ 3026

题目大概意思是#是墙,不能走,S是起点,A是目标点,要求从S出发走到所有点,路径不可交叉,然后求最小的路径和。

就是一个BFS+MST的题,自己BFS写的有问题,真是够糟糕的。。。

POJ-3020 Antenna Placement

题目传送门:POJ 3020

题意就是用圈来圈,求用多少圈能把圈完。

属于最大独立集问题,开始不知道这个,想了半天Orz。

最大独立集的定义是图中两两互不相邻的顶点构成的集合。

有个结论是最大独立集+最小覆盖集=V,而最小覆盖集=最大匹配,所以我们可匈牙利算法来做这个题。

POJ-3041 Asteroids

题目传送门:POJ 3041

题意为给你一个N*N的矩阵以及所有矩阵中小行星的位置,现在要用炸弹消灭所有的小行星,每个炸弹每次只能炸一行或者一列,求最少用多少炸弹能够消灭所有的小行星。这道题属于最小点覆盖问题。

图论中覆盖的含义是用一些顶点(或边)的集合,使得图中的每一条边(多一个顶点)都至少接触几何中的一个顶点(边)。

最小点覆盖问题就是用最少的点覆盖所有的边。

这里就有一个有趣的定理了……König定理:最小覆盖点数 == 最大匹配数

POJ-最小生成树和拓扑排序基础问题

POJ 1258 Agri-Net

prim 裸题

POJ 1258
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//by Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define out(v) cerr << #v << ": " << (v) << endl
#define SZ(v) ((int)(v).size())
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
long long map[110][110], dist[110], n, ans;
bool vis[110];
void prim(long long u)
{
long long i, j, min, tmp;
ans = 0;
for(i = 1; i <= n; i++)
{
dist[i] = map[u][i];
vis[i] = false;
}
vis[u] = true;
tmp = u;
for(i = 1; i <= n; i++)
{
min =0x7FFFFFFF;
for(j = 1; j <= n; j++)
if(!vis[j] && min > dist[j])
{
tmp = j;
min = dist[j];
}
if(min != 0x7FFFFFFF)
ans += min;
vis[tmp] = true;
for(j = 1; j <= n; j++)
if(!vis[j] && dist[j] > map[tmp][j])
dist[j] = map[tmp][j];
}
}
int main()
{
long long i, j;
while(~scanf("%lld", &n))
{
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%lld", &map[i][j]);
prim(1);
printf("%lld\n",ans);
}
return 0;
}

POJ-基本最短路问题

POJ 1062 昂贵的聘礼

中文题,dijkstra基本运用

POJ 1062
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
int M, N, lev[110];
int dis[110], map[110][110];
bool vis[110];
void dijstra(int m, int n)
{
int i, k;
int min;
memset(vis, false, sizeof(vis));
memset(dis, 999999999, sizeof(dis));
vis[0] = true;
for(i = 0; i <= N; i++)
if(lev[i] >= m && lev[i] <= n)
dis[i] = map[0][i];
k = 0;
while(1)
{
min = 999999999;
for(i = 0; i <= N; i++)
if(lev[i] >= m && lev[i] <= n && !vis[i] && min > dis[i])
{
min = dis[i];
k = i;
}
vis[k] = true;
if(k == 1)
return;
for(i = 0; i <= N; i++)
if(lev[i] >= m && lev[i] <= n && !vis[i] && dis[i] > dis[k] + map[k][i])
{
dis[i] = dis[k] + map[k][i];
}
}
}
int main()
{
int i, j, k, t, p;
memset(map, 127, sizeof(map));
cin >> M >> N;
int ans = 999999999;
for(i = 1; i <= N; i++)
{
scanf("%d%d%d", &map[0][i], &lev[i], &k);
for(j = 1; j <= k; j++)
{
scanf("%d%d", &t, &p);
map[t][i] = p;
}
}
for(i = lev[1] - M; i <= lev[1]; i++)
{
dijstra(i, i + M);
if(ans > dis[1])
ans = dis[1];
}
cout << ans << endl;
return 0;
}