图算法刷题专题

A1013 Battle Over Cities

思路:通过DFS找连通分量的个数。

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
#include <cstdio>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e3+10;

int n, m, k;
int G[N][N] = {0};
bool vis[N] = {false};

void DFS(int u){
    vis[u] = true;
    for (int v = 1; v <= n; v++) {
        if (vis[v] ==false && G[u][v] != 0) {
            DFS(v);
        }
    }
}

int main (int argc, char *argv[])
{
    scanf("%d%d%d", &n, &m, &k);
    int id1, id2;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &id1, &id2);
        G[id1][id2] = G[id2][id1] = 1;
    }
    for (int i = 0; i < k; i++) {
        int num = 0;
        fill(vis, vis + N, false);
        int check;
        scanf("%d", &check);
        vis[check] = true;
        for (int i = 1; i <= n; i++) {
            if (vis[i] == false) {
                num++;
                DFS(i);
            }
        }
        printf("%d\n", num - 1);
    }
    return 0;
}

注意：每个节点都需要遍历

A1021 Deepest Root

思路：并查集查找几个集合即为几个连通分量，从一个节点出发找到最深的节点，再从找到的节点出发找最深的节点，这两部分节点并集即为最深的集合。

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
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 1e4 + 10;

int n;//node num
bool vis[N] = {false};
vector<int> G[N];


int father[N] = {0};
int isRoot[N] = {0};
int findFather(int x){
    if (father[x] == x) {
        return x;
    }
    int F = findFather(father[x]);
    father[x] = F;
    return F;
}

void Union(int a, int b){
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faA] = faB;
    }
}

void init(){
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

int calBlock(){
    int block = 0;
    for (int i = 1; i <= n; i++) {
        isRoot[findFather(i)]++;
    }
    for (int i = 1; i <= n; i++) {
        if (isRoot[i] != 0) {
            block++;
        }
    }
    return block;
}

int maxH = 0;
vector<int> temp, ans;

void DFS(int u, int Height){
    vis[u] = true;
    if (Height > maxH) {
        temp.clear();
        temp.push_back(u);
        maxH = Height;
    }
    else if (Height == maxH) {
        temp.push_back(u);
    }
    for (int i = 0; i < G[u].size(); i++) {
        if (vis[G[u][i]] == false) {
            DFS(G[u][i], Height + 1);
        }
    }
}
int main (int argc, char *argv[])
{
    scanf("%d", &n);
    int a, b;
    init();
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
        Union(a, b);
    }
    int block = calBlock();
    if (block != 1) {
        printf("Error: %d components\n", block);
    }
    else{
        DFS(1, 1);
        ans = temp;
        fill(vis, vis + N, false);
        temp.clear();
        DFS(ans[0], 1);
        for (int i = 0; i < temp.size(); i++) {
            ans.push_back(temp[i]);
        }
        sort(ans.begin(), ans.end());
        printf("%d\n", ans[0]);
        for (int i = 1; i < ans.size(); i++) {
            if (ans[i] != ans[i-1]) {
                printf("%d\n", ans[i]);
            }
        }
    }
    return 0;
}

注意：并查集初始化，isRoot数组的作用是确认根节点， 下标从1开始，每个节点不要搞错。

A1076 Forwards on Weibo

BFS查找小于层数的节点

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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1010;

struct node {
    int v;
    int layer;
};
vector<node>G[N];
bool vis[N] = {false};

int n, l;

int BFS(int u){
    int numForward = 0;
    node root;
    root.v = u;
    root.layer = 0;
    queue<node> Q;
    Q.push(root);
    vis[u] = true;
    while (!Q.empty()) {
        node front = Q.front();
        Q.pop();
        int id = front.v;
        for (int i = 0; i < G[id].size(); i++) {
            node next = G[id][i];
            next.layer = front.layer + 1;
            if (vis[next.v] == false && next.layer <= l) {
                Q.push(next);
                vis[next.v] = true;
                numForward++;
            }
        }
    }
    return numForward;
}

int main (int argc, char *argv[])
{
    scanf("%d%d", &n, &l);
    int k;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k);
        int id;
        for (int j = 0; j < k; j++) {
            scanf("%d", &id);
            node now;
            now.v = i;
            now.layer = 0;
            G[id].push_back(now);
        }
    }
    int numQuery;
    scanf("%d", &numQuery);
    int id2;
    for (int i = 0; i < numQuery; i++) {
        fill(vis, vis + N, false);
        scanf("%d", &id2);
        int num = BFS(id2);
        printf("%d\n", num);
    }
    return 0;
}

A1003 Emergency

思路：Dijkstra算法求最短路径。

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
#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAXV = 510;
const int INF = 1000000000;

int n, m, c1, c2;
int G[MAXV][MAXV], weight[MAXV];
bool vis[MAXV] = {false};
int d[MAXV], w[MAXV], num[MAXV];

void Difkstra(int s){
    fill(d, d + MAXV, INF);
    memset(num, 0, sizeof(num));
    memset(w, 0, sizeof(w));
    d[s] = 0;
    w[s] = weight[s];
    num[s] = 1;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    w[v] = w[u] + weight[v];
                    num[v] = num[u];
                }
                else if (d[u] + G[u][v] == d[v]) {
                    if (w[u] + weight[v] > w[v]) {
                        w[v] = w[u] + weight[v];
                    }
                    num[v] += num[u];
                }
            }
        }
    }
}

int main (int argc, char *argv[])
{
    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for (int i = 0; i < n; i++) {
        scanf("%d", weight + i);
    }
    int u, v, we;
    fill(G[0], G[0] + MAXV * MAXV, INF);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &u, &v, &we);
        G[u][v] = we;
        G[v][u] = we;
    }
    Difkstra(c1);
    printf("%d %d\n", num[c2], w[c2]);
    return 0;
}

1030 Travel Plan

思路:Dijkstra + DFS

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
#include <cstdio>
#include <cstring>
#include <iterator>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const int MAXV = 510;
const int INF = 1000000000;

int n, m, S, D;
int G[MAXV][MAXV], C[MAXV][MAXV];
bool vis[MAXV] = {false};
vector<int>pre[MAXV];
int d[MAXV];

void Dijkstra(int s){
    fill(d, d + MAXV, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) return;
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (d[u] + G[u][v] == d[v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
}
vector<int>tempPath;
vector<int>path;
int optValue = INF;
//v目的节点
void DFS(int v){
    //递归边界
    if (v == S) {
        tempPath.push_back(v);
        int value = 0;
        //边权
        for (int i = tempPath.size() - 1; i > 0; i--) {
            value += C[tempPath[i]][tempPath[i - 1]];
        }
        if (value < optValue) {
            optValue = value;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for (int i = 0; i < pre[v].size(); i++) {
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}

int main (int argc, char *argv[])
{
    scanf("%d %d %d %d", &n, &m, &S, &D);
    int c1, c2;
    fill(G[0], G[0] + MAXV * MAXV, INF);
    fill(C[0], C[0] + MAXV * MAXV, INF);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &c1, &c2);
        scanf("%d%d", &G[c1][c2], &C[c1][c2]);
        G[c2][c1] = G[c1][c2];
        C[c2][c1] = C[c1][c2];
    }
    Dijkstra(S);
    DFS(D);
    for (int i = path.size() - 1; i >= 0; i--) {
        printf("%d ", path[i]);
    }
    printf("%d %d\n", d[D], optValue);
    return 0;
}

注意点：无向图，建立邻接矩阵时，两个方向都有初始化。一些细节处理。记得初始化fill，G[][],d[],vis[]

A1018 Public Bike Management

思路：首先DFS找最短路径，DFS找第二和第三条件最小的

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
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <algorithm>
#include <sys/wait.h>
#include <vector>
using namespace std;
const int N = 510;
const int INF = 1e9;

int G[N][N] = {INF}, carNum[N];
int d[N] = {INF};
vector<int> pre[N];
bool vis[N] = {false};

int c, n, en, m;

void Dijkstra(int s){
    fill(d, d + N, INF);
    d[s] = 0;
    for (int i = 0; i <= n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j <= n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int v = 0; v <= n; v++) {
            if (vis[v] == false && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (d[u] + G[u][v] == d[v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
}

vector<int> path, tempPath;
int minNeed = INF, minRemain = INF;
void DFS(int v){
    if (v == 0) {
        tempPath.push_back(v);
        int need = 0, remain = 0;
        for (int i = tempPath.size() - 1; i >= 0; i--) {
            int id = tempPath[i];
            if (carNum[id] > 0) {
                remain += carNum[id];
            }
            else{
                if (remain > abs(carNum[id])) {
                    remain -= abs(carNum[id]);
                }else {
                    need += abs(carNum[id])- remain;
                    remain = 0;
                }
            }
        }
        if (need < minNeed) {
            minNeed = need;
            minRemain = remain;
            path = tempPath;
        }
        else if (need == minNeed && remain < minRemain) {
            minRemain = remain;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for (int i = 0; i < pre[v].size(); i++) {
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}

int main (int argc, char *argv[])
{
    fill(G[0], G[0] + N * N, INF);
    fill(vis, vis + N, false);
    scanf("%d%d%d%d", &c, &n, &en, &m);
    int car;
    carNum[0] = 0;//开始车站
    for (int i = 1; i <= n; i++) {
        scanf("%d", &car);
        car -= c/2;
        carNum[i] = car;
    }
    int id1, id2, l;    
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &id1, &id2, &l);
        G[id1][id2] = G[id2][id1] = l;
    }
    Dijkstra(0);
    DFS(en);
    printf("%d ", minNeed);
    for (int i = path.size() - 1; i >= 0; i--) {
        printf("%d", path[i]);
        if (i > 0) {
            printf("->");
        }
    }
    printf(" %d\n", minRemain);
    return 0;
}

注意，need和remain那块太难想到了

A1072 Gas Station

思路：Dijkstra + DFS关键要把加油站也加进去，序号在住所后，无需管四舍五入.

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
#include <cstdio>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
const int N = 1020;
const int INF = 1e9;


int n, m, k, Ds;
int G[N][N] = {INF};
int d[N] = {INF};
bool vis[N] = {false};

int change(string str){
    if (str[0] == 'G') {
        str.erase(str.begin());
        return atoi(str.c_str()) + n;
    }
    else return atoi(str.c_str());
}

void Dijkstra(int s){
    fill(d, d + N, INF);
    d[s] = 0;
    for (int i = 1; i <= n + m; i++) {
        int u = -1, MIN = INF;
        for (int j = 1; j <= n + m; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int v = 1; v <= n + m; v++) {
            if (vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}
int main (int argc, char *argv[])
{
    fill(G[0], G[0] + N * N, INF);
    scanf("%d%d%d%d", &n, &m, &k, &Ds);
    string str1, str2;
    int p1, p2, dist;
    for (int i = 0; i < k; i++) {
        cin >> str1 >> str2 >> dist;
        p1 = change(str1);
        p2 = change(str2);
        G[p1][p2] = G[p2][p1] = dist;
    }
    int no = 0;
    int id = -1;
    double max = -1;
    double ave = INF;
    for (int i = n + 1; i <= n + m; i++) {
        double minDis = INF;
        double sum = 0;
        fill(vis, vis + N, false);
        Dijkstra(i);
        for (int j = 1; j <= n; j++) {
            if (d[j] > Ds) {
                no++;
                minDis = -1;
                break;
            }
            else if (d[j] < minDis) {
                minDis = d[j];
            }
            sum += 1.0 * d[j];
        }
        if (minDis > max) {
            max = minDis;
            id = i;
            ave = sum / n;
        }
        else if (minDis == max && sum / n < ave) {
            max = minDis;
            id = i;
            ave = sum / n;
        }
    }
    if (no == m) {
        printf("No Solution\n");
    }
    else {
        printf("G%d\n", id - n);
        printf("%.1f %.1f\n", max, ave);
    }
    return 0;
}

注意，在d[j]>minDis 之后要设定minDis = -1，不然max会被设为INF;

A1087 All Roads Lead to Rome

思路：Dijkstra + DFS,常规思路

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
const int N = 210;
const int INF = 1e9;

int n, k;
string start;
int st;
int G[N][N] = {INF}, happy[N];
int d[N] = {INF};
bool vis[N] = {false};
vector<int> pre[N];

int num = 0;
int ROMIndex = 0;
map<string, int> stringToInt;
map<int, string> intToString;
int change(string str){
    if (stringToInt.find(str) !=  stringToInt.end()) {
        return stringToInt[str];
    }
    else if (str == "ROM") {
        ROMIndex = num;
        stringToInt[str] = num;
        intToString[num] = str;
        return num++;
    }
    else {
        stringToInt[str] = num;
        intToString[num] = str;
        return num++;
    }
}

void Dijkstra(int s){
    fill(d, d + N, INF);
    fill(vis, vis + N, false);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (d[u] + G[u][v] == d[v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
}

int roadNum = 0;
vector<int> tempPath, path;
int maxHappy = -1;
int avgHappy = -1;
void DFS(int v){
    if (v == st) {
        roadNum ++;
        tempPath.push_back(v);
        int value = 0;
        int avg = 0; 
        for (int i = tempPath.size() - 1; i >= 0; i--) {
            value += happy[tempPath[i]];
        }
        avg = value / (tempPath.size() - 1);
        if (value > maxHappy) {
            maxHappy = value;
            avgHappy = avg;
            path = tempPath;
        }
        else if (value == maxHappy && avg > avgHappy) {
            avgHappy = avg;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    tempPath.push_back(v);
    for (int i = 0; i < pre[v].size(); i++) {
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}

int main (int argc, char *argv[])
{
    fill(G[0], G[0] + N * N, INF);
    scanf("%d%d", &n, &k);
    cin >> start;
    st = change(start);
    happy[st] = 0;
    string strId;
    int happyValue;
    for (int i = 0; i < n - 1; i++) {
        cin >> strId >> happyValue;
        happy[change(strId)] = happyValue;
    }
    string id1, id2;
    int cost;
    for (int i = 0; i < k; i++) {
        cin >> id1 >> id2 >> cost;
        G[change(id1)][change(id2)] = cost;
        G[change(id2)][change(id1)] = cost;
    }
    Dijkstra(0);
    DFS(ROMIndex);
    printf("%d %d %d %d\n", roadNum, d[ROMIndex], maxHappy, avgHappy);
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << intToString[path[i]];
        if (i != 0) {
            cout <<  "->";
        }
    }
    return 0;
}

注意：下标啊，检查了半小时，总是搞错。happy[tempPath[i]] 写成happy[i]检查半天，不然一遍过了.

赏

谢谢你请我吃糖果

支付宝

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

stay hungry,stay foolish<br>keep walking,keep thinking<br><br><br>数码爱好者<br>技术探寻者<br>生活领悟者<br>永远保持对新事物的热情<br><br><br>浙江工业大学的本科生<br>邮箱联系:201906062230@zjut.edu.cn<br>QQ:272181284