「POJ2404」Jogging Trails
Description
Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.
Input
Input consists of several test cases. The first line of input for each case contains two positive integers: n <= 15, the number of water stations, and m < 1000, the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord’s route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.
Output
For each case, there should be one line of output giving the length of Gord’s jogging route.
Sample Input
|
1 2 3 4 5 6 7 |
4 5 1 2 3 2 3 4 3 4 5 1 4 10 1 3 12 0 |
Sample Output
|
1 |
41 |
题解
带权无向图上的中国邮路问题
若原图不连通则无解。若所有点的度均为偶数，则存在欧拉回路，所有边权加和即为结果。
否则必有偶数个奇度点，将这些奇点拉出来构建新图，任意两点之间的边权为原图中两点之间的最短距离，对新图求一次一般图的最小权完美匹配，加上原图所有边权和即为最终结果。
本题最小权完美匹配用状压DP解决，或者带花树~ TAT 流算法是不正确的。
|
1 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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ed,tot,top; int d[20],q[20]; int f[32768],dis[20][20]; int bin[20]; void floyd() { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } void dp() { memset(f,127/3,sizeof(f)); f[0]=0; for(int i=0;i<ed;i++) { int x=1; while(bin[x-1]&i)x++; for(int y=x+1;y<=top;y++) if((i&bin[y-1])==0) f[i|bin[y-1]|bin[x-1]]=min(f[i|bin[y-1]|bin[x-1]],f[i]+dis[q[x]][q[y]]); } } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; while(1) { top=tot=0; memset(dis,127/3,sizeof(dis)); memset(d,0,sizeof(d)); n=read();if(!n)return 0; m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); dis[u][v]=dis[v][u]=min(dis[u][v],w); d[u]++;d[v]++;tot+=w; } floyd(); for(int i=1;i<=n;i++) if(d[i]&1)q[++top]=i; ed=bin[top]-1; dp(); printf("%d\n",f[ed]+tot); } return 0; } |
Subscribe
计数器 9318733
OI 课件=>
OI 课件=>