连着三发 UKE
查看原帖
连着三发 UKE
151601
Aphros楼主2021/5/23 21:13

rt

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <iomanip>
#include <queue>

using namespace std;

typedef pair<int,int> pii;
const int MAXN = 110;
const int MAXM = 410;
const int MAXS = (1<<10)+10;
const int INF = 0x3f3f3f3f;

inline void prework()
{

}

int n, m, a[MAXN];
struct edge{
    int ne, to;
    edge(int N=0,int T=0):ne(N),to(T){}
}e[MAXM<<1];
int fir[MAXN], num = 0;
inline void join(int a, int b)
{
    e[++num] = edge(fir[a], b);
    fir[a] = num;
}
inline int id(int i, int j) {return (i-1)*m+j;}
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
inline bool in(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
pii pre[MAXN][MAXS];

int f[MAXN][MAXS];
priority_queue<pii,vector<pii>,greater<pii> > q;

inline void dijk(int S)
{
    while(!q.empty())
    {
        int u = q.top().second, d = q.top().first;
        q.pop();
        if(f[u][S] != d) continue;
        for(int i=fir[u];i;i=e[i].ne)
        {
            int v = e[i].to;
            if(f[v][S] > f[u][S] + a[v])
            {
                f[v][S] = f[u][S] + a[v];
                pre[v][S] = make_pair(u, S);
                q.push(make_pair(f[v][S], v)); 
            }
        }
    }
    while(!q.empty()) q.pop();
}
bool vis[MAXN];
void dfs(int u, int s)
{
    vis[u] = 1;
    if(pre[u][s].first + pre[u][s].second > 0)
    {
        int v = pre[u][s].first, t = pre[u][s].second;
        if(u == v) dfs(v, t), dfs(v, s^t);
        else dfs(v, s);
    }
}

inline void work()
{
    scanf("%d%d",&n,&m);
    memset(f, 0x3f, sizeof(f));
    for(int i=1;i<=n*m;i++) f[i][0] = 0;
    int cnt = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[id(i,j)]);
            for(int k=0;k<4;k++)
            {
                int x = i+dx[k], y = j+dy[k];
                if(in(x, y)) join(id(i, j), id(x, y));
            }
            if(!a[id(i,j)]) f[id(i,j)][(1<<cnt++)] = 0;
        }
    }
    int maxs = 1<<cnt;
    for(int s=0;s<maxs;s++)
    {
        for(int i=1;i<=n*m;i++)
        {
            for(int t=(s-1)&s;t;t=(t-1)&s)
            {
                if(f[i][s] > f[i][t]+f[i][s^t]-a[i])
                    f[i][s] = f[i][t] + f[i][s^t] - a[i], 
                    pre[i][s] = make_pair(i, t);
            }
            if(f[i][s] < INF)
                q.push(make_pair(f[i][s], i));
        }
        dijk(s);
    }
    int ansVal = INF, ansInd = 0;
    for(int i=1;i<=n*m;i++)
        if(f[i][maxs-1] < ansVal)
            ansVal = f[i][maxs-1], ansInd = i;
    dfs(ansInd, maxs-1);
    printf("%d\n",ansVal);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            putchar(!a[id(i,j)]?'x':vis[id(i,j)]?'o':'-');
            if(j == m) putchar('\n');
        }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("mine.in","r",stdin);
    freopen("mine.out","w",stdout);
#endif
    clock_t st = clock();
    prework();
    int T = 1;
    while(T--) work();
    clock_t et = clock();
    cerr << "The run time is: " <<(int)(et - st) / CLOCKS_PER_SEC << "s" << endl;
    return 0;
}
2021/5/23 21:13
加载中...