4774: 修路
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 290 Solved: 137
[Submit][Status][Discuss]
Description
村子间的小路年久失修，为了保障村子之间的往来，法珞决定带领大家修路。对于边带权的无向图 G = (V, E)，
请选择一些边，使得1 <= i <= d， i号节点和 n - i + 1 号节点可以通过选中的边连通，最小化选中的所有边
的权值和。
Input
第一行两个整数 n, m，表示图的点数和边数。接下来的 m行，每行三个整数 ui, vi, wi，表示有一条 ui 与 vi
之间，权值为 wi 的无向边。
1 <= d <= 4
2d <= n <= 10^4
0 <= m <= 10^4
1 <= ui, vi <= n
1 <= wi <= 1000
Output
一行一个整数，表示答案，如果无解输出-1
Sample Input
10 20 1
6 5 1
6 9 4
9 4 2
9 4 10
6 1 2
2 3 6
7 6 10
5 7 1
9 7 2
5 9 10
1 6 8
4 7 4
5 7 1
2 6 9
10 10 6
8 7 2
10 9 10
1 2 4
10 1 8
9 9 7
6 5 1
6 9 4
9 4 2
9 4 10
6 1 2
2 3 6
7 6 10
5 7 1
9 7 2
5 9 10
1 6 8
4 7 4
5 7 1
2 6 9
10 10 6
8 7 2
10 9 10
1 2 4
10 1 8
9 9 7
Sample Output
8
分析：斯坦纳树模板题.维护数组f[i][j]表示从i出发，使得状态为j的最小花费,这里的状态是用二进制表示的:01010101之类的，如果第i位为1，表示第i号点已经被连通.再维护一个数组g[i],表示状态为j的最小花费，这里就不管是从哪个点出发了.g[j] = min{f[i][j]}.
最后更新g[i]用i的子集更新.若i的子集j满足条件(如果点p连通了，那么点p+d也连通)，并且j^i也满足条件，就更新g[i].为什么要判断是否满足条件才能更新呢？例子：
最后输出答案g[1 << (2 * d) - 1].
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int maxn = ,inf = 0x7ffffff; int n,m,d,head[maxn],to[maxn],nextt[maxn],w[maxn],tot = ,f[maxn][ << ],g[ << ],maxx,vis[maxn],dis[maxn];
queue <int> q; void add(int x,int y,int z)
{
w[tot] = z;
to[tot] = y;
nextt[tot] = head[x];
head[x] = tot++;
} void spfa(int sta)
{
memset(vis,,sizeof(vis));
queue <int> q;
for (int i = ; i <= n; i++)
{
q.push(i);
vis[i] = ;
}
while (!q.empty())
{
int u = q.front();
q.pop();
vis[u] = ;
for (int i = head[u];i;i = nextt[i])
{
int v = to[i];
if (f[v][sta] > f[u][sta] + w[i])
{
f[v][sta] = f[u][sta] + w[i];
if (!vis[v])
{
vis[v] = ;
q.push(v);
}
}
}
}
} bool check(int sta)
{
for (int i = ; i < d; i++)
{
int temp = << i;
if (sta & temp)
{
int temp2 = << (i + d);
if (!(sta & temp2))
return false;
}
temp = << (i + d);
if (sta & temp)
{
int temp2 = << i;
if (!(sta & temp2))
return false;
}
}
return true;
} int main()
{
scanf("%d%d%d",&n,&m,&d);
for (int i = ; i <= m; i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
maxx = ( << ( * d));
for (int i = ; i <= n; i++)
for (int j = ; j < maxx; j++)
f[i][j] = inf,g[j] = inf;
for (int i = ; i <= d; i++)
{
f[i][ << (i - )] = ;
f[n - i + ][ << (d + i - )] = ;
} for (int j = ; j < maxx; j++)
{
for (int i = ; i <= n; i++)
{
for (int k = j; k; k = (k - ) & j)
f[i][j] = min(f[i][j],f[i][k] + f[i][j ^ k]);
}
spfa(j);
for (int i = ; i <= n; i++)
g[j] = min(g[j],f[i][j]);
}
for (int i = ; i < maxx; i++)
for (int j = i; j; j = (j - ) & i)
if (check(j) && check(i ^ j))
g[i] = min(g[i],g[j] + g[j ^ i]);
if (g[maxx - ] < inf)
printf("%d\n",g[maxx - ]);
else
puts("-1"); return ;
}