【图论专题四】【JSOI2013】吃货JYY

本文主要是介绍【图论专题四】【JSOI2013】吃货JYY，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【江苏省省选2013】吃货JYY

【JSOI2013】吃货JYY (Standard IO)
Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits

Description
世界上一共有N个JYY愿意去的城市，分别从1编号到N。JYY选出了K个他一定要乘坐的航班。除此之外，还有M个JYY没有特别的偏好，可以乘坐也可以不乘坐的航班。
一个航班我们用一个三元组(x,y,z)来表示，意义是这趟航班连接城市x和y，并且机票费用是z。每个航班都是往返的，所以JYY花费z的钱，既可以选择从x飞往y，也可以选择从y飞往x。
南京的编号是1，现在JYY打算从南京出发，乘坐所有K个航班，并且最后回到南京，请你帮他求出最小的花费。

Input
输入数据的第一行包含两个整数N和K；
接下来K行，每行三个整数x，y，z描述必须乘坐的航班的信息，数据保证在这K个航班中，不会有两个不同的航班在同一对城市之间执飞；
第K+2行包含一个整数M；
接下来M行，每行三个整数x，y，z 描述可以乘坐也可以不乘坐的航班信息。

Output
输出一行一个整数，表示最少的花费。数据保证一定存在满足JYY要求的旅行方案。

Sample Input
6 3
1 2 1000
2 3 1000
4 5 500
2
1 4 300
3 5 300

Sample Output
3100

Data Constraint
对于10%的数据满足N≤4；
对于30%的数据满足N≤ 7；
对于额外30%的数据满足，JYY可以只通过必须乘坐的K个航班从南京出发到达任意一个城市；
对于100%的数据满足2≤N≤13，0≤K≤78，2 ≤M ≤ 200，1 ≤x,y ≤N，1 ≤z ≤ 10^4。

Hint
样例说明：一个可行的最佳方案为123541。机票所需的费用为1000+1000+300+500+300=3100。

题解

我们发现N很小。可以考虑状态压缩。压缩点。怎么压缩点呢？我们可以发现，如果从1（南京）走回1（南京），这个可以构成一个每一个点都是偶数度的欧拉回路。欧拉回路的每一个点的度数都是偶数！这是不是可以状态压缩呢？

正解

压缩每一个点的状态（0：没有经过、1：度数为奇数、2：度数为偶数）。然后最后将奇数度数的点两两匹配，跑一个floyed预处理。最后取一个最小值。

代码

#include<cstdio>
#include<cstring>
#define N 14  //江苏有13个城市
#define K 79
#define M 201
#define MAX_f 1594323
using namespace std;
int n,m,k,total1;
int th3[N],next[(M+K)*2],head[(M+K)*2],edge[(M+K)*2],cost[(M+K)*2],must[N][N],zhuan[MAX_f][N],f[MAX_f],g[N][N];
bool bo[N];
int add(int x,int x1,int y1)
{if (zhuan[x][n-x1+1]<=1) x+=th3[x1];else	x-=th3[x1];if (zhuan[x][n-y1+1]<=1) x+=th3[y1];else	x-=th3[y1];return x;
}
void insert(int x,int y,int z)
{total1++;next[total1]=head[x];head[x]=total1;edge[total1]=y;cost[total1]=z;
}
void zhuan_3(int k)
{zhuan[k][0]=n;int p=k;while (p>0){zhuan[k][zhuan[k][0]]=p%3;zhuan[k][0]--;p=p/3;}zhuan[k][0]=0;for (int i=1;i<=n;i++){if (zhuan[k][i]!=0)zhuan[k][0]=zhuan[k][0]+1;}
}
int main()
{scanf("%d%d",&n,&k);for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){g[i][j]=9999999;}}memset(bo,false,sizeof(bo));int ad=0;for (int i=1;i<=k;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);ad+=z;bo[x]=true;bo[y]=true;must[x][y]=z;must[y][x]=z;if (g[x][y]>z){g[x][y]=z;g[y][x]=z;}}scanf("%d",&m);for (int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if (g[x][y]>z){g[x][y]=z;g[y][x]=z;}}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (g[i][j]!=9999999){insert(i,j,g[i][j]);}}}m=k;th3[1]=1;for (int i=2;i<=n+1;i++){th3[i]=th3[i-1]*3;}for (int i=0;i<=th3[n+1]-1;i++){zhuan_3(i);}for (int i=0;i<=th3[n+1]-1;i++){f[i]=9999999;}f[2]=0;for (int i=1;i<=n;i++){for (int j=0;j<=th3[n+1]-1;j++){if (zhuan[j][0]==i&&f[j]<9000000){if (zhuan[j][1]==0&&zhuan[j][2]==0&&zhuan[j][3]==1&&zhuan[j][4]==0&&zhuan[j][5]==1){i++;i--;}if (j==772){j++;j--;}if (zhuan[j][6]==1&&zhuan[j][5]==2&&zhuan[j][4]==1){n++;n--;}bool bzp=true;for (int k=1;k<=n;k++){if (zhuan[j][n-k+1]!=0){for (int p=1;p<=n;p++){if (must[k][p]!=0&&zhuan[j][n-p+1]==0){int s=j;bzp=false;s=add(s,k,p);for (int q=head[p];q;q=next[q]){int y=edge[q];if (must[p][y]!=0&&zhuan[j][n-y+1]!=0&&y!=k)s=add(s,p,y);}if (f[s]>f[j])f[s]=f[j];}}}}if (bzp==false) continue;for (int k=1;k<=n;k++){if (zhuan[j][n-k+1]!=0){int pq=zhuan[j][n-k+1];for (int p=head[k];p;p=next[p]){int y=edge[p];int s1=j;if (zhuan[j][n-y+1]==0){s1=add(s1,k,y);if (f[s1]>f[j]+cost[p])f[s1]=f[j]+cost[p];}}}}}}}for (int k=1;k<=n;k++){for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (g[i][j]>g[i][k]+g[k][j]){g[i][j]=g[i][k]+g[k][j];}}}}for (int i=0;i<=th3[n+1]-1;i++){if (i==772){i++;i--;}if (f[i]>9000000) continue;bool bz=true;for (int j=1;j<=n;j++){if (bo[j]==true&&zhuan[i][n-j+1]==0){bz=false;break;}}if (bz==false) continue;int first=0;for (int j=1;j<=n;j++){if (zhuan[i][n-j+1]==1){first=j;break;}}for (int j=first+1;j<=n;j++){if (zhuan[i][n-j+1]==1){int s=i;s+=th3[first];s+=th3[j];if (f[s]>f[i]+g[first][j]){f[s]=f[i]+g[first][j];}if (s==782){j++;j--;}if (zhuan[s][1]==2&&zhuan[s][4]==2&&zhuan[s][5]==2&&zhuan[s][6]==2&&zhuan[s][7]==2){j++;j--;}}}}int min=99999999;for (int i=0;i<=th3[n+1]-1;i++){if (f[i]>9000000) continue;bool bz=true;for (int j=1;j<=n;j++){if (bo[j]==true&&zhuan[i][n-j+1]==0){bz=false;break;}if (zhuan[i][n-j+1]==1){bz=false;break;}}if (bz==false) continue;if (min>f[i]) min=f[i];if (f[i]<100000){f[i]++;f[i]--;}}printf("%d",min+ad);
}