Peach Blossom Spring
Problem Description
Tao Yuanming(365-427) was a Chinese poet of Eastern Jin dynasty. One of his most famous works is "Peach Blossom Spring", which is a fable about a chance
discovery of an ethereal village where the people lead an ideal existence in harmony with nature, unaware of the outside world for centuries. So in Chinese, "Peach Blossom Spring" means "utopia".
In the story of "Peach Blossom Spring", there was a mysterious place. In Qin dynasty, some people escaped to that place during the civil unrest and built a village. They and their descendants never left and never had any contact with the outside world since then, until centuries latter a fisherman of Jin dynasty found them.
Recently, some Chinese ACMers happened to find the relics of the village mentioned in"Peach Blossom Spring".
They also found a document about building hiding places to escape from Qin army. The document said:
There were n houses and m roads in the village. Each road connected two houses. These houses were numbered from 1 to n. There were k families, each living in a different house.
The houses they lived were house 1, house 2, … , house k. There were also k broken houses: house n-k+1, house n-k+2, ... , house n, with secret basements so that those houses could be used as hiding places.
The problem was that all roads were broken. People wanted to repair some roads so that every family could reach a hiding place through the repaired roads. Every hiding place could only hold one family. Each road cost some labor to be repaired. The head of the village wanted to find out the minimum cost way of repairing the roads, but he didn't know how to do.
Would you solve the problem which the ancient village head never solved?
discovery of an ethereal village where the people lead an ideal existence in harmony with nature, unaware of the outside world for centuries. So in Chinese, "Peach Blossom Spring" means "utopia".
In the story of "Peach Blossom Spring", there was a mysterious place. In Qin dynasty, some people escaped to that place during the civil unrest and built a village. They and their descendants never left and never had any contact with the outside world since then, until centuries latter a fisherman of Jin dynasty found them.
Recently, some Chinese ACMers happened to find the relics of the village mentioned in"Peach Blossom Spring".
They also found a document about building hiding places to escape from Qin army. The document said:
There were n houses and m roads in the village. Each road connected two houses. These houses were numbered from 1 to n. There were k families, each living in a different house.
The houses they lived were house 1, house 2, … , house k. There were also k broken houses: house n-k+1, house n-k+2, ... , house n, with secret basements so that those houses could be used as hiding places.
The problem was that all roads were broken. People wanted to repair some roads so that every family could reach a hiding place through the repaired roads. Every hiding place could only hold one family. Each road cost some labor to be repaired. The head of the village wanted to find out the minimum cost way of repairing the roads, but he didn't know how to do.
Would you solve the problem which the ancient village head never solved?
Input
The input begins with a line containing an integer T(T<=50), the number of test cases. For each case, the first line begins with three integers ---- the above mentioned n (4<=n<=50), m (0<=m<=1000) and k (1<=k<=5, 2k<=n). Then m lines follow, each containing three integers u,v and w, indicating that there is a broken road connecting house u an d v, and the cost to repair that road is w(1<=w<=1000).
Output
For each test case, if you cannot find a proper way to repair the roads, output a string "No solution" in a line. Otherwise, output the minimum cost to repair the roads in a line.
Sample Input
2 4 3 1 4 2 10 3 1 9 2 3 10 6 7 2 1 5 1000 2 6 1000 1 3 1 2 3 1 3 4 1 4 5 1 4 6 1
Sample Output
29 5
Source
题目大意：T组数据， 对于每组数据给定一张n点m边的无向图， 要求选出一些边， 使得每个前k号点可以对应到达一个后k号点（点是唯一对应的），求最小代价， 若没有合法的方案则输出 "No solution"
斯坦纳树+DP
连接某些边使得给定点（前后k个点）互相到达且可经过一些非给定点（剩下的点）， 显然就是斯坦纳树
我们用斯坦纳树求出某些点给定点互相到达的代价
那么答案就是若干棵斯坦纳树相加
DP维护一个拥有若干个给定点的森林的最小代价（当然要排除不可行的方案）
那么答案就是拥有所有给定点的森林的代价
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int MaxN = 51;
const int MaxM = 2010;
const int MaxO = 1 << 10;
const int INF = 1e9;
int T, n, m, k, opt, tot;
int first[MaxN], nxt[MaxM], point[MaxM], val[MaxM];
int f[MaxN][MaxO], vis[MaxN], g[MaxO];
queue <int> Q;
void addEdge(int x, int y, int z) {
nxt[++tot] = first[x], first[x] = tot, point[tot] = y, val[tot] = z;
nxt[++tot] = first[y], first[y] = tot, point[tot] = x, val[tot] = z;
}
void SPFA(int opt) {
while (!Q.empty()) {
int u = Q.front();
vis[u] = 0;
Q.pop();
for (int k = first[u], v; v = point[k], k; k = nxt[k])
if (f[v][opt] > f[u][opt] + val[k]) {
f[v][opt] = f[u][opt] + val[k];
if (!vis[v]) {
vis[v] = 1;
Q.push(v);
}
}
}
}
bool check(int opt) {
int res = 0;
for (int l = opt, i = 1; l; l >>= 1, ++i)
if (l & 1) res += i <= k ? 1 : -1;
return !res;
}
int main()
{
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &k);
tot = 0;
memset(first, 0, sizeof(first));
for (int i = 1; i <= m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
}
opt = 1 << (k << 1);
for (int i = 1; i <= n; ++i)
for (int o = 0; o < opt; ++o)
f[i][o] = INF;
for (int i = 0; i < k; ++i)
f[i + 1][1 << i] = f[n - i][1 << (i + k)] = 0;
for (int o = 0; o < opt; ++o) {
for (int i = 1; i <= n; ++i) {
for (int op = o & o - 1; op; op = op - 1 & o)
f[i][o] = min(f[i][o], f[i][op] + f[i][o - op]);
if (f[i][o] != INF) Q.push(i), vis[i] = 1;
}
SPFA(o);
}
for (int o = 0; o < opt; ++o) {
g[o] = INF;
if (check(o))
for (int i = 1; i <= n; ++i)
g[o] = min(g[o], f[i][o]);
}
for (int o = 0; o < opt; ++o)
for (int op = o & o - 1; op; op = op - 1 & o)
g[o] = min(g[o], g[op] + g[o - op]);
if (g[opt - 1] != INF) printf("%d\n", g[opt - 1]);
else printf("No solution\n");
}
}
2018年11月29日 10:48
The change of the joy and all reflections has been ensured for the pats. The items and myassignmenthelp.com review have been joined for the flow of the fixation of the terms for the humans. The sign is assigned for the formation of the better and al approached items for the candidates.