POJ - 1797 最短路变形

题意

给定一张n点m条边的无向图，求出1-n路径中边权最小值最大的边。

分析

这道题，刚开始的时候，没有什么思路。最简单暴力的方法就是 $O(n^n)$ 的搜索，暴力比较。但是这题在最短路的专题里，那必定和最短路有关。

在最短路算法中，通过复杂度，可以排除 $Flody$ ，剩下的 $SPFA/Dijkstra$ 。而最短边权最大，其实就是选出边权最大的一条路，然后更新到终点v的最小值即可。原本的松弛操作 $dis[v] = min(dis[v], dis[u] + w)$ 变成了 $dis[v] = max(dis[v], min(w, dis[u]))$ 。

另外，因为选出最大边权，最小。所以可以贪心的用最大生成树，来实现。

证明：若1->n中，经过x点，最大生成树贪心连边，保证1->x连通的最大，则不存在比 $e(x,v)$ 更大的边。从而构建出一颗最大路径树取其中最小值即可。

AC代码

Dijkstra

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}
int n, m;

struct node {
    int v, w, next;
}e[maxn<<1];
int head[maxn], cnt;
int vis[maxn], dis[maxn];

void init() {
    memset(head, -1, sizeof(head));
    cnt = 0;
}

void add(int u, int v, int w) {
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

int dijkstra(int st, int ed) {
    for (int i = 1; i <= n; i++) {
        dis[i] = -INF;
    }
    dis[st] = 0;
    memset(vis, 0, sizeof(vis));
    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, st));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            int w = e[i].w;
            if (u != st && dis[u] != -INF) {
                w = min(dis[u], w);//选择最小值
            }
            if (dis[v] < w) {
                dis[v] = w;
                q.push({dis[v], v});//选出最大边
            }
        }
    }
    return dis[ed];
}

int main(void) {
    FAST_IO;
    int t;
    cin >> t;
    int nt = 0;
    while (t--) {
        init();
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w);
            add(v, u, w);
        }

        cout << "Scenario #" << ++nt << ":" << endl;
        cout << dijkstra(1, n) <<endl << endl;
    }

    return 0;
}

最大生成树

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

struct node {
    int u, v, w;
    node(const int &u = 0, const int &v = 0, const int &w = 0) : 
        u(u), v(v), w(w) { }
    bool operator<(const node &x) const {
        return w > x.w;
    }
}e[maxn << 1];

int fa[maxn];
int n, m;
void init(int n) {
    // cnt = 0;
    for (int i = 0; i <= n; i++)  {
        fa[i] = i;
    }
}

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool unio(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    fa[fx] = fy;
    return true;
}

int MST() {
    sort(e + 1, e + 1 + m);
    int cnt = 0;
    int ans = INF;
    for (int i = 1; i <= m; i++) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (unio(u, v)) {
            ans = min(w, ans);
            cnt++;
            if (cnt == n - 1) break;
            if (find(1) == find(n)) break;
        }
    }
    return ans;
}

int main(void) {
    FAST_IO;

    int t, nt = 0;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init(n);
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            cin >> e[i].u >> e[i].v >> e[i].w;
        }
        int ans = MST();
        cout << "Scenario #" << ++nt << ":" << endl;
        cout << ans << endl << endl;
    }

    return 0;
}

POJ-1426 水题

题意

给定一个正整数n，求n的非0倍数，且只包含0和1的数字。

分析

两种状态， $x = x * 10 ,x = x * 10 + 1$ ，暴力 $DFS$ 。

AC代码

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}
int n;

bool dfs(ull x, int step) {
    if (step > 19) return false;
    if (x % n == 0) {
        cout << x << endl;
        return true;
    }
    if (dfs(x * 10, step + 1)) return true; 
    if (dfs(x * 10 + 1, step + 1)) return true; 
}

int main(void) {
    FAST_IO;

    while (cin >> n) {
        if (n == 0) break;
        dfs(1, 1);
    }

    return 0;
}

CF-1037D 验证BFS序，好题！

题意

$BFS$ 算法定义如下：

设想有一个顶点编号从 1 到 n 的无向图。初始化 q 为一个只包含顶点 1 的新队列，并将顶点 1 标记为已使用。
从队列 q 的头部提取顶点 v 。
打印顶点 v 的下标。
以任意顺序遍历所有与 v 相邻的且未被使用的顶点 u 。将顶点 u 标记为已使用，并将其插入队列 q 的尾部。
如果队列不是空的，则从步骤 2 继续。
否则结束。

给定一棵结点编号从1到n的无根树，以及一个BFS序列，问该BFS序列是否为合法的树的BFS序列。保证BFS算法必从结点1开始，但BFS序列的第一个结点未必是1。

分析

一开始写了朴素的 $BFS$ wa on test11，然后再次读题，是随机取点，就该成记录层次验证。但是没想到wa on test4了。

思考后发现理由如下：

如图：

1 2

1 4

2 3

2 5

4 6

BFS序列：1 4 2 3 5 6，其对应层次序列没问题，但是4先入队，所以节点6应该在3 5之前。其先后顺序无法通过深度记录下来。

对于每个节点的先后顺序，可以先记录每个顶点在给定序列中的位置。
然后把邻接表内可达点的顺序，按照位置排序。
进行BFS，比较最终的序列是否和给定序列一致。

复杂度分析：每次进行排序的复杂度是 $O(nlogn)$ ，跑一次 $BFS$ 为 $O(n)$ ，所以预计复杂度在 $O(nlogn^2)$ 左右。

AC代码

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 200000 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

int a[maxn];
int ans[maxn];
vector<int> e[maxn];
int vis[maxn];
int pos[maxn];

void bfs(int root) {
    queue<int> q;
    q.push(root);
    int cnt = 1;
    while (!q.empty()) {
        int u = q.front();
        ans[cnt++] = u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto &v : e[u]) {
            if (!vis[v]) q.push(v);
        }
    }
}

int main(void) {
    FAST_IO;

    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    for (int i = 0; i <= n; i++) {
        sort(e[i].begin(), e[i].end(), [](int const &x, int const &y){
            return pos[x] < pos[y];
        });
    }
    bfs(1);
    int flag = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] != ans[i]) {
            flag = 1;
            break;
        }
    }
    // cout << endl;
    if (flag) cout << "No" <<endl;
    else cout << "Yes" << endl;

    return 0;
}

POJ - 3279 二进制状态压缩+暴力，好题

题意

有一个01矩阵，每次改变一格同时也会反转它上下左右的格子。问对于每个格子，最少操作多少次，可以矩阵全为0。若是不可能，输出 $IMPOSSIBLE$ 。

分析

本题在思维上算是贪心。每次改定上下左右和自身。若是改动偶数次，就会还原成原始状态，所以最少的方案就是每个格子最多改动一次。

再考虑格子间的关系，当我们翻转一个格子的时候，会影响上下左右的格子，所以我们以上一行为基础进行翻转，当上一行为1时，就改变当前格子，这样就不会影响上一行的其他格子，当翻转完成后，只需要看最后一行是否全部是0即可，若是代表次方案可行。
我们枚举第一行的状态， $2^m$ 种情况，根据第一行状态压缩枚举，来进行各种情况的翻转。
若最后一行全是0，且翻转次数小于以前的方案就可以更新答案。

AC代码

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 15 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

int m, n;
int a[maxn][maxn], g[maxn][maxn];
int const dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int mp[maxn][maxn];
int cnt;

bool checkpos(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;   
    return true;
}

void change(int x, int y) {
    cnt++;
    mp[x][y] = 1;
    g[x][y] ^= 1;
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (checkpos(tx, ty)) {
            g[tx][ty] ^= 1;
        }
    }
}

bool check(int v) {
    memcpy(g, a, sizeof(g));
    memset(mp, 0, sizeof(mp));
    cnt = 0;
    for (int i = 0; i < m; i++) {
        if (v & (1 << (m - 1 - i))) change(0, i);
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i - 1][j]) {
                change(i, j);
            }
        }
    }
    for (int i = 0; i < m; i++) {
        if (g[n - 1][i]) return false;
    }
    return true;
}

int main(void) {
    // FAST_IO;

    cin >> n >> m;
    int p = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    int ans = INF;
    for (int i = 0; i < (1 << m); i++) {
        if (check(i) && cnt < ans) {
            ans = cnt;
            p = i;
        }
    }
    if (ans != INF) {
        check(p);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << mp[i][j];
                if (j < m - 1) cout <<" ";
            }
            cout << endl;
        }
    } else {
        cout << "IMPOSSIBLE" << endl;
    }

    return 0;
}

寒假练习（二）最短路 and 搜索

POJ - 1797 最短路变形

题意

分析

AC代码

Dijkstra

最大生成树

POJ-1426 水题

题意

分析

AC代码

CF-1037D 验证BFS序，好题！

题意

分析

AC代码

POJ - 3279 二进制状态压缩+暴力 ，好题

题意

分析

AC代码

POJ - 3279 二进制状态压缩+暴力，好题