A. 拜访约翰

  • 找关系然后dijstra
    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
    #include <iostream>
    #include <queue>  // BFS　　Ｉ．拜访约翰
    using namespace std;
    struct node {
        int x, y, v, c;
        bool operator<(const node& a) const { return v > a.v; }
    };
    priority_queue<node> q;
    int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 }, a[105][105], n, T;
    bool mk[105][105][3];
    int bfs() {
        while (!q.empty()) {
            q.pop();
        }
        q.push({ 1, 1, 0, 0 });
        while (!q.empty()) {
            node now = q.top();
            q.pop();
            int x = now.x, y = now.y, v = now.v, c = now.c;
            if (x == n && y == n) {
                return v;
            }
            if (mk[x][y][c]) {
                continue;
            }
            mk[x][y][c] = 1;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
                    int nv = v + T, nc = (c + 1) % 3;
                    if (mk[nx][ny][nc]) {
                        continue;
                    }
                    if (!nc) {
                        nv += a[nx][ny];
                    }
                    q.push({ nx, ny, nv, nc });
                }
            }
        }
    }
    int main() {
        cin >> n >> T;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> a[i][j];
            }
        }
        cout << bfs();
        return 0;
    }

B. 最短路输出路径

  • splay去DP就好了
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    int n, q, d[205][205], x, y, t[205][205], a[205];
    int main() {
        cin >> n >> q;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) cin >> d[i][j], t[i][j] = j;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            for (int j = 1; j <= n; j++) d[j][i] += a[i];
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (d[i][j] > d[i][k] + d[k][j] || d[i][j] == d[i][k] + d[k][j] && t[i][k] < t[i][j])
                        d[i][j] = d[i][k] + d[k][j], t[i][j] = t[i][k];
        while (q--) {
            cin >> x >> y;
            printf("From %d to %d : \nPath: ", x, y);
            int now = x;
            while (now != y) printf("%d-->", now), now = t[now][y];
            printf("%d\nTotal cost : %d \n\n", y, d[x][y] - a[y]);
        }
        system("pause");
        return 0;
    }

C. POI2013 Tales of seafaring

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q;
int dis[5005][2], vis[5005][2];
vector<int> G[5005];
queue<pair<int, int>> qu;
void bfs(int s) {
    qu.push({s, 0});
    dis[s][0] = 0;
    vis[s][0] = s;
    while (!qu.empty()) {
        auto t = qu.front();
        qu.pop();
        int u = t.first, x = t.second^1, y = t.second;
        for (int &v : G[u])
            if (vis[v][x] != s)
                qu.push({v, x}),
                vis[v][x] = s,
                dis[v][x] = dis[u][y] + 1;
    }
}
struct Query {
    int t;
    ll d;
    int id;
};
vector<Query> Q[5005];
bool ans[1000005];
int main() {
    cin >> n >> m >> q;
    for (int i=1;i<=m;i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i=1;i<=q;i++) {
        int s, t, d;
        cin >> s >> t >> d;
        Q[s].push_back({t, d, i});
    }
    for (int i=1;i<=n;i++) {
        bfs(i);
        for (auto &x : Q[i])
            ans[x.id] = vis[x.t][x.d%2] == i && dis[x.t][x.d%2] <= x.d
            && (dis[x.t][x.d%2] == x.d || !G[x.t].empty());
    }
    for (int i=1;i<=q;i++) cout << (ans[i] ? "TAK\n" : "NIE\n");
    return 0;
}

D. 公路修建问题

  • 二分的去贪就好了， 直接贪心也行
    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
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1e4 + 5, M = 2e4 + 5;
    int n, k, m, mx;
    int fa[N], flag[M];
    int find(int x) {
        if (x == fa[x])
            return x;
        return fa[x] = find(fa[x]);
    }
    struct dat {
        int x, y, c1, c2;
    } a[M];
    bool check(int val) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) fa[i] = i;
        for (int i = 1; i <= m; i++) {
            auto [x, y, c1, c2] = a[i];
            if (c1 > val)
                continue;
            int fx = find(x), fy = find(y);
            if (fx != fy) {
                fa[fy] = fx, cnt++;
                flag[i] = 1;
                if (cnt == k)
                    break;
            }
        }
        if (cnt < k)
            return false;
        for (int i = 1; i <= m; i++) {
            auto [x, y, c1, c2] = a[i];
            if (c2 > val)
                continue;
            int fx = find(x), fy = find(y);
            if (fx != fy) {
                fa[fy] = fx, cnt++;
                flag[i] = 2;
            }
        }
        if (cnt == n - 1)
            return true;
        return false;
    }
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);
        cin >> n >> k >> m;
        m--;
        for (int i = 1, x, y, c1, c2; i <= m; i++) {
            cin >> x >> y >> c1 >> c2;
            a[i] = { x, y, c1, c2 };
            mx = max(mx, c1);
        }
        int l = 1, r = mx, ans;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                ans = mid, r = mid - 1;
            else
                l = mid + 1;
        }
        cout << ans << '\n';
        return 0;
    }

F. 最优贸易

  • 缩点 + 拓扑 + DP
    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
    #include <bits/stdc++.h>
    #define int long long
    #define pb push_back
    #define erep(i, u) for(int i=h[u];~i;i=ne[i])
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    #define dep(i,a,b) for(int i=a;i>=b;i--)
    using namespace std;

    namespace zty
    {
    	const int N = 500010;
    	
    	bool m1;
    	int n, m, w[N];
    	int dfn[N], low[N], scc[N], cnt, scnt, stk[N], in[N], top, mx[N], mn[N];
    	int h[N], e[N], ne[N], idx;
    	int ind[N], dp[N];
    	pair<int, int> edge[N];
    	int tot;
    	map<pair<int, int>, bool> mp;
    	bool m2;
    	
    	void add(int a, int b)
    	{
    		e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    	}
    	
    	void tarjan(int u)
    	{
    		dfn[u] = low[u] = ++ cnt;
    		in[u] = 1, stk[++ top] = u;
    		erep(i, u)
    		{
    			int v = e[i];
    			if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
    			else if (in[v]) low[u] = min(low[u], dfn[v]);
    		}
    		if (low[u] == dfn[u])
    		{
    			scnt ++;
    			int f;
    			do
    			{
    				f = stk[top --];
    				scc[f] = scnt, in[f] = 0;
    				mx[scnt] = max(mx[scnt], w[f]), mn[scnt] = min(mn[scnt], w[f]);
    			}while (u != f);
    		}
    	}
    	
    	void topsort()
    	{
    		queue<int> q;
    		rep(i, 1, scnt)
    			if (!ind[i]) q.push(i);
    		while (q.size())
    		{
    			int u = q.front();q.pop();
    			erep(i, u)
    			{
    				int v = e[i];
    				dp[v] = dp[u];
    				mn[v] = min(mn[v], mn[u]);
    				dp[v] = max(dp[v], mx[v] - mn[v]);
    				ind[v] --;
    				if (!ind[v]) q.push(v);
    			}
    		}
    	}
    	
    	signed main()
    	{
    		ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    	    //cout << fixed << setprecision(3) << (&m2 - &m1) / 1024.0 / 1024 << endl;
    	    memset(h, -1, sizeof h), memset(mx, 0xcf, sizeof mx), memset(mn, 0x3f, sizeof mn);
    		cin >> n >> m;
    		rep(i, 1, n)
    			cin >> w[i];
    		rep(i, 1, m)
    		{
    			int op, a, b;
    			cin >> a >> b >> op;
    			add(a, b);
    			edge[++ tot] = {a, b};
    			if (op == 2) add(b, a), edge[++ tot] = {b, a};
    		}
    		rep(i, 1, n)
    			if (!dfn[i]) tarjan(i);
    		memset(h, -1, sizeof h), idx = 0;
    		rep(i, 1, tot)
    		{
    			int u = edge[i].first, v = edge[i].second;
    			if (scc[u] != scc[v] && !mp[{u, v}])
    				add(scc[u], scc[v]), ind[scc[v]] ++, mp[{u, v}] = 1;
    		}
    		//rep(i, 1, n) cout << scc[i] << " "; cout << endl;
    		topsort();
    		cout << dp[scc[n]] << endl;
    		return 0;
    	}
    }

    signed main()
    {
    	//freopen(".in", "r", stdin), freopen(".out", "w", stdout);
        zty::main();
    }