AcWing 358. 岛屿

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 358. 岛屿原题链接中等

作者：

今夕 , 2020-01-28 19:36:25 , 所有人可见 , 阅读 2917

17

1

358. 岛屿

思路整理

从1-n遍历，遇到曾经没有遍历过的点时，进行dfs，找到当前点所在联通块中唯一的环。
将环上的点以及边放到一个数组中，遍历所有点，把当前点当作根，遍历不包括环上的点的子树，树形dp求出子树直径，以及子树中距离根节点最远的距离。
每个子树的直径就是一个备选答案。以及经过环上的边，两端点在两个子树上的某一个直径。

细节

dfs找环，记录来向边（参考割边割点的求法），直到找到第一个非树边时，通过打过的标记将环记录下来（并且要包括边权）。要注意即使找到环之后也要继续遍历其他点，直到当前连通块所有点都被遍历（原因其实很简单）
找到了环就很方便了，树形dp后，按照书上提示的单调队列处理就行。

其他一些东西

我们可以找一个环，处理一个环，没有必要把所有环都找到最后再进行处理（MLE）
dfs找环Acwing能AC但在bzoj上面会爆栈，所以可以通过bfs+拓扑排序来，拓扑排序最后没有遍历过的点就是环上的点。代码在BZOJ上面AC但是在Acwing上面T了，或许是STL以及BFS里面操作常数太大了。（所以我现在并没有写出能够在这两个平台上面同时AC的代码，另外在我最开始在AcWing写这个题的时候，MLE到自闭，但是洛谷很容易就过了。所以这里就先留坑不补了。

dfs找环

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1000010;
int head[N], ver[N << 1], nxt[N << 1], edge[N << 1], num, q[N*2], l, r, tot;
int n, pre[N];
bool vis[N], mark[N];
vector<pair<int,int> > v; // v[i]表示第i棵环的点
ll d[N], a[N*2], sum[N*2];
bool flag;
void add(int x,int y,int z){
    ver[++tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
void dfs(int x,int in_edge){
    vis[x] = 1;
    for (int i = head[x]; i;i=nxt[i]){
        int y = ver[i];
        if((i^1) == in_edge) //这里看不懂可以看蓝书0x66
            continue;
        if(flag && vis[y]) //如果已经找到环并且访问到了环上的点
            continue;
        if(vis[y]){ // 通过非树边找到了访问过的点
            int cur = i ^ 1; 
            do{
                v.push_back(make_pair(ver[cur], edge[cur]));
                mark[ver[cur]] = 1;
                cur = pre[ver[cur]];
            } while (ver[cur] != y);
            v.push_back(make_pair(ver[cur], edge[cur]));
            mark[ver[cur]] = 1;
            flag = true;
            continue;
        }
        pre[y] = i ^ 1; //记录来时路
        dfs(y, i);
    }
}
//树形dp求直径
ll dp(int x,int fa){
    ll res = 0;
    for (int i = head[x]; i;i=nxt[i]){
        int y = ver[i];
        if(y == fa || mark[y])
            continue;
        res = max(res, dp(y, x));
        res = max(res, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);
    }
    return res;
}
ll solve(){
    ll cur = 0;//记录当前环的直径
    for (int j = 0; j < v.size();j++){
        cur = max(cur, dp(v[j].first, 0));
        a[j] = d[v[j].first];
        sum[j] = v[j].second;
    }
    int num = v.size();
    //环形处理
    memcpy(a+num, a, num*sizeof(ll));
    memcpy(sum+num, sum, num*sizeof(ll));
    l = 0, r = -1;
    for (int k = 0; k < 2 * num;k++){
        if(k)
            sum[k] += sum[k - 1];
        while(l <= r && k - q[l] >= num)
            l++;
        if(l <= r){
            int j = q[l];
            cur = max(cur, a[j] + a[k] + sum[k] - sum[j]);
        }
        while(l <= r && a[k] - sum[k] >= a[q[r]] - sum[q[r]])
            r--;
        q[++r] = k;
    }
    return cur;
}
int main()
{
    scanf("%d", &n);
    tot = 1;
    for (int i = 1, y ,z; i <= n;i++){
        scanf("%d%d", &y, &z);
        add(i, y, z);
        add(y, i, z);
    }
    ll res = 0;
    for (int i = 1; i <= n;i++){
        if(vis[i])
            continue;
        flag = false;
        dfs(i, 0);
        res += solve();
        v.clear();
    }
    cout << res << endl;
    return 0;
}

bfs拓扑排序找环

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1000010;
int head[N], ver[N << 1], nxt[N << 1], edge[N << 1], num, q[N*2], deg[N], l, r, tot;
int n, pre[N];
bool vis[N];
vector<int> v;
ll d[N], f[N], a[N*2], sum[N*2];
bool flag;
void add(int x,int y,int z){
    ver[++tot] = y;
    edge[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot;
}
void bfs(int x){
    v.clear();
    queue<int> q;
    q.push(x);
    vis[x] = 1;
    while(q.size()){
        int x = q.front();
        q.pop();
        v.push_back(x);
        for (int i = head[x]; i;i=nxt[i]){
            int y = ver[i];
            if(vis[y])
                continue;
            vis[y] = 1;
            q.push(y);
        }
    }
}
void topsort(){
    queue<int> q;
    for (int i = 0; i < v.size();i++){
        if(deg[v[i]] == 1)
            q.push(v[i]);
        vis[v[i]] = 0;
    }
    while(q.size()){
        int x = q.front();
        q.pop();
        vis[x] = 1;
        for (int i = head[x]; i;i=nxt[i]){
            int y = ver[i];
            if(vis[y])
                continue;
            f[y] = max(f[y], f[x]);
            f[y] = max(f[y], d[y] + d[x] + edge[i]);
            d[y] = max(d[y], d[x] + edge[i]);
            if(--deg[y] == 1)
                q.push(y);
        }
    }
    int p = 0;
    for (int i = 0; i < v.size();i++){
        if(vis[v[i]])
            continue;
        v[p++] = v[i];
    }
    num = p;
}
ll solve(){
    int p = v[0], last = 0, j = 0;
    ll res = 0;
    do{
        for (int i = head[p]; i;i=nxt[i]){
            if(i == last)
                continue;
            if(vis[ver[i]])
                continue;
            p = ver[i];
            last = i ^ 1;
            res = max(res, f[p]);
            a[j] = d[p];
            sum[j++] = edge[i];
            vis[p] = 1;
            break;
        }
    } while (p != v[0]);
    memcpy(a+num, a, num*sizeof(ll));
    memcpy(sum+num, sum, num*sizeof(ll));
    l = 0, r = -1;
    for (int k = 0; k < 2 * num;k++){
        if(k)
            sum[k] += sum[k - 1];
        while(l <= r && k - q[l] >= num)
            l++;
        if(l <= r){
            int j = q[l];
            res = max(res, a[j] + a[k] + sum[k] - sum[j]);
        }
        while(l <= r && a[k] - sum[k] >= a[q[r]] - sum[q[r]])
            r--;
        q[++r] = k;
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    tot = 1;
    for (int i = 1, y ,z; i <= n;i++){
        scanf("%d%d", &y, &z);
        add(i, y, z);
        add(y, i, z);
        deg[i]++;
        deg[y]++;
    }
    ll res = 0;
    for (int i = 1; i <= n;i++){
        if(vis[i])
            continue;
        flag = false;
        bfs(i);//找到i的连通块放到点集v中
        topsort();//找到环，并且计算出d数组和f数组
        res += solve();
    }
    cout << res << endl;
    return 0;
}