www.acmicpc.net/problem/2273

 

2273번: 줄 서기

첫째 줄에 N(1≤N≤256), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

www.acmicpc.net

키를 비교한 두 학생의 번호 u, v가 주어집니다.

d[u][v] : u가 v보다 앞에서야하는 경우

이는 방향그래프이며 인접행렬을 만들어주고 플로이드로 상대적인 키 정보를 구합니다.

 

그리고 이중for를 돌리면서 d[i][j] = true이고, d[j][i] = true인 것을 찾아줍니다.

d[i][j]=true이면 i가 j보다 앞에 있어야한다는 뜻인데

d[j][i]=true이면 j가 i보다 앞에 있어야한다는 뜻이므로 둘다 true면 모순입니다. 이때는 -1을 출력하고 리턴합니다.

 

확인이 끝났으면 왼쪽 경계 값(l = 1), 오른쪽 경계 값(r = N)으로 두고 1번학생부터 확인합니다.

d[i][j]=true이면 i보다 뒤에 있어야하는 학생이 1명 추가됩니다. => r--;

d[j][i]=true이면 i보다 앞에 있어야하는 학생이 1명 추가됩니다. => l++;

 

모든 학생을 확인하고 l r 을 출력합니다.

 

 

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
#include <iostream>
using namespace std;
 
bool d[257][257];
int N, M;
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (d[i][k] && d[k][j]) d[i][j] = true;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (d[i][j] && d[j][i]) {
                cout << "-1\n";
                return;
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        int l = 1;
        int r = N;
        for (int j = 1; j <= N; j++) {
            if (d[i][j]) r--;
            else if (d[j][i]) l++;
        }
 
        cout << l << ' ' << r << '\n';
    }
}
 
void input() {
    int u, v;
    cin >> N >> M;
    while (M--) {
        cin >> u >> v;
        d[u][v] = true;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > Floyd' 카테고리의 다른 글

boj 14938 서강그라운드  (0) 2021.03.24

www.acmicpc.net/problem/14938

 

14938번: 서강그라운드

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을

www.acmicpc.net

플로이드 와샬 알고리즘을 이용하여 각 정점에서부터의 최단거리를 모두 구해줍니다.

그리고 1 ~ N정점을 시작점으로 다른 정점과의 거리가 M 이하인 경우만 아이템 수를 더해줍니다.

다 더했으면 최댓값을 갱신해줍니다.

 

 

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
#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;
 
int dis[101][101], list[101];
int N, M, R;
 
void solve() {
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        int sum = 0;
        for (int j = 1; j <= N; j++) {
            if (dis[i][j] > M) continue;
 
            sum += list[j];
        }
        ans = max(ans, sum);
    }
 
    cout << ans << '\n';
}
 
void func() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++){
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}
 
void init() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) dis[i][j] = 0;
            else dis[i][j] = INF;
        }
    }
}
 
void input() {
    int u, v, w;
    cin >> N >> M >> R;
    init();
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
    while (R--) {
        cin >> u >> v >> w;
        dis[u][v] = w;
        dis[v][u] = w;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
    solve();
 
    return 0;
}
 cs

'algorithm > Floyd' 카테고리의 다른 글

boj 2273 줄 서기  (0) 2021.04.16

+ Recent posts

티스토리툴바