题解：P10758 [CTSC2011] 道路监控
donghanwen1225
·
·
题解
首先感谢 @隔壁泞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，发现数据有以下特点：
-
-
-
-
实际上，测试点 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 是不影响答案的，因为最短路里选择这条边对答案没有贡献。
到这里你可能很高兴，似乎只要实现这个算法就已经可以通过此题了！但别急，有些测试点是有其特殊之处的，我们还要单独讨论。
$(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$ 的代码（包含了所有特殊情况的处理）：
```cpp
#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;
}
```