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 1789 Truck History

计算出每两车牌照字符差异数,然后prim

POJ 1789
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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
char s[2002][10];
long long map[2002][2002], dist[2002], t, ans;
bool vis[2002];

void prim(long long u)
{
long long i, j, min, tmp;
ans = 0;
for(i = 1; i <= t; i++)
{
dist[i] = map[u][i];
vis[i] = false;
}
vis[u] = true;
for(i = 1; i <= t; i++)
{
min = 0x7FFFFFFF;
for(j = 1; j <=t; j++)
if(!vis[j] && min > dist[j])
{
min = dist[j];
tmp = j;
}
if(min != 0x7FFFFFFF)
ans += min;
vis[tmp] = true;
for(j = 1; j <= t; j++)
if(!vis[j] && map[tmp][j] < dist[j])
dist[j] = map[tmp][j];

}

}

int main()
{
long long i, j, k, cou;
while(~scanf("%lld", &t) && t)
{
for(i = 1; i <= t; i++)
scanf("%s", s[i]);
for(i = 1; i <= t; i++)
for(j = 1; j <= t; j++)
map[i][j] = 0x7FFFFFFF;
for(i = 1; i <= t; i++)
for(j = 1; j <= t; j++)
if(i != j)
{
cou = 0;
for(k = 0; k < 7; k++)
if(s[i][k] != s[j][k])
cou++;
map[i][j] = map[j][i] = cou;
}
prim(1);
printf("The highest possible quality is 1/%lld.\n", ans);
}
return 0;
}

POJ 2421 Constructing Roads

克鲁斯卡尔裸题

POJ 2421
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

typedef struct lin{
int a;
int b;
int len;
} lin;

int n, map[110][110];
lin le[225000];
int parent[225000], q;
int rank[225000];

void makeset(int n)
{
for(int i = 0; i < n; i++)
{
parent[i] = i;
rank[i] = 0;
}
}

int getparent(int x)
{
if(parent[x] == x)
return x;
else
{
parent[x] = getparent(parent[x]);
return parent[x];
}
}

bool cmp(lin p, lin q)
{
return p.len < q.len;
}

void unionset(int x, int y)
{
if(rank[x] > rank[y])
parent[y] = x;
else
{
parent[x] = y;
if(rank[x] == rank[y])
++rank[y];
}
}

int main()
{
int a, b, ans = 0, i, j, count, k;
while(~scanf("%d", &n))
{
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d", &map[i][j]);
scanf("%d", &q);
for(i = 0; i < q; i++)
{
scanf("%d%d", &a, &b);
map[a][b] = map[b][a] = 0;
}
k = 0;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if(j < i)
{
le[k].a = i;
le[k].b = j;
le[k++].len = map[i][j];
}
sort(le, le + k, cmp);
makeset(n);
count = 0;
for(i = 0; i < k; i++)
{
int x = getparent(le[i].a);
int y = getparent(le[i].b);
if(x != y)
{
unionset(x, y);
count++;
ans += le[i].len;
if(count == n - 1)
break;
}
}
printf("%d\n", ans);
q = 0;
count = 0;
ans = 0;
}
return 0;
}

POJ 2485 Highways

prim 裸题

POJ 2485
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
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
long long n, ans;
long long map[510][510], dist[510];
bool vis[510];

void prim(long long u)
{
long long i, j, tmp, min;
ans = -1;
for(i =1; i <= n; i++)
{
dist[i] = map[u][i];
vis[i] = false;
}
vis[u] = true;
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)
if(min > ans) ans = min;
vis[tmp] = true;
for(j = 1; j <= n; j++)
if(!vis[j] && dist[j] > map[tmp][j])
dist[j] = map[tmp][j];
}
return;
}

int main()
{
long long t, i, j;
scanf("%lld", &t);
while(t--)
{
scanf("%lld", &n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%lld", &map[i][j]);
for(i = 1; i <= n; i++)
map[i][i] = 0x7FFFFFFF;
prim(1);
printf("%lld\n", ans);
}
return 0;
}

POJ 1094 Sorting It All Out

基本拓扑排序,具体拓扑排序就是每次找出图中入度为零的点,然后删去与其相连的边,再寻找新的入度为零的点,不断处理,找出点的顺序就是拓扑排序的顺序。

POJ 1094
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
70
71
72
73
74
//By Brickgao
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

int map[50][50], t[50], d[50], ans[50];
int n, m, flag1;
char s[10];

int topu()
{
int i, j, flag2 = 1, p, tmp, k = 0;
for(i = 0; i < n; i++)
t[i] = d[i];
for(i = 0; i < n; i++)
{
p = 0;
for(j = 0; j < n; j++)
if(t[j] == 0)
{
p++;
tmp = j;
}
if(p == 0 && p != n) return 0;
if(p > 1) flag2 = -1;
ans[k++] = tmp;
t[tmp] = -1;
for(j = 0; j < n; j++)
if(map[tmp][j] == 1)
t[j] --;
}
return flag2;
}

int main()
{
int i, p, j;
while(~scanf("%d%d", &n, &m))
{
if(m == 0 && n == 0) break;
flag1 = 0;
memset(map, 0, sizeof(map));
memset(d, 0, sizeof(d));
for(i = 0; i < m; i++)
{
scanf("%s", s);
map[s[0] - 'A'][s[2] - 'A'] = 1;
d[s[2] - 'A']++;
if(flag1 == 0)
p = topu();
if(p == 1 && flag1 == 0)
{
printf("Sorted sequence determined after %d relations: ", i + 1);
for(j = 0; j < n; j++)
printf("%c", ans[j] + 'A');
printf(".\n");
flag1 = 1;
}
if(p == 0 && flag1 == 0)
{
printf("Inconsistency found after %d relations.\n", i + 1);
flag1 = 1;
}
}
if(flag1 == 0)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}