自动搬运

查看原文

来自洛谷，原作者为

	donghanwen1225 一只啥都不会的蒟蒻

搬运于2025-08-24 23:00:57，当前版本为作者最后更新于2024-07-23 00:14:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先感谢 @隔壁泞2的如心 神仙教会我网格图最小割转对偶图最短路的技巧，拜谢。

---

作为一道提交答案题，虽然题面本身是 NPC 问题，但给出的数据却很特殊，不是 NPC 问题。

这题实际需要你对数据进行人工分析 or 大胆猜测找到性质。实在是毒瘤！！！

---

测试点 $1\sim3$

这 $3$ 个测试点的图好像非常普通，什么性质都没有。因此考虑发扬人类智慧。

对测试点 $1$，可以发现所有连到 $t$ 的边的权值之和恰为 $m_1$；

对测试点 $2$，可以发现所有连到 $t$ 的边的权值中去掉最大值后的和恰为 $m_1$；

对测试点 $3$，可以发现连到 $s$ 的边共有 $55=k+1$ 条，而其中权值最小的恰为 $m_1$；

通过人类智慧已经可以在这三个测试点中拿到 $10$ 分。当然如果你能写一个很强大的随机化来跑，甚至有可能找到比 $m_1$ 小的答案，直接拿 $12$ 分。

测试点 $4\sim10$

观察测试点 $4$，发现数据有以下特点：

1. $s$ 和 $t$ 正好是 $n$ 和 $n-1$；
2. $s$ 与从 $1$ 开始的连续的一些点相连、$t$ 与到 $n-2$ 结束的连续的一些点相连，且连点的个数相同；
3. $i$ 和 $i+1$ 相连，但同时有一些并未相连，而且这些未与 $i+1$ 相连的 $i$ 都是上面的连点个数的倍数；
4. $i$ 和 $i+t$ 相连，并且这个 $t$ 恰好是上述的连点数。

实际上，测试点 $5\sim 10$ 虽然不严格满足以上性质，但整体上也基本满足。

根据以上观察，可以推断：这些图从整体上看都是网格图，而且 $s$ 和 $t$ 类似于源点和汇点。虽然靠后的几个测试点中，网格图中有一部分边甚至是点没有给出，但同样是以网格图为基础的。

于是我们可以把问题转化为网络流模型：给定源点 $s$ 和汇点 $t$，$s$ 与网格图最左边一列的点相连、网格图最右边一列与 $t$ 相连。每条边有边权，可以选择 $k$ 条边使它们的边权变为 $0$。在以上条件下，求这张图的最小割。

不考虑可以将 $k$ 个边权置为 $0$，这个问题是经典的：网格图满足平面图的性质，可以把网格图的最小割转化为对偶图的最短路。由于这是一个经典问题，这里不再赘述，可以参考例题 BZOJ 1001 狼抓兔子。

而有 $k$ 次机会将边权置为 $0$ 在最短路问题中也是经典的：使用分层图，将图分为 $k+1$ 层，层之间的连边权值为 $0$，层内正常连边。同样这里也不再赘述，可以参考例题 P6190（NOI Online 2020 普及组 T3）的 $90$ 分部分分做法。

这样就已经基本解决了这 $7$ 个测试点，但还有一个重要的细节问题：如果某条边没有给出，该如何处理？很明显，把不存在的边当成这条边权值为 $0$ 是不影响答案的，因为最短路里选择这条边对答案没有贡献。

到这里你可能很高兴，似乎只要实现这个算法就已经可以通过此题了！但别急，有些测试点是有其特殊之处的，我们还要单独讨论。

$(1)$ 测试点 $4,5,7$：没啥特殊的，看准行数和列数就行了。

$(2)$ 测试点 $6$：发现 $s$ 连接的点是 $1,16,31,\cdots$，是以 $15$ 为公差的等差数列。发现 $15$ 也是行数，因此该测试点的网格图实际上要旋转 $90\degree$ 才与正常的情况一致。

$(3)$ 测试点 $8,9,10$：发现 $n-2$ 并不是行数的倍数，而且取模后的结果依次为 $-1,-2,-2$。这提示我们网格图中的某些点被删去了。

事实上，如果想写代码来找到被删的点是有些麻烦的。不妨发扬人类智慧，肉眼观察数据：多数地方 $i$ 与 $i+t$ 相连，但少数地方 $i$ 和 $i+t-1$ 相连，这就说明附近有点被删去了。具体来说，被删的点附近会变成如下情况：

$$\begin{matrix}i-t&i&i+t-1\\i-t+1&\text{deleted}&i+t\\i-t+2&i+1&i+t+1\end{matrix} $$

寻找 $i\to i+t-1$ 和 $i+1\to i+t+1$ 的分界点，即可找到这个被删去的数。为了保持网格图的优秀性质，可以将所有 $\geq i+1$ 的点的编号都 $+1$；同时出题人较为良心，没有 $i-t+1\to i+t$ 或 $i\to i+1$ 这样的边，所以可以把删去的点补回来，并和相邻四个点均连上权值为 $0$ 的边。

想清楚了删点的机制，人工找到被删的点不需要费太多时间。三个测试点加起来也就用 $15$ 分钟。

综合以上所有情况，这道题终于被彻底解决了。

附测试点 $4\sim 10$ 的代码（包含了所有特殊情况的处理）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,k,s,t,x,y,z;int r,c,al,ns,nt,sz;int cnt,ans[10005];
int tot,fir[100005],nxt[500005],to[500005],val[500005];
int rtot,rf[100005],rn[500005],rt[500005],rv[500005];
int fr[105],en[105],h[105][105],w[105][105];int vis[100005],dis[100005];
int i1[105],i2[105],ih[105][105],iw[105][105],nv[100005];int v[10005];
int nid[10005];/*for case 6*/
struct pt{int id,v;};
bool operator <(const pt &x,const pt &y){return x.v>y.v;}
priority_queue<pt> q;
void ins(int x,int y,int z)
{
	nxt[++tot]=fir[x];fir[x]=tot;to[tot]=y;val[tot]=z;
	rn[++rtot]=rf[y];rf[y]=rtot;rt[rtot]=x;rv[rtot]=z;
}
void dc(int id,int &cc,int &x,int &y)
{
	if(id==ns||id==nt){cc=x=y=0;return;}
	cc=(id-1)/sz+1;id-=(cc-1)*sz;
	x=(id-1)/(c+1)+1;y=(id-1)%(c+1)+1;
}
int dfs(int now)
{
	if(now==ns) return 1;nv[now]=1;
	for(int i=rf[now];i;i=rn[i])
		if(dis[rt[i]]+rv[i]==dis[now])
		{
			if(nv[rt[i]]) continue;
			int c1,x1,y1,c2,x2,y2;
			dc(now,c1,x1,y1);dc(rt[i],c2,x2,y2);
			if(now==nt)
			{
				if(c2==k+1)
				{
					if(y2==1){if(i1[1]) ans[++cnt]=i1[1];}
					else if(y2==c+1){if(i2[1]) ans[++cnt]=i2[1];}
					else{if(ih[1][y2-1]) ans[++cnt]=ih[1][y2-1];}
				}
			}
			else if(rt[i]==ns)
			{
				if(c1==1)
				{
					if(y1==1){if(i1[r]) ans[++cnt]=i1[r];}
					else if(y1==c+1){if(i2[r]) ans[++cnt]=i2[r];}
					else{if(ih[r][y1-1]) ans[cnt]=ih[r][y1-1];}
				}
			}
			else if(c1==c2)
			{
				int my=min(y1,y2),mx=min(x1,x2);
				if(x1==x2){if(iw[x1][my]) ans[++cnt]=iw[x1][my];}
				if(y1==y2)
				{
					if(y1==1){if(i1[mx+1]) ans[++cnt]=i1[mx+1];}
					else if(y1==c+1){if(i2[mx+1]) ans[++cnt]=i2[mx+1];}
					else{if(ih[mx+1][my-1]) ans[++cnt]=ih[mx+1][my-1];}
				}
			}
			if(dfs(rt[i])) return 1;
		}
	return 0;
}
int main()
{
//	freopen("road9.in","r",stdin);
//	freopen("road9.out","w",stdout);
	cin>>n>>m>>k;cin>>s>>t;
//	r=100;c=10;/*case 4*/
//	r=30;c=40;swap(s,t);/*case 5*/
//	r=37;c=41;swap(s,t);/*case 7*/
//	r=75;c=15;/*case 6*/
//	r=43;c=19;s++;t++;/*case 8*/
//	r=53;c=31;s+=2;t+=2;swap(s,t);/*case 9*/
//	r=50;c=50;s+=2;t+=2;/*case 10*/
	al=(k+1)*(r-1)*(c+1);ns=al+1;nt=al+2;sz=(r-1)*(c+1);
//	for(int i=1;i<=c;i++) for(int j=1;j<=r;j++) nid[(j-1)*c+i]=(i-1)*r+j;
//	nid[s]=s;nid[t]=t;/*for case 6*/
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;v[i]=z;
//		x=nid[x];y=nid[y];/*for case 6*/
//		if(x>=149) x++;if(y>=149) y++;/*for case 8*/
//		if(x>=1038) x++;if(x>=810) x++;if(y>=1038) y++;if(y>=810) y++;/*for case 9*/
//		if(x>=2448) x++;if(x>=52) x++;if(y>=2448) y++;if(y>=52) y++;/*for case 10*/
		if(x==s)
		{
			fr[y]=z;i1[y]=i;
		}
		else if(y==t)
		{
			en[x-r*(c-1)]=z;i2[x-r*(c-1)]=i;
		}
		else if(y-x==r)
		{
			int ci=(x-1)%r+1,cj=(x-1)/r+1;
			if(cj==c){cout<<"spe edges!!!\n";return 0;}
			h[ci][cj]=z;ih[ci][cj]=i;
		}
		else if(y-x==1)
		{
			int ci=(x-1)%r+1,cj=(x-1)/r+1;
			if(ci==r){cout<<"spe edges!!!\n";return 0;}
			w[ci][cj]=z;iw[ci][cj]=i;
		}
		else{cout<<"spe edges!!!\n";return 0;}
	}
	for(int i=1;i<=k+1;i++)
	{
		int bf=(i-1)*(r-1)*(c+1);
		for(int j=1;j<r;j++)
			for(int l=1;l<=c;l++)
			{
				ins(bf+(j-1)*(c+1)+l,bf+(j-1)*(c+1)+l+1,w[j][l]);
				ins(bf+(j-1)*(c+1)+l+1,bf+(j-1)*(c+1)+l,w[j][l]);
			}
		for(int j=2;j<r;j++)
		{
			ins(bf+(j-2)*(c+1)+1,bf+(j-1)*(c+1)+1,fr[j]);
			ins(bf+(j-1)*(c+1)+1,bf+(j-2)*(c+1)+1,fr[j]);
			ins(bf+(j-1)*(c+1),bf+j*(c+1),en[j]);
			ins(bf+j*(c+1),bf+(j-1)*(c+1),en[j]);
			for(int l=1;l<c;l++)
			{
				ins(bf+(j-2)*(c+1)+l+1,bf+(j-1)*(c+1)+l+1,h[j][l]);
				ins(bf+(j-1)*(c+1)+l+1,bf+(j-2)*(c+1)+l+1,h[j][l]);
			}
		}
		if(i==k+1) break;
		int af=i*(r-1)*(c+1);
		for(int j=1;j<r;j++)
			for(int l=1;l<=c;l++)
			{
				ins(bf+(j-1)*(c+1)+l,af+(j-1)*(c+1)+l+1,0);
				ins(bf+(j-1)*(c+1)+l+1,af+(j-1)*(c+1)+l,0);
			}
		for(int j=2;j<r;j++)
		{
			ins(bf+(j-2)*(c+1)+1,af+(j-1)*(c+1)+1,0);
			ins(bf+(j-1)*(c+1)+1,af+(j-2)*(c+1)+1,0);
			ins(bf+(j-1)*(c+1),af+j*(c+1),0);
			ins(bf+j*(c+1),af+(j-1)*(c+1),0);
			for(int l=1;l<c;l++)
			{
				ins(bf+(j-2)*(c+1)+l+1,af+(j-1)*(c+1)+l+1,0);
				ins(bf+(j-1)*(c+1)+l+1,af+(j-2)*(c+1)+l+1,0);
			}
		}
	}
	ins(ns,(r-2)*(c+1)+1,fr[r]);ins(ns,sz+(r-2)*(c+1)+1,0);
	ins(ns,(r-1)*(c+1),en[r]);ins(ns,sz+(r-1)*(c+1),0);
	for(int j=1;j<c;j++)
	{
		ins(ns,(r-2)*(c+1)+j+1,h[r][j]);ins(ns,sz+(r-2)*(c+1)+j+1,0);
	}
	ins(k*sz+1,nt,fr[1]);ins((k-1)*sz+1,nt,0);
	ins(k*sz+c+1,nt,en[1]);ins((k-1)*sz+c+1,nt,0);
	for(int j=1;j<c;j++)
	{
		ins(k*sz+j+1,nt,h[1][j]);ins((k-1)*sz+j+1,nt,0);
	}
	for(int i=1;i<=nt;i++) dis[i]=1<<30;
	dis[ns]=0;q.push({ns,0});
	while(!q.empty())
	{
		pt now=q.top();q.pop();
		if(vis[now.id]) continue;vis[now.id]=1;
		for(int i=fir[now.id];i;i=nxt[i])
			if(dis[to[i]]>dis[now.id]+val[i])
			{
				dis[to[i]]=dis[now.id]+val[i];
				q.push({to[i],dis[to[i]]});
			}
	}
//	cout<<dis[nt]<<"\n";
	dfs(nt);
	cout<<cnt<<"\n";
	for(int i=1;i<=cnt;i++) cout<<ans[i]<<"\n";
//	int ch=0;for(int i=1;i<=cnt;i++) ch+=v[ans[i]];cout<<ch<<"\n";
	return 0;
}