1103번: 게임

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

DAG로 가정해서 DP로 푸는 동시에 사이클이 존재하는지 확인한다.

시간복잡도는 $O(nm)$

#include<cstdio>
#include<algorithm>
using namespace std;
const int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
int n, m, dp[50][50], vis[50][50], p[50][50];
char s[50][51];
int f(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m || s[x][y] == 'H') return 0;
    if (p[x][y]) { puts("-1"); exit(0); }
    int &ret = dp[x][y];
    if (vis[x][y]) return ret;
    p[x][y] = vis[x][y] = 1;
    int t = s[x][y] - '0';
    for (int i = 0; i < 4; i++) ret = max(ret, f(x + t*dx[i], y + t*dy[i]));
    p[x][y] = 0;
    return ++ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", s[i]);
    printf("%d", f(0, 0));
    return 0;
}

14554번: The Other Way

https://www.acmicpc.net/source/5852286


$O(m\lg n)$

최단경로를 따라 DAG를 만들고 DP를 한다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, s, e, dp[MXN + 1];
long long dis[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
priority_queue<pair<long long, int> > pq;
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &e);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    fill(dis + 1, dis + 1 + n, 1e18);
    dis[s] = 0;
    dp[s] = 1;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int tpos = pq.top().second;
        long long tdis = -pq.top().first;
        pq.pop();
        if (dis[tpos] ^ tdis) continue;
        for (auto it : adj[tpos]) {
            if (it.second + tdis < dis[it.first]) {
                dis[it.first] = it.second + tdis;
                dp[it.first] = 0;
                pq.push({ -dis[it.first],it.first });
            }
            if (it.second + tdis == dis[it.first]) dp[it.first] = (dp[it.first] + dp[tpos]) % (int(1e9) + 9);
        }
    }
    printf("%d", dp[e]);
    return 0;
}

2211번: 네트워크 복구

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


$O(m\lg n)$

1번 지점으로부터 나머지 지점까지의 shortest path로 이뤄진 DAG를 구한다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 1e3;
int cst[MXN + 1], fr[MXN + 1], n, m;
vector<pair<int, int> > adj[MXN + 1];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    fill(cst + 2, cst + 1 + n, 1e9);
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,1 });
    printf("%d\n", n - 1);
    while (!pq.empty()) {
        int h = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (cst[h] ^ d) continue;
        if (fr[h]) printf("%d %d\n", fr[h], h);
        for (auto it : adj[h]) if (d + it.second<cst[it.first]) {
            cst[it.first] = d + it.second;
            fr[it.first] = h;
            pq.push({ -cst[it.first],it.first });
        }
    }
    return 0;
}

9470번: Strahler 순서

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


$O(tn)$

dfs를 통해 말단 노드에서 거슬러 올라가며 dp를 해준다.

#include<cstdio>
#include<vector>
using namespace std;
int t, k, m, p, dp[1001];
vector<int> adj[1001];
int f(int h) {
        if (dp[h]) return dp[h];
        int ck = 1;
        for (auto it : adj[h]) {
                if (f(it) == dp[h]) ck = 1;
                if (f(it) > dp[h]) {
                        dp[h] = f(it);
                        ck = 0;
                }
        }
        return dp[h] += ck;
}
int main() {
        for (scanf("%d", &t); t--;) {
                scanf("%d%d%d", &k, &m, &p);
                for (int i = 1; i <= m; i++) adj[i].clear(), dp[i] = 0;
                for (int i = 0, x, y; i < p; i++) {
                        scanf("%d%d", &x, &y);
                        adj[y].push_back(x);
                }
                printf("%d %d\n", k, f(m));
        }
        return 0;
}

2157번: 여행

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


$O(m(n+k))$

a<b인 (a,b,c) 쌍에 대해 b->a, 가중치 c 간선을 만들면 DAG를 만들 수 있다.
DAG 상에서 최장 거리는 dp를 통해 구할 수 있다.
dp[n][m]: 1-> ... -> n으로 m번 이하에 도착하는 최대 점수

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, m, k, dp[301][301];
vector<pair<int, int> > adj[301];
int f(int x, int y) {
    if (x > 1 && y == 1) return -1e9;
    if (x>1 && !dp[x][y]) {
        dp[x][y] = -1e9;
        for (auto it : adj[x]) dp[x][y] = max(dp[x][y], f(it.first, y - 1) + it.second);
    }
    return dp[x][y];
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0, x, y, z; i < k; i++) {
        scanf("%d%d%d", &x, &y, &z);
        if (x<y) adj[y].push_back({ x,z });
    }
    printf("%d", f(n, m));
    return 0;
}

1948번: 임계경로

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


$O(n+m)$

DAG 그래프에서 최장거리는 dp를 통해 구할 수 있다.
임의의 dp[i]를 구할 때 참조한 dp[j]에 대해 i->j 간선을 만들어 시작점으로부터 끝점까지 dfs를 통해 지나갈 수 있는 간선 수를 구한다.

#include<cstdio>
#include<vector>
using namespace std;
int dp[10001], ck[10001], n, m, s, e, r;
vector<pair<int, int> > adj[10001];
void dfs1(int h) {
    for (auto it : adj[h]) {
        if (!dp[it.first]) dfs1(it.first);
        if (dp[it.first] + it.second > dp[h]) dp[h] = dp[it.first] + it.second;
    }
}
void dfs2(int h) {
    if (!ck[h]) {
        ck[h] = 1;
        for (auto it : adj[h]) if (dp[it.first] + it.second == dp[h]) dfs2(it.first), r++;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
    }
    scanf("%d%d", &s, &e);
    dfs1(s);
    dfs2(s);
    printf("%d\n%d", dp[s], r);
    return 0;
}

2056번: 작업

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


$O(nm)$

dp[i]=max(j<i)(dp[j])+t[i]

#include<cstdio>
int n, dp[10001], r;
int main() {
    scanf("%d", &n);
    for (int i = 1, t, x, y; i <= n; i++) {
        for (scanf("%d%d", &t, &x); x--;) {
            scanf("%d", &y);
            if (dp[i] < dp[y]) dp[i] = dp[y];
        }
        dp[i] += t;
        if (r < dp[i]) r = dp[i];
    }
    printf("%d", r);
    return 0;
}

2611번: 자동차경주

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


$O(n+m)$

DAG 그래프이므로 dp로 해결할 수 있다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1000;
int n, m, dp[MXN + 1], go[MXN + 1];
vector<pair<int, int> > adj[MXN + 1];
int f(int h) {
    if (!dp[h] && h != 1) for (auto it : adj[h]) {
        int t = f(it.first) + it.second;
        if (t > dp[h]) dp[h] = t, go[h] = it.first;
    }
    return dp[h];
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++)
        scanf("%d %d %d", &x, &y, &z), adj[x].push_back({ y,z });
    int r = 0, idx = 1, t;
    for (auto it : adj[1]) {
        t = f(it.first) + it.second;
        if (t > r) r = t, idx = it.first;
    }
    printf("%d\n1", r);
    for (int i = idx; i; i = go[i]) printf(" %d", i);
    return 0;
}

1005번: ACM Craft

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


$O(n)$

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 1e3;
int t, n, m, w, s[MAX_N + 1], ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int dfs(int h) {
    if (ck[h]) return s[h];
    ck[h] = 1;
    int maxi = 0;
    for (auto it : adj[h]) maxi = max(maxi, dfs(it));
    return s[h] += maxi;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), adj[i].clear(), ck[i] = 0;
        for (int i = 0, x, y; i<m; i++) scanf("%d %d", &x, &y), adj[y].push_back(x);
        scanf("%d", &w);
        printf("%d\n", dfs(w));
    }
    return 0;
}