Pre
作为斯坦纳树的第一道题
Solution
以每一个格子建立点，然后直接跑斯坦纳树就可以了。
code
#include <cstdio>
#include <bitset>
#include <iostream>
#include <queue>
#include <limits.h>
#include <cstring>
#define ll long long
#define xx first
#define yy second
#define testname kkksc03
using namespace std;
const int N = 100 + 5, M = 10 + 5, mx = 2139062143, NN = 2800;
struct _in {
const _in operator , (int &a) const {
a = 0;
char k = getchar ();
int f = 1;
while (k > '9' || k < '0') {
if (k == '-') f = -1;
k = getchar ();
}
while (k >= '0' && k <= '9') {
a = a * 10 + k - '0';
k = getchar ();
}
a *= f;
return*this;
}
};
inline int add (int u, int v) {
if (u == mx || v == mx) return mx;
else return u + v;
}
inline int mns (int u, int v) {
return u == mx ? mx : u - v;
}
inline int min (int u, int v) {
return u > v ? v : u;
}
inline int max (int u, int v) {
return u > v ? u : v;
}
int dp[N][NN], n, m, mp[M][M];
inline int get (int x, int y) {
return (x - 1) * m + y;
}
inline int GetLne (int x) {
return (x - 1) / m + 1;
}
inline int GetCol (int x) {
return (x - 1) % m + 1;
}
int anspos;
queue<int> q;
bool inq[N];
pair<int, int> s[N][NN];
inline void update (int u, int v, int w) {
if (dp[v][w] > add (dp[u][w], mp[GetLne (v)][GetCol (v)])) {
dp[v][w] = add (dp[u][w], mp[GetLne (v)][GetCol (v)]);
s[v][w] = make_pair (u, w);
if (!inq[v]) {
inq[v] = 1;
q.push (v);
}
}
}
inline void SPFA (int st) {
while (!q.empty ()) {
int tmp = q.front ();
q.pop ();
inq[tmp] = 0;
int x = GetLne (tmp), y = GetCol (tmp);
if (x != 1) update (tmp, tmp - m, st);
if (x != n) update (tmp, tmp + m, st);
if (y != 1) update (tmp, tmp - 1, st);
if (y != m) update (tmp, tmp + 1, st);
}
}
int k;
int op[M][M];
inline void dfs (int u, int v) {
// printf ("%d ", u);
// cout << bitset <8> (v) << " ";
// printf ("%d ",s[u][v].xx);
// cout << bitset <8> (s[u][v].yy) << endl;
if (s[u][v].xx == -1) {
int x = GetLne (u), y = GetCol (u);
if (!mp[x][y]) op[x][y] = 'x';
else op[x][y] = 'o';
return ;
}
int x = GetLne (u), y = GetCol (u);
op[x][y] = mp[x][y] ? 'o' : 'x';
x = s[u][v].xx, y = s[u][v].yy;
dfs (x, y);
if (x == u) dfs (u, y ^ v);
}
int main () {
// #ifdef chitongz
// freopen ("x.in", "r", stdin);
// freopen ("x.out", "w", stdout);
// #endif
memset (dp, 127, sizeof dp);
memset (s, -1, sizeof s);
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
op[i][j] = '_';
scanf ("%d", &mp[i][j]);
if (!mp[i][j]) {
anspos = get (i, j);
++k;
dp[get (i, j)][1 << (k - 1)] = 0;
}
}
}
int ans = INT_MAX;
for (int j = 1; j <= (1 << k) - 1; ++j) {
for (int i = 1; i <= n * m; ++i) {
for (int tmp = j; tmp; tmp = (tmp - 1) & j) {
if (dp[i][j] > mns (add (dp[i][tmp], dp[i][tmp ^ j]), mp[GetLne (i)][GetCol (i)])) {
dp[i][j] = mns (add (dp[i][tmp], dp[i][tmp ^ j]), mp[GetLne (i)][GetCol (i)]);
s[i][j] = make_pair (i, tmp);
}
if (dp[i][j] != dp[0][0]) {
q.push (i);
inq[i] = 1;
}
}
}
SPFA (j);
}
for (int i = 1; i <= n * m; ++i) {
if (dp[i][(1 << k) - 1] < ans) {
ans = dp[i][(1 << k) - 1];
anspos = i;
}
}
printf ("%d
", ans);
dfs (anspos, (1 << k) - 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf ("%c", op[i][j]);
}
puts ("");
}
return 0;
}
Conclusion
空间开小查错查了半天没有查出来，交上去发现 (M) 一般应该是 (10 + 5) ，我写的 (M=10)