请问一共有多少个 JYY (o﹏o)
# 题面
> Linked 洛谷 P6085
给定一个 $n$ （$2\le n\le13$）个点 $m+K$ （$2\le m\le200,0\le K\le78$）条边的无向图，每条边有边权，其中有 $K$ 条是特殊边。
你从节点 $1$ 出发，每次只能沿着与当前节点相邻的边前往下一个节点，节点和边都可以经过多次，且每经过一次边就会花费其边权的代价。
现在要求你必须要经过所有特殊边然后回到节点 $1$，求最小花费。
# 解析
看到点数好小就想要状压，但是怎么压？
先转化一下问题，由于一条边可以经过任意多次，那我们就把一条非特殊边拆成无数条重边，而一条特殊边拆成一条特殊边和无数条非特殊重边；那么现在问题可以转化为——选出一个边集 $E$ 使得 $E$ 包含所有特殊边，并且 $E$ 存在一条从 $1$ 出发的欧拉回路。
再来回顾一下存在欧拉回路的充要条件：
- 设 $V$ 是 $E$ 的所有端点的点集，则 $V$ 通过 $E$ 可以形成连通块；
- 所有点在 $E$ 中的度数均为偶数。
（以下自动忽略没有特殊边的情况，该情况可以直接在点 $1$ 不动）
由于题目的限制 $V$ 必须包含点 $1$。于是可以想到用状压来表示当前包含 $1$ 的连通块。如果一个点不在连通块中，则其度数为 $0$，一定符合度数限制；而如果一个点在连通块中，则可能存在暂时为奇数度的情况，所以对于在连通块内的点，需要记录度数的奇偶性。
由于特殊边一定在 $E$ 中，特殊边对总花费以及对点的度数的贡献是确定的。所以我们在状压的时候，可以忽略加入一条特殊边造成的对花费以及度数的影响。
具体而言，状压的每一位：
- $0$：该点不在连通块内（其实也不一定真的不在连通块里，下面DP转移部分会具体说明）
- $1$：该点在连通块内且是奇数度（忽略掉特殊边）；
- $2$：该点在连通块内且是偶数度（忽略掉特殊边）。
那么这是一个三进制状压，$S\le 3^{13}=1594323$ 很没有问题。关键是怎么转移 awa
考虑我们为什么要加边：
- 将一个点连入连通块；
- 改变一对点的度数。
这里有一个理解的关键——最多只有一次加入一条与某个点 $u$ 相邻的边的操作的目的是改变点 $u$ 度数，因为只关心度数奇偶性。那为什么 $u$ 会被连许多条边呢？其实其他边都是因为加入了一条连接另外两个点的路径，而 $u$ 恰好在路径上，就会被加上两条边，而度数奇偶性不变。
我们一定是一个点一个点的扩展出这个连通块，即每次将一个点 $u$ 加入连通块，有两种情况：
- 该点有特殊边与当前的连通块相连，由于特殊边默认在 $E$ 中，所以可以直接把 $u$ 加进去；
- 加一条非特殊边路径将 $u$ 和连通块内点 $v$ 相连，目的有两个，改变 $u$ 的连通性，改变 $u$ 的度数；顺便会改变 $v$ 的度数。
对于第一种情况，由于我们不计特殊边的贡献，所以只需要在状态中加入“偶度数”的点 $u$ 即可。
对于第二种情况，为了达到目的且产生最小的花费，当然是取 $u,v$ 的最短路（Floyd 先求出最短路）；以 $\operatorname{dist}(u,v)$ 的代价在状态中加入“奇数度” $u$ 并且改变 $v$ 的度数。
欸？不是说对于一个点，只会有一次加边的目的是改变其奇偶性？但是显然这样转移很有可能点 $v$ 被改变了多次奇偶性。实际上，要么点 $v$ 是第一次被改变奇偶性，要么 $v$ 的实际作用是作为一个中转点——在某一次加入点 $w$ 时，连接了点 $v$，那么这两次转移的实质是加入了路径 $u,w$，目的是改变 $u,w$ 的度数奇偶性。
DP完后就需要算答案了，枚举出一个连通块状态 $S$，至少包含了所有特殊边端点；然后将所有特殊边的度数以及边权的贡献加进去（不要忘了(￣▽￣)”），然后我们会发现还会有一些点是奇数度的……需要额外加上一些路径来改变度数。
假设需要改变度数的点集为 $S$，是一个二进制状态，我们可以再做一个简单的状压DP求出改变度数的最小花费 $g(S)$，转移则选择两个 $S$ 中的点 $u,v$，要改变其度数就加 $u,v$ 的最短路，即 $g(S)=\min\big\{g(S-\{u,v\})+\operatorname{dist}(u,v)\big\}$。
最后复杂度就是 $O(3^nn^2)$，瓶颈在三进制状压转移时枚举连通块外点 $u$ 以及连通块内点 $v$（加入路径 $u,v$）。
# 源代码
自带小常数，现在好像在最优解 awa1
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/*Lucky_Glass*/
using namespace std;
const int N=13,M=205,SZ=1600000,INF=0x3f3f3f3f;
inline int Read(int &r){
int b=1,c=getchar();r=0;
while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r*=b;
}
int n,m,K,ansS,ans,totmust;
int dis[N][N],mustS[N],mustdu[N],f[SZ],g[1<<N],pow3[N];
queue<int> que;
int GetS(int S,int *sta){
int ret=0;
for(int i=0;i<n;i++,S/=3)
if((sta[i]=S%3))
ret|=(1<<i);
return ret;
}
int main(){
memset(dis,0x3f,sizeof dis);
Read(n),Read(K);
for(int i=1,u,v,l;i<=K;i++){
Read(u),Read(v),Read(l);u--,v--;
minc(dis[u][v],l),minc(dis[v][u],l);
mustS[u]|=(1<<v),mustS[v]|=(1<<u);
mustdu[u]++,mustdu[v]++;
ansS|=(1<<u)|(1<<v);
totmust+=l;
}
Read(m);
for(int i=1,u,v,l;i<=m;i++){
Read(u),Read(v),Read(l),u--,v--;
minc(dis[u][v],l),minc(dis[v][u],l);
}
//
for(int i=0;i<n;i++) dis[i][i]=0;
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
minc(dis[i][j],dis[i][k]+dis[k][j]);
//
memset(g,0x3f,sizeof g),g[0]=0;
for(int S=1;S<(1<<n);S++)
for(int u=0;u<n;u++)
for(int v=u+1;v<n;v++)
if((S>>u&1) && (S>>v&1))
minc(g[S],g[S^(1<<u)^(1<<v)]+dis[u][v]);
//
pow3[0]=1;for(int i=1;i<n;i++) pow3[i]=pow3[i-1]*3;
int all=1;for(int i=0;i<n;i++) all*=3;
//
ans=INF;
memset(f,0x3f,sizeof f),f[2]=0;
que.push(2);
while(!que.empty()){
int S=que.front(),sta[N],exiS;que.pop();
// printf("? %d\n",S);
exiS=GetS(S,sta);
for(int v=0;v<n;v++)
if(!sta[v]){
if(exiS&mustS[v]){
int T=S+2*pow3[v];
// printf(" %d -> %d\n",S,T);
if(f[T]==INF) que.push(T);
minc(f[T],f[S]);
}
for(int u=0;u<n;u++)
if(sta[u]){
int T=S+pow3[v]+(sta[u]==1? pow3[u]:-pow3[u]);
// printf(" %d -> %d (%d,%d) %d\n",S,T,u,sta[u],pow3[u]);
if(f[T]==INF) que.push(T);
minc(f[T],f[S]+dis[u][v]);
}
}
// printf("done\n");
if((exiS&ansS)==ansS){
int chgS=0;
for(int i=0;i<n;i++)
if(exiS>>i&1 && ((mustdu[i]&1)^(sta[i]==1)))
chgS|=(1<<i);
minc(ans,f[S]+g[chgS]+totmust);
}
}
//
printf("%d\n",ans);
return 0;
}