题目：Maximum Matching
传送门：http://codeforces.com/contest/1038/problem/E
分析：
一个块拥有{color1，val，color2}，两个块相连要求相连处颜色相同，求价值最大的连接方案。
关心到color最大为4，以4种颜色为点，对于每个块，在（color1，color2）间连一条边权为（val）的边，建一张4个点n条边的图。显然，在图上选一条价值最大的路径（或回路）就是答案了。
方法一：
如果这张图本身就是Eular路径（或Eular回路），那就是答案了，不会有方案比全选更优。
如果本身不是Eular路径（或Eular回路），我们可以删掉一些边，使其成为Eular路径（或Eular环路）。
对于两个点而言，最多删去一条边（若删去两条，这两条构成的环可加入答案），删去的边一定是连接这两个点的边中权重最小的。
枚举要删掉的边，对于4个点，两两连接，最多16条边需要考虑是否删除，枚举删掉边的集合st（对该集合状态压缩），对去除该集合中的边的集合求一条Eular路径（或Eular回路）
复杂度：$O(2^16 * 4 * 4 * n)$ 实际上对存在自环的集合是不用考虑的，复杂度：$O(2^16 * n)$
引用：Ashishgup大佬的题解：http://codeforces.com/blog/entry/61692
方法二:
如果两点（u，v）之间存在多条边，每两条边就能走回本身，可从原图中消去，在遍历到u点或v点时加到答案中，注意不要重复加。
为了保证不破坏原图的连通性，那最多只需保留2条边，保留的当然是权值最小的边啦（这些边有可能不被选中，保留权值大的边就可能得不到答案）
对4个点13条边暴力DFS找一条路径即可。这样复杂度与n无关，题目的n可以进一步加强。
#include <bits/stdc++.h>
int e[][][],f[][],vis[];
int ans=;
void dfs(int x,int tmp){
for(int y=;y<=;++y)if(!vis[x] && !vis[y])tmp+=f[x][y];++vis[x];
if(tmp>ans)ans=tmp;
for(int y=;y<=;++y)
if(x!=y && e[x][y][]>){
tmp+=e[x][y][e[x][y][]];
--e[x][y][];--e[y][x][];
dfs(y,tmp);
++e[x][y][];++e[y][x][];
tmp-=e[x][y][e[x][y][]];
}
--vis[x];for(int y=;y<=;++y)if(!vis[x] && !vis[y])tmp-=f[x][y];
}
int main(){
//freopen("in.txt","r",stdin);
int n;scanf("%d",&n);
for(int i=,u,val,v;i<n;++i){
scanf("%d %d %d",&u,&val,&v);
if(v>u)u^=v,v^=u,u^=v;
e[v][u][++e[v][u][]]=val;
}
for(int i=;i<=;++i){
for(;e[i][i][];--e[i][i][])f[i][i]+=e[i][i][e[i][i][]];
for(int j=i+;j<=;++j){
std::sort(e[i][j]+,e[i][j]+e[i][j][]+);
for(;e[i][j][]>;e[i][j][]-=)f[i][j]+=e[i][j][e[i][j][]]+e[i][j][e[i][j][]-];
e[j][i][]=e[i][j][];e[j][i][]=e[i][j][];e[j][i][]=e[i][j][];
f[j][i]=f[i][j];
}
}
dfs(,);
for(int i=;i<=;++i)
dfs(i,);
printf("%d",ans);
return ;
}
方法3：
我们可以设计一个复杂度与n相关的做法，这样颜色数量可以加强。
定义f[i][j][x][y]:[i,j]区间里的链左右端点颜色为(x,y);
转移方程：
1继承：f[i][j][x][y]: max{f[i][k][x][y],f[k+1][j][x][y]};
2拼接：f[i][j][x][y]: max{f[i][k][x][t]+f[k+1][j][t][y], f[k+1][j][x][t]+f[i][k][t][y]};
引用：http://codeforces.com/contest/1038/submission/42602607
方法4：
对于本题而言，在连通块中，每当找到一个环就可以直接加入到答案中。最后可能会剩下一些零星的边，对于只有4个点的图而言的，只有剩下$e_{a,b},e_{c,d}$这种情况要考虑，删除一条就好了，可以从加入答案的边中用权值最小的边替换剩下的边，删掉。等效于删去一条最小边。
找环（实际上不关心环的具体情况，与找Eular路径（回路）方法相同，使用Fleury算法，复杂度O(n)）
联通块可用并查集维护。