网站引导页利弊,全国新农村建设中心网站,有多少人自己做电影网站,生鲜做的好的网站正题
luogu 6085 题目大意
给你一个无向图#xff0c;其中有一些边是必须走的#xff0c;问你从1开始走#xff0c;经过所有必须走的边#xff0c;然后回到1的最短路径 解题思路
n很小#xff0c;可以先用Floyd跑出两个点之间的最短路
然后状压DP#xff0c;每个点存…正题
luogu 6085 题目大意
给你一个无向图其中有一些边是必须走的问你从1开始走经过所有必须走的边然后回到1的最短路径 解题思路
n很小可以先用Floyd跑出两个点之间的最短路
然后状压DP每个点存三种状态 0.不在连通图内 1.在连通图内且连边为奇数 2.在连通图内且连边为偶数
遍历所有状态每个状态找不在连通图内的点然后和连通图内一点连边然后记录奇偶性必要的边不记录
枚举完所有状态后把必要的边加进里面然后对于连边为奇数的找到一种最小代价连接方式这样可以构造一条回路 代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 1594323
using namespace std;
int n, m, k, x, y, z, p, MX, nec, sum, ans, tot, h[100], v[100], g[10000], deg[100], dis[100][100];
int f[N 10];
queueintd;
struct rec
{int to, l, next;
}e[200];
void add(int x, int y, int z)
{e[tot].to y;e[tot].l z;e[tot].next h[x];h[x] tot;
}
int main()
{memset(dis, 127/3, sizeof(dis));memset(g, 127/3, sizeof(g));memset(f, 127/3, sizeof(f));MX g[0];scanf(%d%d, n, m);for (int i 1; i m; i){scanf(%d%d%d, x, y, z);x--;y--;add(x, y, z);add(y, x, z);dis[x][y] dis[y][x] min(dis[x][y], z);nec ^ (1x) ^ (1y);deg[x];deg[y];sum z;}scanf(%d, m);for (int i 1; i m; i){scanf(%d%d%d, x, y, z);x--;y--;dis[x][y] dis[y][x] min(dis[x][y], z);}v[0] 1;dis[0][0] 0;for (int i 1; i n; i)v[i] v[i - 1] * 3, 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)dis[i][j] min(dis[i][j], dis[i][k] dis[k][j]);//Floydg[0] 0;for (int now 0; now (1n); now)for (int i 0; i n; i)if (!(now (1i)))for (int j i 1; j n; j)if (!(now (1j))){k now ^ (1i) ^ (1j);g[k] min(g[k], g[now] dis[i][j]);//预处理奇数点的连边}d.push(2);f[2] 0;while(!d.empty()){int now d.front();d.pop();for (int i 0; i n; i){if (now / v[i] % 3) continue;k now v[i] * 2;//必须的连边不算奇偶性for (int j h[i]; j; j e[j].next){if (!(now / v[e[j].to] % 3)) continue;if (f[k] MX) d.push(k);f[k] min(f[k], f[now]);}for (int j 0; j n; j)//不必须的连边{if (!(now / v[j] % 3)) continue;k now v[i];if (now / v[j] % 3 2) k - v[j];//计算奇偶性else k v[j];if (f[k] MX) d.push(k);f[k] min(f[k], f[now] dis[j][i]);}}}ans MX;for (int now 0; now v[n]; now){p 0;k 0;for (int i 0; i n; i){if (!(now / v[i] % 3) deg[i])//有必须的点不在连通图内{p 1;break;}if (now / v[i] % 3) k ^ (1i) * (now / v[i] % 3 1? 1: 0);//计算奇偶性}if (p) continue;k ^ nec;ans min(ans, f[now] g[k]);}printf(%d, sum ans);return 0;
}
