T3 赤键救赎 题解

前言

原本是按蓝题（提高+、省选-）标准出的题目。难度应该排在小P前。

但是，赛时发现大家都在小P拿到了70乃至90的成绩，而本题无人拿到部分分。分析提交的代码，绝大多数人都选择不可以总司令（输出hungry）而将50的部分分抛弃。

题意

简而言之，在一张网格图上有$q$个带权值格和一个出发格和一个终止格，要求在从出发格通过不超过$p$个无权值格（红房间）到达终止格能取得的最大价值。

10分做法

注意到对于$10\%$的数据，$n,m\le2$

这说明地图最大为$2\times2$的网格图

当无法从出发格到达终止格，或最大权值小于0时，输出hungry

否则输出最大权值和

30分做法

注意到对于另$20\%$的数据，$n=1或m=1$

则该图为一条直线。

因此考虑每个包含出发格与终止格且不超过p个无权值格的区间，记录最大区间和。

如果最大区间和小于$0$或无法从出发格到达终止格，输出hungry

50分做法

注意到对于$50\%$的数据，$wi>0$

则所有格权值不为负。

连接出发格与终止格，贪心连点，check是否满足不超过p个无权值格即可

100分做法

我们可以将图上所有带权值格、出发格与终止格看做点，在点与点之间两两连边，边权为从一个点不经过其他点到达另一点所经过的无权值格数量。特别的如无法不经过其他点则不连边或边权为正无穷。代码实现使用bfs。

我们发现，连接几个点所需经过的最小无权值格数为这几个点的最小生成树大小。

因此，二进制枚举所有要包含的点（必须包含出发格与终止格），统计点权和，check最小生成树大小是否不大于p。

最终答案为最大点权和。如最大点权和小于0，输出hungry。

标程

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3000;
struct qwe{
	ll x,y,w;
}ppx[N],hr[N];
ll T,n,m,sx,sy,tx,ty,p,q,cnt,summ,ans,tot;
ll a[N][N],ma[N][N],dis[N][N],bin[N];
ll fa[N];
ll dx[5]={0,0,-1,1},dy[5]={1,-1,0,0};
bool vis[N][N];
bool cmp(qwe x,qwe y)
{
	return x.w<y.w;
}
ll get(ll x)
{
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
}
void clear()
{
    for(int i=1;i<=q;i++)
    {
        ppx[i].x=ppx[i].y=ppx[i].w=0;
        hr[i].x=hr[i].y=hr[i].w=0;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            vis[i][j]=false;
            a[i][j]=ma[i][j]=0;
        }
    }
    cnt=0;ans=-1e18;
}
void bfs(ll x)
{
	queue<pair<ll,ll> > q;
	queue<ll> pd;
	q.push(make_pair(ppx[x].x,ppx[x].y));
	pd.push(0);
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)vis[i][j]=false;
	}
	vis[ppx[x].x][ppx[x].y]=true;
	while(!q.empty())
	{
		ll nx=q.front().first;
		ll ny=q.front().second;
		ll dep=pd.front();
		q.pop();
		pd.pop();
		for(int i=0;i<=3;i++)
		{
			ll wx=nx+dx[i];
			ll wy=ny+dy[i];
			if(wx<1||wx>n||wy<1||wy>m)continue;
			if(vis[wx][wy])continue;
			vis[wx][wy]=true;
			if(ma[wx][wy]>0)
			{
                dis[x][ma[wx][wy]]=dep;
                dis[ma[wx][wy]][x]=dep;
			}
			else
			{
				q.push(make_pair(wx,wy));
				pd.push(dep+1);
			}
		}
	}
}
bool check()
{
	ll ret=0,ccnt=0;
	tot=0;
	for(int i=1;i<cnt;i++)
	{
		for(int j=i+1;j<=cnt;j++)
		{
			hr[++tot].x=bin[i];
			hr[tot].y=bin[j];
			hr[tot].w=dis[bin[i]][bin[j]];
		}
	}
	for(int i=1;i<=cnt;i++)fa[bin[i]]=bin[i];
	sort(hr+1,hr+tot+1,cmp);
	for(int i=1;i<=tot;i++)
	{
		ll nx=hr[i].x;
		ll ny=hr[i].y;
		ll fx=get(nx);
		ll fy=get(ny);
		if(fx==fy)continue;
		ccnt++;
		fa[fy]=fx;
		ret+=hr[i].w;
		if(ccnt==cnt-1)break;
	}
	return ret<=p;
}
void work()
{
	ll x,y,z;
	cin>>n>>m>>sx>>sy>>tx>>ty>>p>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>x>>y>>z;
		a[x][y]=z;
		ma[x][y]=i;
		ppx[i].x=x,ppx[i].y=y,ppx[i].w=z;
	}
	ppx[q+1].x=sx,ppx[q+1].y=sy,ppx[q+1].w=0;
	ma[sx][sy]=q+1;
	ppx[q+2].x=tx,ppx[q+2].y=ty,ppx[q+2].w=0;
	ma[tx][ty]=q+2;
	for(int i=1;i<=q+2;i++)
	{
		for(int j=1;j<=q+2;j++)
		{
			dis[i][j]=1e18;
		}
	}
	for(int i=1;i<=q+2;i++)bfs(i);
	for(int i=0;i<=(1<<(q))-1;i++)
	{
		cnt=2;bin[1]=q+1,bin[2]=q+2;summ=0;
		for(int j=1;j<=q;j++)
		{
			if((1<<(j-1))&i)
			{
				bin[++cnt]=j;
				summ+=ppx[j].w;
			}
		}
		if(summ<=ans)continue;
		if(check())ans=summ;
	}
	if(ans>=0)cout<<ans<<endl;
	else cout<<"hungry"<<endl;
}
int main()
{
	freopen("red.in","r",stdin);
	freopen("red.out","w",stdout);
	cin>>T;
	while(T--)
	{
        clear();
		work();
	}
	return 0;
}