NC20604. [ZJOI2014]璀灿光华
描述
输入描述
第一行是a, 表示水晶立方体的边长.
接下来a^3行, 每行若干整数. 第一个数g[i] 表示第i块水晶的好看程度,如果g[i] =0, 代表这块水晶会发光. 接下来 3-6 个整数, 代表与这块水晶有共同而的水晶编号.
输出描述
两个整数，最小值最大值
示例1
输入:
2 0 7 2 3 0 8 1 4 4 5 4 1 8 6 3 2 16 3 6 7 32 4 5 8 1 1 8 5 2 2 7 6
输出:
0 12
C++14(g++5.4) 解法, 执行用时: 983ms, 内存消耗: 31472K, 提交时间: 2020-10-12 20:25:57
#include <cstring>
#include <iostream>
#include <fstream>
#include <sstream>//stringstream
#include <queue>
using namespace std;
const int maxm = 2058000;//這裏的最大邊數我是把點數加起來乘了6
const int maxn = 75*75*75;
const int inf = 0x3f3f3f3f;
int n;//總個數
int tn;//邊長
struct Edge
{
int to, nxt;
} e[maxm<<1];
int first[maxn];
int cnt;
inline void add_edge(int f, int t)
{
e[++cnt].nxt = first[f];
first[f] = cnt;
e[cnt].to = t;
}
int dirx[] = {1, -1, 0, 0, 0, 0};
int diry[] = {0, 0, 1, -1, 0, 0};
int dirz[] = {0, 0, 0, 0, 1, -1};
int dep[maxn];//"好看程度"
int vis[maxn];
int minn = inf;
int maxx = -inf;
int ll[10];//會發光的水晶的編號
int ddn[maxn];//度數
int zl;//這是個ddn的cnt
int mmap[73][73][73];
struct zb
{
int x, y, z;
} poi[maxn];
#define pan (x > 0 && x <= tn && y > 0 && y <= tn && z > 0 && z <= tn)
#define nxxt x += dirx[i], y += diry[i], z += dirz[i]
inline int getans(int i, zb a)//能加多少"好看程度"
{
int ans = 0;
int x = a.x, y = a.y, z = a.z;
for(; pan; nxxt)
if(!vis[mmap[x][y][z]]++)//由於待會兒回溯時要刪除，所以懶到家的我就直接用++,--代替記錄了
ans += dep[mmap[x][y][z]];
return ans;
}
inline void delvis(int i, zb a)//回溯時把dfs前加的vis刪除
{
int x = a.x, y = a.y, z = a.z;
for(; pan; nxxt)
vis[mmap[x][y][z]]--;
}
inline void dfs(int now, int ans)//大力枚舉所有情況
{
if(now > zl)
{
minn = min(minn, ans);
maxx = max(maxx, ans);
return;
}
for(int i = 0; i < 6; ++i)
{
dfs(now+1, ans + getans(i, poi[ll[now]]));
delvis(i, poi[ll[now]]);
}
}
int dist[4][maxn];
int di[4];
bool viss[maxn];
inline void bfs(int id)//求最短路
{
memset(viss, 0, sizeof(viss));
queue<int> q;
int from = di[id];
viss[from] = true;
q.push(from);
while(!q.empty())
{
int now = q.front();
q.pop();
for(int i = first[now]; i; i = e[i].nxt)
{
int to = e[i].to;
if(!viss[to])
{
viss[to] = true;
dist[id][to] = dist[id][now] + 1;
q.push(to);
}
}
}
}
int main()
{
ios:: sync_with_stdio(false);
cin >> n;
tn = n;
string tmp;
getline(cin, tmp);
n *= n * n;
for(int i = 1; i <= n; ++i)
{
getline(cin, tmp);
stringstream ss(tmp);
ss >> dep[i];
int aa;
if(!dep[i])
{
vis[i] = true;
ll[++zl] = i;
}
while(ss >> aa)
{
add_edge(i, aa);
ddn[i]++;
}
}
for(di[0] = 1; ddn[di[0]] > 3; ++di[0]);
bfs(0);
for(int i = 1; i <= n; ++i)
{
if(ddn[i] == 3 && dist[0][i] == ((tn-1)<<1))
{
di[1] = i;
break;
}
}
bfs(1);
for(int i = 1; i <= n; ++i)//得到z
{
poi[i].z = (dist[0][i] + dist[1][i] - ((tn-2)<<1)) >> 1;
if(poi[i].z == tn && dist[0][i] == dist[1][i] && ddn[i] == 3)
di[2] = i;
}
bfs(2);
for(int i = 1; i <= n; ++i)//得到x, y
{
poi[i].x = (dist[0][i] + dist[2][i] - ((tn-1)<<1)) >> 1;
poi[i].y = (dist[0][i] - poi[i].x - poi[i].z) + 1;
poi[i].x++;
poi[i].y++;
mmap[poi[i].x][poi[i].y][poi[i].z] = i;
}
dfs(1, 0);
cout << minn << ' ' << maxx << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1520ms, 内存消耗: 31480K, 提交时间: 2020-03-10 11:54:53
#include<cstring>
#include<iostream>
#include<fstream>
#include<sstream>
#include<queue>
using namespace std;
const int maxm=2058000;
const int maxn=75*75*75;
const int inf=0x3f3f3f3f;
int n;
int tn;
struct Edge
{
int to,nxt;
}e[maxm<<1];
int first[maxn];
int cnt;
inline void add_edge(int f,int t)
{
e[++cnt].nxt=first[f];
first[f]=cnt;
e[cnt].to=t;
}
int dirx[]={1,-1,0,0,0,0};
int diry[]={0,0,1,-1,0,0};
int dirz[]={0,0,0,0,1,-1};
int dep[maxn];
int vis[maxn];
int minn=inf;
int maxx=-inf;
int ll[10];
int ddn[maxn];
int zl;
int mmap[73][73][73];
struct zb
{
int x,y,z;
}poi[maxn];
#define pan (x>0&&x<=tn&&y>0&&y<=tn&&z>0&&z<=tn)
#define nxxt x+=dirx[i],y+=diry[i],z+=dirz[i]
inline int getans(int i,zb a)
{
int ans=0;
int x=a.x,y=a.y,z=a.z;
for(;pan;nxxt)
if(!vis[mmap[x][y][z]]++)
ans+=dep[mmap[x][y][z]];
return ans;
}
inline void delvis(int i,zb a)
{
int x=a.x,y=a.y,z=a.z;
for(;pan;nxxt)
vis[mmap[x][y][z]]--;
}
inline void dfs(int now,int ans)
{
if(now>zl)
{
minn=min(minn,ans);
maxx=max(maxx,ans);
return;
}
for(int i=0;i<6;++i)
{
dfs(now+1,ans+getans(i,poi[ll[now]]));
delvis(i,poi[ll[now]]);
}
}
int dist[4][maxn];
int di[4];
bool viss[maxn];
inline void bfs(int id)
{
memset(viss,0,sizeof(viss));
queue<int> q;
int from=di[id];
viss[from]=true;
q.push(from);
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=first[now];i;i=e[i].nxt)
{
int to=e[i].to;
if(!viss[to])
{
viss[to]=true;
dist[id][to]=dist[id][now]+1;
q.push(to);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
tn=n;
string tmp;
getline(cin,tmp);
n*=n*n;
for(int i=1;i<=n;++i)
{
getline(cin,tmp);
stringstream ss(tmp);
ss>>dep[i];
int aa;
if(!dep[i])
{
vis[i]=true;
ll[++zl]=i;
}
while(ss>>aa)
{
add_edge(i,aa);
ddn[i]++;
}
}
for(di[0]=1;ddn[di[0]]>3;++di[0]);
bfs(0);
for(int i=1;i<=n;++i)
{
if(ddn[i]==3&&dist[0][i]==((tn-1)<<1))
{
di[1]=i;
break;
}
}
bfs(1);
for(int i=1;i<=n;++i)
{
poi[i].z=(dist[0][i]+dist[1][i]-((tn-2)<<1))>>1;
if(poi[i].z==tn&&dist[0][i]==dist[1][i]&&ddn[i]==3)
di[2]=i;
}
bfs(2);
for(int i=1;i<=n;++i)
{
poi[i].x=(dist[0][i]+dist[2][i]-((tn-1)<<1))>>1;
poi[i].y=(dist[0][i]-poi[i].x-poi[i].z)+1;
poi[i].x++;
poi[i].y++;
mmap[poi[i].x][poi[i].y][poi[i].z]=i;
}
dfs(1,0);
cout<<minn<<' '<<maxx<<endl;
return 0;
}