Dylan's Blog
0%

Posted on Edited on In

问题描述：

你将要游览一个有N个岛屿的公园。从每一个岛i出发，只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛，但每座桥均可以双向行走。同时，每一对这样的岛屿，都有一艘专用的往来两岛之间的渡船。

你希望所经过的桥的总长度尽可能的长，但受到以下的限制： • 可以自行挑选一个岛开始游览。 • 任何一个岛都不能游览一次以上。 • 无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。

由S到D可以有以下方法： 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离 渡船：你可以选择这种方法，仅当没有任何桥或以前使用过的渡船的组合可以由S走到D（当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）

输入：

第一行包含N个整数，即公园内岛屿的数目（2<=N<=1000000） 随后的N行每一行用来表示一个岛，第i 行由两个以单空格分隔的整数，表示由岛i筑的桥，第一个整数表示桥另一端的岛，第二个整数表示该桥的长度Li （1<=Li<=100000000）

输出：

输出可能的最大步行距离

思路：

由于每个点都有一条出边，所以图是一个基环树森林的形态，题目就是求每棵基环树直径之和。

回顾一下树的直径，有树形DP和两边BFS的解法。推广到基环树，同样可以用树形DP求解。首先应该分类讨论，有两种情况：一种是直径在某一棵子树上，另一种是直径经过环，连接两棵子树的最长链。第一种情况不难处理，依然是树形DP，在DP的过程中还可以求出最长链。第二种情况就稍微难一点，首先我们需要找环，这我们可以用拓扑排序，为了节省码量，我们可以拓扑排序的过程中进行DP。找出环后，我们应该如何处理？

不难想到，我们可以把每棵子树的最长链投影到环上的点上（子树根节点）作为点权，设为$f_i$。然后我们就要在环上找两个点$i,j$，使得$f_i+dis(i,j)+f_j$最大。这是一个DP的模型，我们先破环为链，然后前缀和维护两点距离，设节点$i$到节点1的距离为$g_i$。然后我们可以枚举$i$,然后求$max(f_j-g_j)$，这个我们就可以用单调队列维护，这样我们就可以在$O(n)$内求出$max(f_i+f_j+g_i-g_j)$。

代码：

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
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 1000005
#define LL long long
using namespace std;

int n, id, l=1, r, cnt, head[MAXN], belong[MAXN], deg[MAXN], q[MAXN*2];
LL ans, dia[MAXN], len[MAXN], f[MAXN*2], g[MAXN*2];
bool vis[MAXN];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int x, int y, LL z)
{
    edge[++cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].dis=z;
    head[x]=cnt;
    deg[y]++;
}

void dfs(int x, int id)
{
    belong[x]=id;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!belong[to]) dfs(to, id);
    }
}

void topsort()
{
    for(int i=1; i<=n; i++) if(deg[i]==1) q[++r]=i;
    while(l<=r)
    {
        int x=q[l++];
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(deg[to]<=1) continue;
            deg[to]--;
            dia[belong[x]]=max(dia[belong[x]], len[to]+len[x]+edge[i].dis);
            len[to]=max(len[to], len[x]+edge[i].dis);
            if(deg[to]==1) q[++r]=to;
        }
    }
}

void dp(int x)
{
    int y=x, tot=0;
    while(1)
    {
        bool flag=false;
        deg[y]=1; f[++tot]=len[y];
        for(int i=head[y]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(deg[to]<=1) continue;
            g[tot+1]=g[tot]+edge[i].dis;
            flag=true; y=to;
        }
        if(!flag) break;
    }
    if(tot==2)
    {
        int temp=0;
        for(int i=head[y]; i; i=edge[i].next)
            if(edge[i].to==x) temp=max(temp, edge[i].dis);
        dia[belong[x]]=max(dia[belong[x]], len[x]+len[y]+temp);
    }
    for(int i=head[y]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==x) g[tot+1]=g[tot]+edge[i].dis;
    }
    for(int i=1; i<=tot; i++)
    {
        f[i+tot]=f[i];
        g[i+tot]=g[tot+1]+g[i];
    }
    l=r=1; q[1]=1;
    for(int i=2; i<2*tot; i++)
    {
        while(l<=r && i-q[l]>=tot) l++;
        dia[belong[x]]=max(dia[belong[x]], f[i]+f[q[l]]+g[i]-g[q[l]]);
        while(l<=r && f[q[r]]+g[i]-g[q[r]]<=f[i]) r--;
        q[++r]=i;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(i, x, y);
        addedge(x, i, y);
    }
    for(int i=1; i<=n; i++) if(!belong[i]) dfs(i, ++id);
    topsort();
    for(int i=1; i<=n; i++)
    {
        if(deg[i]<=1 || vis[belong[i]]) continue;
        vis[belong[i]]=true;
        dp(i);
        ans+=dia[belong[i]];
    }
    printf("%lld\n", ans);
}

Posted on Edited on In

7月7号 Codeforces Round #495 题目链接：http://codeforces.com/contest/1004

A - Sonya and Hotels

过水，不多说。

B - Sonya and Exhibition

思路： 神仙题！！！我做完E题才想到。。。

千万不要想多了，就是0101010101…直接输出就好了，因为这样就可以保证任意一个序列中0和1的差最多相差1。也就保证了和最大。 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define MAXN 1005
#define LL long long
using namespace std;

int n, m;
struct A {int l, r;} a[MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) scanf("%d%d", &a[i].l, &a[i].r);
    for(int i=1; i<=n; i++)
    {
        if(i&1) printf("1");
        else printf("0");
    }
}

C - Sonya and Robots

思路： 就是求每个数之前有多少个不一样的数。记录每一个数上一次出现位置，从后向前扫，设num为之前有多少个不一样的数。如果上一次出现位置为0（也就是之前没有这个数）那么num—。

然后对于每个数最后的位置求一个num的和就好了。 代码：

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
#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long
using namespace std;

int n, a[MAXN], vis[MAXN], last[MAXN], pos[MAXN], num;
LL ans;

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        last[i]=pos[a[i]];
        if(pos[a[i]]==0) num++;
        pos[a[i]]=i;
    }
    for(int i=n; i>=1; i--)
    {
        if(!last[i]) num--;
        if(pos[a[i]]!=i) continue;
        ans+=num;
    }
    printf("%lld\n", ans);
}

D - Sonya and Matrix

思路： 比较难的一题。我们可以知道最大的数一定是在最角落，所以我们定义a为左上角的数，b为左下角的数。然后我们可以根据数量推出x的值，通过暴力枚举枚举出n，m的值。

知道了这些后我们就可以推出n, m, x, y, a, b。进而确定矩形，然后check一下这个矩形是否符合要求，如果符合直接输出，结束。 代码：

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;

int t, temp, n, m, x, y, b, num[MAXN], cnt[MAXN];

void solve(int n, int m, int x, int y)
{
    memset(cnt, 0, sizeof(cnt));
    y=n+m-x-b;
    if(x<0 || x>n || y<0 || y>m) return;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
    {
        int dis=abs(x-i)+abs(y-j);
        cnt[dis]++;
    }
    for(int i=1; i<=b; i++) if(cnt[i]!=num[i]) return;
    printf("%d %d\n%d %d\n", n, m, x, y);
    exit(0);
}


int main()
{
    scanf("%d", &t);
    for(int i=1; i<=t; i++)
    {
        scanf("%d", &temp);
        num[temp]++;
        b=max(b, temp);
    }
    if(num[0]!=1) {printf("-1\n"); return 0;}
    for(x=1; x*4==num[x]; x++) ;
    for(int i=1; i*i<=t; i++)
    {
        if(t%i) continue;
        solve(i, t/i, x, b);
        solve(t/i, i, x, b);
    }
    printf("-1\n");
}

E - Sonya and Ice Cream

思路： 相对于E题比较水吧。。。没有什么思维含量，就是码量大。。

和NOIP那道树网的核差不多，路径一定是在数的直径上，在直径上$O(n)$枚举路径，$O(1)$确定最远距离，用这个最远距离更新答案就好了。 代码：

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
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

int n, k, maxlen, maxdis, root, l, r, cnt, head[MAXN], son1[MAXN], son2[MAXN], dis[MAXN], tag[MAXN], vis1[MAXN], vis2[MAXN];

struct Edge {int next, to, dis;} edge[MAXN*2];

void addedge(int x, int y, int z)
{
    edge[++cnt].next=head[x];
    edge[cnt].to=y;
    edge[cnt].dis=z;
    head[x]=cnt;
}

int findline(int x, int fa)
{
    int len1=0, len2=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        int len=findline(to, x)+edge[i].dis;
        if(len>=len2) len2=len, son2[x]=i;
        if(len2>len1) swap(len2, len1), swap(son1[x], son2[x]);
    }
    if(len1+len2>maxlen) maxlen=len1+len2, root=x;
    return len1;
}

void finddis(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || tag[to]) continue;
        finddis(to, x);
        dis[x]=max(dis[x], edge[i].dis+dis[to]);
    }
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!tag[to] || to==fa) continue; 
        finddis(to, x);
    }
    maxdis=max(maxdis, dis[x]);
}

int solve(int l, int r)
{
    int ans=1e9, ldis=0, rdis=maxlen, x=l, y=l;
    for(int i=1; i<k; i++)
    {
        for(int j=head[y]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            if(!tag[to] || vis1[to]) continue;
            rdis-=edge[j].dis;
            vis1[y]=1; y=to; 
        }
    }
    ans=min(ans, max(rdis, ldis));
    while(y!=r)
    {
        for(int j=head[y]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            if(!tag[to] || vis1[to]) continue;
            rdis-=edge[j].dis;
            vis1[y]=1; y=to;
        }
        for(int j=head[x]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            if(!tag[to] || vis2[to]) continue;
            ldis+=edge[j].dis;
            vis2[x]=1; x=to;
        }

        ans=min(ans, max(rdis, ldis));
    }
    return max(ans, maxdis);
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);   
    }
    findline(1, 0);
    tag[root]=1; l=r=root;
    for(int i=son1[root]; i; i=son1[edge[i].to]) tag[edge[i].to]=1, l=edge[i].to;
    for(int i=son2[root]; i; i=son1[edge[i].to]) tag[edge[i].to]=1, r=edge[i].to;
    finddis(root, 0);
    printf("%d\n", solve(l, r));
}

Posted on Edited on In

问题描述：

给你一张n个节点m条边的图，每一条边包含一个位运算$op$和一个值$c$（0或1）。每条边两个端点权值$op$操作后的结果为$c$。你的任务是求出是否存在这样的图。

输入：

第一行$n (n<=1000), m (m<=100000)$表示n个节点，m条边。 接下来m行每行三个数$a, b, c$以及一个位运算$op$。表示$a, b$之间的一条边。

输出：

直接输出YES或NO。

思路：

不难看出这是一个2-SAT问题。每个点只能取0或1，并且点之间存在一些约束关系。这道题就是2-SAT的一道模版，比较简单。

按照2-SAT的套路，每个点有两种取值，每个值对应一个节点，然后按照约束关系建边（这个比较重要）。由于每个点只能取一个值，所以如果一个点对应的两个取值在同一个环中，则是不可能的。求无向图的环用tarjan就好了。

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 20005
#define MAXE 2000005
using namespace std;

int n, m, cnt, head[MAXN];
int id, top, tot, low[MAXN], dfn[MAXN], sta[MAXN], bel[MAXN];
bool vis[MAXN];
struct Edge {int to, next;} edge[MAXE];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

bool check()
{
    for(int i=1; i<=n; i++) if(bel[i]==bel[i+n]) return false;
    return true;
}

void tarjan(int x)
{
    low[x]=dfn[x]=++id;
    sta[++top]=x; vis[x]=true;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[x]=min(low[x], low[to]);
        }
        else if(vis[to]) low[x]=min(low[x], low[to]);
    }
    if(dfn[x]==low[x])
    {
        int y; tot++;
        do
        {
            y=sta[top--]; vis[y]=false;
            bel[y]=tot;
        }while(x!=y);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y, z; char op[5];
        cin>>x>>y>>z>>op;
        x++; y++;
        if(op[0]=='A' && z==0) addedge(x, y+n), addedge(y, x+n);
        if(op[0]=='A' && z==1) addedge(x+n, x), addedge(y+n, y);
        if(op[0]=='O' && z==0) addedge(x, x+n), addedge(y, y+n);
        if(op[0]=='O' && z==1) addedge(x+n, y), addedge(y+n, x);
        if(op[0]=='X' && z==0) addedge(x, y), addedge(y, x), addedge(x+n, y+n), addedge(y+n, x+n);
        if(op[0]=='X' && z==1) addedge(x, y+n), addedge(x+n, y), addedge(y, x+n), addedge(y+n, x);
    }
    for(int i=1; i<=n*2; i++) if(!dfn[i]) tarjan(i);
    if(check()) printf("YES\n");
    else printf("NO\n");
}

Posted on Edited on In

A - F & B - Acrostic

过水 QWQ…

C - Ordinary Beauty

思路： 一道比较巧妙的数学题。我们其实只需要考虑一位的期望，然后整个序列的期望就是这个的m+1倍。

然后我们考虑如何计算期望。一共是有$n*n$种情况（只考虑一位），如果$d==0$时，显然是有$n$种情况符合要求，如果$d!=0$那么就有$(n-d)*2$种情况符合要求，所以分类讨论一下就好。还有一点就是要注意精度，不要一下除$n*n$，精度损失比较大。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstring>
#define LL long long
using namespace std;

LL n, m, d;

int main()
{
    scanf("%lld%lld%lld", &n, &m, &d);
    double temp;
    if(d==0) temp=n;
    else temp=(n-d)*2;
    printf("%.10lf\n", (double)(m-1)/n*temp/n);
}

D - Saving Snuuk

思路： 比较水的一道图论题，只是题目好难看懂啊。。。其实就是给你一张无向图，每条边有两种权值，然后求在每个点切换权值的最短路。

不难想到建两张图，分别从起点，终点跑SPFA。每个点切换权值的最短路就是到起点，终点的距离之和。 代码：

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
#include <bits/stdc++.h>
#define LL long long
#define INF 1e18
#define MAXN 100005

LL min(LL x, LL y) {if(x<y) return x; return y;}

int n, m, s, t, u, v;
LL a, b, f=1e15, ans[MAXN];

struct Graph
{
    int cnt, head[MAXN], vis[MAXN];
    LL dis[MAXN];

    struct Edge {int next, to; LL dis;} edge[MAXN*2];

    std::queue<int> q;

    void addedge(int from, int to, LL dis)
    {
        edge[++cnt].next=head[from];
        edge[cnt].to=to;
        edge[cnt].dis=dis;
        head[from]=cnt;
    }

    void spfa(int s)
    {
        for(int i=1; i<=n; i++) dis[i]=INF;
        memset(vis, 0, sizeof(vis));
        q.push(s); vis[s]=1; dis[s]=0;
        while(!q.empty())
        {
            int x=q.front(); q.pop();
            vis[x]=0;
            for(int i=head[x]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if(dis[to]>dis[x]+edge[i].dis)
                {
                    dis[to]=dis[x]+edge[i].dis;
                    if(!vis[to]) q.push(to), vis[to]=1;
                }
            }
        }
    }
} g1, g2;

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%lld%lld", &u, &v, &a, &b);
        g1.addedge(u, v, a); g1.addedge(v, u, a);
        g2.addedge(v, u, b); g2.addedge(u, v, b);
    }
    g1.spfa(s);  g2.spfa(t);
    ans[n+1]=INF;
    for(int i=n; i>=1; i--) ans[i]=min(ans[i+1], g1.dis[i]+g2.dis[i]);
    for(int i=1; i<=n; i++) printf("%lld\n", f-ans[i]);
}

E - + Graph

思路： 思维难度不大，只是超级考验码力，我比赛时调了超级久还是没有写出QWQ。

我们设节点1的值为x，然后其它所有点的值都可以用$w_1-x$或$w_2+x$表示（w可以根据题目条件推出来）。先bfs一遍处理出每个节点$w_1,w_2$，储存在f数组里，然后统一进行判断。

限制条件有很多，不要漏了。首先要判断是否有正整数解，还要判断解的范围，还要判断解是否在范围内。详细的看代码好了。

代码：

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
#include <bits/stdc++.h>
#define MAXN 1000005
#define INF 1e18
#define LL long long

int n, m, cnt, head[MAXN], vis[MAXN];
LL l=1, r=INF, root=-1, f[MAXN][5];

LL min(LL x, LL y) {if(x>y) return y; return x;}
LL max(LL x, LL y) {if(x<y) return y; return x;}

struct Edge{int next, to; LL dis;} edge[MAXN];

std::queue<int> q;

void addedge(int from, int to, LL dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    head[from]=cnt;
}

void bfs(int x)
{
    vis[x]=1; q.push(x);
    f[x][0]=1; f[x][1]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(vis[to]) continue;
            f[to][0]=-f[x][0];
            f[to][1]=edge[i].dis-f[x][1];
            vis[to]=1; q.push(to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int u, v, s;
        scanf("%d%d%d", &u, &v, &s);
        addedge(u, v, s);
        addedge(v, u, s);
    }
    bfs(1);
    for(int i=1; i<=n; i++)
    {
        if(f[i][0]==1) l=max(l, 1-f[i][1]);
        else r=min(r, f[i][1]-1);
        for(int j=head[i]; j; j=edge[j].next)
        {
            int to=edge[j].to;
            LL x=f[i][0]+f[to][0];
            LL y=f[i][1]+f[to][1];
            if(x==0 && y!=edge[j].dis) {printf("0\n"); return 0;}
            if(x!=0)
            {
                LL temp=edge[j].dis-y;
                if(temp%2 || temp/x<=0) {printf("0\n"); return 0;}
                if(root==-1) root=temp/x;
                if(root!=temp/x) {printf("0\n"); return 0;}
            }
        }
    }
    if(root==-1) printf("%lld\n", max(0, r-l+1));
    else printf("%d", (root>=l && root<=r));
}

Posted on Edited on In

问题描述：

给你一张有n个节点m条边的无向图，需要你求出这张图的严格次小生成树。

输入：

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

输出：

仅一个数，表示严格次小生成树的边权和。

思路：

这道题和POJ1639度限制生成树一样，先计算出最小生成树，然后在最小生成树的基础上进行调整，得到要求的答案。

我们知道最小生成树与次小生成树最多只有一条边不同。所以我们可以在已经求出最小生成树的基础上，枚举每一条不在树上的边。假设它是次小生成树上的边，那么我们既要保持树的结构还要使树尽可能小，这时我们就要删去这条边两端树上路径的最长边，然后利用这个更新答案。

但这就出现了一个问题，有可能这条删去的边的边权和我们加的边的边权相等，这时新的树依然是最小生成树。所以我们需要记录下两端树上路径的次长边，如果出现上面情况我们就删去次长边，这样就是严格树次小生成树了。

代码：

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
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 100005
#define MAXE 300005
#define LL long long
#define INF 1e18
using namespace std;

int n, m, cnt, max1, max2, head[MAXN], f1[MAXN], f2[MAXN][25], dis[MAXN][25][2], dep[MAXN];
LL sum, ans=INF;

struct Edge {int x, y, dis; bool tag;} edge[MAXE];
struct Tree {int next, to, dis;} tree[MAXN*2];

bool CMP (Edge x, Edge y) {return x.dis<y.dis;}

int find(int x)
{
    if(f1[x]!=x) f1[x]=find(f1[x]);
    return f1[x];
}

void addedge(int from, int to, int dis)
{
    tree[++cnt].next=head[from];
    tree[cnt].to=to;
    tree[cnt].dis=dis;
    head[from]=cnt;
}

void kruskal()
{
    for(int i=1; i<=n; i++) f1[i]=i;
    sort(edge+1, edge+m+1, CMP);
    for(int i=1; i<=m; i++)
    {
        int fx=find(edge[i].x), fy=find(edge[i].y);
        if(fx!=fy)
        {
            f1[fx]=fy; sum+=edge[i].dis;
            edge[i].tag=true;
            addedge(edge[i].x, edge[i].y, edge[i].dis);
            addedge(edge[i].y, edge[i].x, edge[i].dis);
        }
    }
}

void dfs(int x, int fa)
{
    f2[x][0]=fa;
    for(int i=head[x]; i; i=tree[i].next)
    {
        int to=tree[i].to;
        if(to==fa) continue;
        dis[to][0][0]=tree[i].dis;
        dep[to]=dep[x]+1;
        dfs(to, x);
    }
}

void init()
{
    for(int i=1; i<=20; i++)
    {
        for(int j=1; j<=n; j++)
        {
            f2[j][i]=f2[f2[j][i-1]][i-1];
            dis[j][i][0]=max(dis[j][i-1][0], dis[f2[j][i-1]][i-1][0]);
            dis[j][i][1]=max(dis[j][i-1][1], dis[f2[j][i-1]][i-1][1]);
            if(dis[f2[j][i-1]][i-1][0]==dis[j][i-1][0]) continue;
            dis[j][i][1]=max(dis[j][i][1], min(dis[f2[j][i-1]][i-1][0], dis[j][i-1][0]));
        }
    }
}

int Lca(int x, int y)
{
    if(dep[x]<dep[y]) swap(x, y);
    for(int i=20; i>=0; i--) if(dep[f2[x][i]]>=dep[y]) x=f2[x][i];
    if(x==y) return x;
    for(int i=20; i>=0; i--) if(f2[x][i]!=f2[y][i]) x=f2[x][i], y=f2[y][i];
    return f2[x][0];
}

int solve(int x, int y, int len)
{
    int maxn=0;
    for(int i=20; i>=0; i--)
    {
        if(dep[f2[x][i]]>=dep[y])
        {
            if(dis[x][i][0]==len) maxn=max(maxn, dis[x][i][1]);
            else maxn=max(maxn, dis[x][i][0]);
            x=f2[x][i];
        }
    }
    return maxn;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].dis);
    kruskal();
    dfs(1, 0);
    init();
    for(int i=1; i<=m; i++)
    {
        if(edge[i].tag) continue;
        int lca=Lca(edge[i].x, edge[i].y);
        max1=solve(edge[i].x, lca, edge[i].dis);
        max2=solve(edge[i].y, lca, edge[i].dis);
        ans=min(ans, sum-max(max1, max2)+edge[i].dis);
    }
    printf("%lld\n", ans);
}