J.Toad’s Travel

銀川區域賽補題,Toad’s Travel

A toad is travelling in Byteland, which consists of some cities and some roads, each of which connects a pair of cities. More specifically, the map of Byteland is an undirected connected edge-weighted graph in which every edge lies on at most one simple cycle. The toad is in the city numbered by 11 at first and wants to go through all the roads at least once.

TIME IS MONEY!

The toad must minimize the total length of the path in his travelling.

樣例輸入

6 7

1 2 1

1 3 1

2 3 1

3 4 1

3 5 1

4 5 1

2 6 1

樣例輸出

8

題意：給定一個可能有重邊的仙人掌，從1号節點出發，求走過所有邊(如果1可以是歐拉路的起點，那麼一筆畫就是全部的邊長和，如果沒有歐拉路自然有些邊會重複)，求走過所有邊的最短路。

思路：建構仙人掌的圓方樹，在圓方樹上dp

dp[i][0]：表示tarjan算法dfs進入i節點然後回溯出i節點走完i以下所有邊至少一遍的最小代價。

dp[i][1]：表示tarjan算法dfs進入i節點然後最後停在i以下所的某節點且走完i以下所有邊至少一遍的最小代價。

cir[i]表示i節點代表的環的環長(i為圓點時cir[i]=0)

eij表示點i和點j邊長

i為方點時(子節點都為圓點)：

dp[i][0] = cir[i] + Σdp[j][0] (j∈i的子節點)

dp[i][1] = dp[i][0] + min(eij + dp[j][0] - dp[j][1])

i為圓點時(子節點可能是方點也可以能是圓點)：

dp[i][0] = Σ(dp[j][0] + 2eij)(j∈i的子節點)

dp[i][1] = dp[i][0] + min(dp[j][0] - dp[j][1] - eij)

AC代碼：(生成圓方樹的代碼主要來自高三巨佬yyb，然後自己根據題目瞎diy+DP了一下)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define RG register
#define MAX 400000
const ll inf = 0x3f3f3f3f3f3f3f3fll;

inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct Line{int v,next,w;};
struct Link
{
    Line e[2 * MAX];
    int h[MAX],cnt;
    inline void Add(int u,int v,int w)
    {
        e[++cnt]=(Line){v,h[u],w};h[u]=cnt;
        e[++cnt]=(Line){u,h[v],w};h[v]=cnt;
    }
}T,G;
int n;
struct RST
{ 
	ll dp[MAX][2], cir[MAX];// 0表示出來，1表示停在裡面 
    bool zn[MAX];
    void dfs(int u, int ff)
    {
    	ll minrs = inf;
    	dp[u][0] = cir[u];
    	for(int i=T.h[u];i;i=T.e[i].next)
    	{
    		int v=T.e[i].v, w=T.e[i].w;
			if(v==ff)continue;
    		dfs(v, u);
    		if (u <= n)	// 目前節點是圓點 
			{
				dp[u][0] += dp[v][0] + 2 * w;// 計算通過通過所有子節點再回到目前節點的代價總和 
				minrs = min(minrs, dp[v][1] - dp[v][0] - w);// 當選擇在一個子節點中停下時與通過再回來的代價差 
			}
    		else
    		{
    			dp[u][0] += dp[v][0];
    			minrs = min(minrs, w + dp[v][1] - dp[v][0]);
			}
		}
		if (minrs != inf)
			dp[u][1] = dp[u][0] + minrs; 
	}
}rst;
int dfn[MAX],low[MAX],tim,tp[MAX],dep[MAX];
int fa[MAX];
ll dis[MAX];
ll S[MAX],tot,m,Q;
vector<int> H[MAX];
void Build(int u,int y,int d)
{// 環首 環末 環首環末距離 
    ll top = dep[y] - dep[u] + 1, sum = d, Dis=0;// top: 環節點數 
    for(int i = y; i != u; i = fa[i]) S[top--] = i, sum += dis[i] - dis[fa[i]];
    ++tot; S[1] = u; top = dep[y] - dep[u] + 1; rst.cir[tot] = sum;// cir[tot]: tot号環的總長 
    for(int i = 1; i <= top; ++i)
    {
        ll D = min(Dis, sum - Dis);// 環首到環上i号節點的最短距離 
        T.Add(tot, S[i], D);
        rst.zn[S[i]] = (D == Dis);// 環的順時針最短的标記，否則是逆時針最短 
        Dis += dis[S[i+1]] - dis[S[i]];
    }
}
void Tarjan(int u,int in_edge)
{
    dfn[u]=low[u]=++tim;fa[u]=G.e[in_edge ^ 1].v;dep[u]=dep[fa[u]]+1;
    for(int i=G.h[u];i;i=G.e[i].next)
    {
        int v=G.e[i].v;if(i==(in_edge ^ 1))continue;
        if(!dfn[v])
        {
            dis[v]=dis[u]+G.e[i].w;
            Tarjan(v,i);low[u]=min(low[u],low[v]);
        }
        else
		{
			H[v].push_back(i ^ 1);
			low[u]=min(low[u],dfn[v]);
		}
        if(dfn[u]<low[v])T.Add(u,v,G.e[i].w);
    }
    for (int i : H[u])
    	Build(u, G.e[i].v, G.e[i].w);
}
int main()
{
    tot = n = read(); m = read();G.cnt = 1;
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read(),w=read();
        G.Add(u,v,w);
    }
    Tarjan(1,0);
    rst.dfs(1, 0);
    printf("%lld\n", min(rst.dp[1][1], rst.dp[1][0]));
    return 0;
}
/*
6 7
1 2 1
1 3 1
2 3 1
3 4 1
3 5 1
4 5 1
2 6 1

8

9 9
1 2 3
2 3 6
3 4 4
3 5 5
1 6 6
1 7 7
6 8 8
7 8 9
8 9 30

4 5
1 2 3
1 2 5
1 3 7
1 3 6
3 4 10

3 3
1 3 3
1 2 5
2 3 4

*/