时间限制:10000ms
单点时限:1000ms
内存限制:256MB
一张卡片可以被表示成这种形式 [color1 | value | color2]，也可以通过翻转操作变成[color2 | value | color1]。两张卡片能够连接，当且仅当左边卡片右边的颜色和右边卡片左边的颜色相同。
现在你有n张这样的卡片，你可以通过翻转和连接操作将其中一部分卡片串成一串，现在你需要求出你能够串成的卡片序列中，value总值最大的是多少。
第一行一个数n
接下来n行，每行三个数，表示color1、value、color2
对于30%的数据，n ≤ 5
对于60%的数据，n ≤ 40
对于100%的数据，1 ≤ n ≤ 1000, 0 ≤ value ≤ 100000, 1 ≤ color ≤ 4
输出一个数，表示答案
样例输入
6 3 70 4 2 26 3 4 39 4 2 77 1 2 88 1 4 43 2样例输出
343思路：将4种颜色看成4个顶点，值看成边的权重，建立一个无向图。顶点之间可能有多条边如果是奇数dfs时就全部加上，
偶数时留一条边从下一个顶点进行dfs(这条剩下的边下个顶就会遍历到)这点是关键，需要好好体会一下。
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<vector> #include<algorithm> #define LL long long #define INF 1e9 using namespace std; const int maxn=1e3+100; int mp[5][5]; int c[5][5]; int Min[5][5]; int ans=0; int vis[5][5]; void dfs(int id,int sum) { sum+=mp[id][id]; int gg=mp[id][id]; //cout<<gg<<endl; mp[id][id]=0; for(int i=1;i<=4;i++) { if(i!=id&&c[id][i]) { int h=sum; h+=mp[id][i]; int v=mp[id][i]; int cnt=c[id][i]; mp[id][i]=0; mp[i][id]=0; if(c[id][i]%2==0) { h-=Min[id][i]; } c[id][i]=(c[id][i]+1)%2; c[i][id]=c[id][i]; mp[id][i]=Min[id][i]; mp[i][id]=Min[id][i]; dfs(i,h); mp[id][i]=v; mp[i][id]=v; c[i][id]=cnt; c[id][i]=cnt; } } mp[id][id]=gg; ans=max(ans,sum); //cout<<ans<<endl; return ; } int main() { int n; scanf("%d",&n); memset(mp,0,sizeof(mp)); memset(c,0,sizeof(c)); for(int i=1;i<=4;i++) { for(int j=1;j<=4;j++) { Min[i][j]=INF; } } for(int i=1;i<=n;i++) { int x,value,y; scanf("%d%d%d",&x,&value,&y); if(y==x) { mp[x][y]+=value; continue; } mp[x][y]+=value; mp[y][x]+=value; Min[x][y]=min(Min[x][y],value); Min[y][x]=min(Min[y][x],value); c[x][y]++; c[y][x]++; } for(int i=1;i<=4;i++) { dfs(i,0); } printf("%d\n",ans); return 0; }感悟：转换成图，和偶数边的处理解题的关键，我也是看了大佬的才会，菜鸡有天也会变大佬。
