11495번: 격자 0 만들기

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각

www.acmicpc.net

#include <bits/stdc++.h>

using namespace std;

const int MAX = 60;

const int NODE_MAX = 3001;
const int INF = 1e9;
int n, m , sum, res;
pair<int,int> arr[MAX][MAX]; // node_num, val 

int c[NODE_MAX][NODE_MAX], f[NODE_MAX][NODE_MAX], d[NODE_MAX];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<int> adj[NODE_MAX];


void maxFlow(int start, int end) {
    while (1) {
        memset(d, -1, sizeof(d));
        queue<int> Q;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front(); Q.pop();

            for (auto nx : adj[x]) {
                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;
        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }

        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        
        sum = 0, res = 0;
        for (int i = 0; i < NODE_MAX; i++) adj[i].clear();

        cin >> n >> m;

        int Node_num = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int tmp;
                cin >> tmp;
                sum += tmp;

                arr[i][j].first = Node_num;
                arr[i][j].second = tmp;

                if ((i + j) % 2 == 0) {
                    adj[0].push_back(Node_num);
                    adj[Node_num].push_back(0);
                    c[0][Node_num] = tmp;
                }
                else {
                    adj[3000].push_back(Node_num);
                    adj[Node_num].push_back(3000);
                    c[Node_num][3000] = tmp;
                }

                Node_num++;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {

                if ((i + j) % 2 == 0) {
					int now = arr[i][j].first;

					for (int k = 0; k < 4; k++) {

						int nx = i + dx[k];
						int ny = j + dy[k];

						if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;

						int next_node = arr[nx][ny].first;

						adj[now].push_back(next_node);
						adj[next_node].push_back(now);
						c[now][next_node] = INF;
					}
                }

            }
        }


        maxFlow(0, 3000);

        cout << sum - res << '\n';
    }



    return 0;
}

'Algorithm > problem' 카테고리의 다른 글

백준 2623번 : 음악프로그램 - 위상정렬 C++ 코드 (0)	2022.02.24
백준 16946번 : 벽 부수고 이동하기 4 - BFS C++ 코드 (0)	2022.02.23
백준 5651번 : 완전 중요한 간선 - Network Flow C++ (0)	2022.02.23
백준 2316번 : 도시 왕복하기 2 - Network Flow, 정점 분할 (0)	2022.02.22
백준 17412번: 도시 왕복하기 1 - Network Flow 문제 (0)	2022.02.22

https://www.acmicpc.net/problem/5651

5651번: 완전 중요한 간선

입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1<=K<=15)가 주어진다. 각 테스트 케이스에는 N, M (2 <= N <= 300; 2 <= M <= 5,000)가 주어지고 각각 정점의 수와 간선의 수

www.acmicpc.net

1.문제접근 및 알고리즘

최대 유량이 흐르는 상태를 구현한 뒤

간선마다 검사를 해주면서 더이상 유량이 흐를수 없는 상태라면

즉 해당 간선의 용량과 흐르는 유량이 일치하는 상태라면

그 간선은 완전 중요한 간선이 된다.

2. 주의할점

1.

a 에서 b 로 가는 간선이 여러개 있을 수 있으니

용량을 계속 더해주어야한다

2.

계속 푸는데 시간초과가 나서 for문을 auto로 바꿔주니 시간초과가 해결되었다.

앞으로는 웬만하면 auto를 사용해주어야겠다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

const int MAX = 333;

int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];
vector<pair<int, int> > edge;
int n, m;

void maxFlow(int start, int end) {
    while (1) {
        memset(d, -1, sizeof(d));
        queue<int> Q;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();

            for(auto nx : adj[x]){
                if (c[x][nx] - f[x][nx] > 0 && d[nx] == -1) {
                    d[nx] = x;
                    Q.push(nx);
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;
        int flow = INT_MAX;

        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }

        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }
    }


}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k;
    cin >> k;
    for (int T = 0; T < k; T++) {
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        for (int i = 0; i < MAX; i++) adj[i].clear();
        edge.clear();
        cin >> n >> m;

        for (int i = 0; i < m; i++) {
            int a, b, d;
            cin >> a >> b >> d;
            

            c[a][b] += d;
            adj[a].push_back(b);
            adj[b].push_back(a);
            edge.push_back({ a,b });
        }


        maxFlow(1, n);

        int ans = 0;

        for (int i = 0; i < edge.size(); i++) {
            int S = edge[i].first;
            int T = edge[i].second;
            int prev[MAX];
            memset(prev, -1, sizeof(prev));

            queue<int> Q;
            Q.push(S);

            while (!Q.empty()) {
                int x = Q.front();
                Q.pop();

                for (auto nx : adj[x]) {
                    if (prev[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                        prev[nx] = x;
                        Q.push(nx);
                    }
                }
            }

            if (prev[T] == -1) ans++;
        }

        cout << ans << '\n';
    }


    return 0;
}

저 많은 시간초과들은

for문을 auto를 이용해서 돌도록 하니까 해결이 되었다..

'Algorithm > problem' 카테고리의 다른 글

백준 16946번 : 벽 부수고 이동하기 4 - BFS C++ 코드 (0)	2022.02.23
백준 11495번 : 격자 0 만들기 - Network Flow C++ 코드 (0)	2022.02.23
백준 2316번 : 도시 왕복하기 2 - Network Flow, 정점 분할 (0)	2022.02.22
백준 17412번: 도시 왕복하기 1 - Network Flow 문제 (0)	2022.02.22
백준 1699번: 제곱수의 합 (0)	2022.02.21

https://www.acmicpc.net/problem/17412

17412번: 도시 왕복하기 1

첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.

www.acmicpc.net

1.문제설명

1번에서 2번으로 갈 수 있는 모든 경로를 구해야 한다.

단 한 경로에 포함된 길이 다른 경로에 포함되면 안된다

2.접근방법[알고리즘]

문제가 처음 접했을 때 DFS로 노드를 순환하면서 풀 수 있을 것 같지만

그럴 수 없다.

이 문제는 Network Flow(최대유량) 알고리즘을 알아야 풀 수 있다.

한 간선을 한 번씩 방문할 수 있을 때 2번으로 갈 수 있는 경우가 몇 개 인지 구해야한다.

한 간선을 한 번씩 방문할 수 있다는 말은

한 간선에 1명만 이동할 수 있다는 말과 같고

이 때 2번으로 총 몇명이 도착 할 수 있는지 최대유량을 구해야 하는 문제다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 401;

int n, p,res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
		fill(d, d + MAX, -1);
        queue<int> Q;
        d[start] = 0;
        Q.push(start);

        while (!Q.empty() && d[end] == -1) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    Q.push(nx);
                    d[nx] = x;
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) break;

        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }
        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }


}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> p;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;

        c[a][b] = 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    maxFlow(1, 2);

    cout << res << '\n';
   

    return 0;
}

'Algorithm > problem' 카테고리의 다른 글

백준 5651번 : 완전 중요한 간선 - Network Flow C++ (0)	2022.02.23
백준 2316번 : 도시 왕복하기 2 - Network Flow, 정점 분할 (0)	2022.02.22
백준 1699번: 제곱수의 합 (0)	2022.02.21
백준 11003번 : 최솟값 찾기 C++ (0)	2022.02.19
백준 15683번 : 감시 C++ (0)	2022.02.19

https://www.acmicpc.net/problem/6086

6086번: 최대 유량

첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위

www.acmicpc.net

#include <bits/stdc++.h>
#include <unordered_set>

#define MAX 800
#define INF 1e9;

using namespace std;

int n, res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
        fill(d, d + MAX, -1);
        queue<int> Q;

        Q.push(start);
        d[start] = 0;
        while (!Q.empty() && d[end]==-1) {
            int x = Q.front();
            Q.pop();

            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    d[nx] = x;
                    Q.push(nx);
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) {
            break;
        }
        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }

        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }
}

int CtoI(char c) {
    if (c <= 'Z') {
		return c - 'A';
    }
    else {
        return (c - 'a') + 26;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) {
        char a, b;
        int q;
        cin >> a >> b >> q;

        int u = CtoI(a);
        int v = CtoI(b);
        c[u][v] += q;
        c[v][u] += q;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    maxFlow(0, 25);

    cout << res << '\n';

    return 0;
}

'Algorithm > etc' 카테고리의 다른 글

DP 경로구하기 (0)	2022.06.27
우선순위 큐와 벡터 정렬 시간복잡도 차이 - Priority queue vs Vector sort (0)	2022.03.07
cycle 찾기 (0)	2022.02.21
Segment Tree 구현 코드 C++ (0)	2022.02.11
플로이드 워샬 알고리즘이란? (냅색 응용) -모든 정점의 최단 거리 구하기 (0)	2022.01.28

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

딩코딩 : Computer Science 블로그

최대유량

백준 11495번 : 격자 0 만들기 - Network Flow C++ 코드

'Algorithm > problem' 카테고리의 다른 글

백준 5651번 : 완전 중요한 간선 - Network Flow C++

1.문제접근 및 알고리즘

2. 주의할점

3. 문제풀이코드 C++

'Algorithm > problem' 카테고리의 다른 글

백준 17412번: 도시 왕복하기 1 - Network Flow 문제

1.문제설명

2.접근방법[알고리즘]

3.문제풀이코드 C++

'Algorithm > problem' 카테고리의 다른 글

Network FLow 최대 유량 알고리즘

'Algorithm > etc' 카테고리의 다른 글

+ Recent posts

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역