Hexo
0%

分层图

Posted on In , ,
Symbols count in article: 3.6k Reading time ≈ 3 mins.

分层图

当我们要进行图的遍历的时候，有时会进行状态的变化，此时我们可以开多个维度的图，每种维度代表一种状态，当状态改变时就可以转移到另一个维度进行推进；

1.wyh的吃鸡

假设地图为n*n的一个图，图中有且仅有一块X的联通快代表安全区域，有一个起点S代表缩圈的时候的起点，图中C代表的是车（保证车的数量小于等于100），标记为.的代表空地，可以任意通过，O代表障碍物不能通过。每次没有车的时候2s可以走一个格（只能走自己的上下左右4个方向），有车的话时间为1s走一个格

现在告诉你最多能坚持的时间为t秒，问你在t秒内（含t秒）能否从s点到达安全区域，能的话输出YES，并且输出最短时间，不能的话输出NO。

此题为bfs，同时使用优先队列优化，我们需要把时间较小的放到队列前面，同时需要注意状态的改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# include <bits/stdc++.h>
using namespace std;
#define LL long long
LL int n,k;
int sx,sy;
char ju[105][105];//保存图形
bool ask[3][105][105];//标记（第一个维度为不同状态，后面两个维度为坐标）
bool pd[105][105];
struct note{
    int x,y;//坐标
    int s;//时间
    int c;//状态
    inline bool operator < (const note& p) const{
        return s>p.s;
    }
};
//方向
int ax[5],ay[5];

void Clear()
{
    memset(pd,0,sizeof pd);
    memset(ask,0,sizeof ask);
}
int main()

{
    ax[1]=-1,ay[1]=0;//zuo
    ax[2]=1,ay[2]=0;//you
    ax[3]=0,ay[3]=-1;//shang
    ax[4]=0,ay[4]=1;//xia
    int t;
    cin>>t;
    while(t--)
    {
        Clear();
        cin>>n>>k;
        for(int i=0;i<n;++i)
            cin>>ju[i];
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(ju[i][j]=='S')
                {
                    sx=i;
                    sy=j;
                }
            }
        }
        int sum=1e9;
        priority_queue<note>q;
        q.push(note{sx,sy,0,2});
        while(!q.empty())//bfs
        {
            note tmp=q.top();
            q.pop();
            int x=tmp.x, y=tmp.y;
            
            if(ask[tmp.c][x][y]||ju[x][y]=='O')
                continue;
            if(x<0||x>=n||y<0||y>=n) 
                continue;//cout<<tmp.c<<" "<<x<<" "<<y<<" "<<tmp.s<<endl;
            if(ju[x][y]=='X'){
                sum=min(sum,tmp.s);//找到更小的
                continue;
            }
            ask[tmp.c][x][y]=1;
            int c=2;
            if(ju[x][y]=='C')
                c=1;//状态改变
            for(int i=1;i<=4;++i){
                int tx=x+ax[i], ty=y+ay[i];
                q.push({tx,ty,tmp.s+min(tmp.c,c),min(tmp.c,c)});
            }
        }
        if(sum<=k)
            cout<<"YES"<<"\n"<<sum<<"\n";
        else
            cout<<"NO"<<"\n";
    }
}

2.对于每个点都可以选择下一条边是否赋予权值为0,那么我们就可以将图画出k+1层1

代码实现：

我们可以将dis数组开成二维dis[i][j]表示到达i号结点,用了j次免费操作!
比如dis[2][0]表示到达2号结点,没有用免费操作,也就是在第一层图移动。 比如dis[2][3],到达2号结点用了3次免费操作,那么**下一次移动应该在第3/4层图进行!**、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int maxn=5e4+10;
vector<PII>se[maxn];
int dis[maxn][20];
bool vis[maxn][20];
int n,m,k,s,t;

struct node{
	int id,v,used;//used使用了几次免费券,id为目标点，v为付出
	node(){}
	node(int id,int v,int used): id(id),v(v),used(used){}//构造器
	bool operator < (const node& a) const {
		return a.v<v;
	}
};

void dj(int u)
{
   memset(dis,0x3f3f3f3f,sizeof(dis));
   priority_queue<node>qu;
   qu.push(node(u,0,0));
   dis[u][0]=0;
   while(!qu.empty())
   {
      node tt=qu.top();
	  qu.pop();
	  int q=tt.id;//now
	  int p=tt.used;//目前层数
	  if(vis[q][p])
	  continue;
	  vis[q][p]=1;
       for(int i=0;i<se[q].size();++i)
	   {
		int next=se[q][i].first;//下一个连接点
		int val=se[q][i].second;//代价
		//两种i情况。用免费和不用免费
		//不用免费
		if(dis[next][p]>dis[q][p]+val)
		{
			dis[next][p]=dis[q][p]+val;
			qu.push(node(next,dis[next][p],p));
		}
		//用免费券
		if(p+1<=k&&dis[next][p+1]>dis[q][p]+0)
		{
			dis[next][p+1]=dis[q][p];
			qu.push(node(next,dis[next][p+1],p+1));
		}
	   }
   }
}


int main()
{
	cin>>n>>m>>k>>s>>t;
    for(int i=1;i<=m;++i)
	{
		int a,b,c;
		cin>>a>>b>>c;
        se[a].push_back({b,c});
		se[b].push_back({a,c});
	}
	dj(s);
	int ans=0x3f3f3f3f;
	for(int i=0;i<=k;++i)
	{
		ans=min(ans,dis[t][i]);
	}
	cout<<ans<<endl;
}