总览
目前 \(90\) 分，容易做到 \(91\) 但是目前没必要。
基本要求：\(0\le n\le10000\)，\(0\le m\le20000\)，\(0\le w\le20000\)。无重边，可以有自环。
\(10\) 个测试点的任务和更多限制：
- test 1：邻接矩阵。\(k=0\)，\(n\le500\)。
- test 2：单源最短路。\(k=10\)。
- test 3：全源最短路（似乎有锅）。\(k=11\)，\(n\le100\)。
- test 4：单源次短路。\(k=12\)。
- test 5：强连通分量。\(k=20\)。
- test 6：集合划分哈希。\(k=21\)，\(n\le10\)
- test 7：集合划分单调性哈希。\(k=22\)，\(n\le20\)。
- test 8：二分图最大匹配。\(k=30\)，\(n\le100\)。
- test 9：二分图最大匹配，某种实现的匈牙利算法构造。\(k=31\)，\(n\le20\)。
- test 10：SPFA 过程中的队列。\(k=13\)，\(n\le500\)，\(m\le3000\)。
要对这些东西反推。\(p\) 在大多数测试点表示边的数目，test 1,5,10 除外：test 1 中总有 \(p=0\)，test 5 中 \(p=\text{强连通分量数目}\)，test 10 中 \(p=\text{队列长度}\)。
test 1
显然。
int main()
{
freopen("nm1.in","r",stdin);
freopen("nm1.out","w",stdout);
uint n,k,p;scanf("%u%u%u",&n,&k,&p);
std::vector<std::pair<uint,uint> >V;
for(uint i=0;i<n;i++)
for(uint j=0,o;j<n;j++)
{
scanf("%u",&o);
if(o)V.push_back({i,j});
}
printf("%u %u %u\n",n,(uint)V.size(),k);
for(auto s:V)
printf("%u %u 0\n",s.first+1,s.second+1);
return 0;
}
test 2
随便构造一颗最短路树，再加上若干无用边即可。
uint Dist[20005],P[20005];
int main()
{
freopen("nm2.in","r",stdin);
freopen("nm2.out","w",stdout);
uint n,k,p;scanf("%u%u%u",&n,&k,&p);
for(uint i=0;i<n;i++)scanf("%u",Dist+i),P[i]=i;
std::sort(P,P+n,[&](uint i,uint j){return Dist[i]<Dist[j];});
printf("%u %u %u\n",n,p,k);
for(uint i=1;i<n;i++)
printf("%u %u %u\n",P[i-1]+1,P[i]+1,Dist[P[i]]-Dist[P[i-1]]);
p-=n-1;
for(uint i=1;i<n;i++)for(uint j=0;p&&j<i;j++)
printf("%u %u 20000\n",P[i]+1,P[j]+1),p--;
return 0;
}
test 3
把所有不能松弛的边找出来即可。
注意这样恰好 \(398\) 条边，比较一下会发现少两个特殊的自环，补上即可。
uint Dist[405][405];
bol B[405][405];
int main()
{
freopen("nm3.in","r",stdin);
freopen("nm3.out","w",stdout);
uint n,k,p;scanf("%u%u%u",&n,&k,&p);
printf("%u %u %u\n",n,p,k);
for(uint i=0;i<n;i++)for(uint j=0;j<n;j++)scanf("%u",Dist[i]+j);
for(uint i=0;i<n;i++)for(uint j=0;j<n;j++)if(Dist[i][j])
{
B[i][j]=true;
for(uint k=0;k<n;k++)if(i!=k&&j!=k&&Dist[i][k]+Dist[k][j]==Dist[i][j])
{
B[i][j]=false;break;
}
if(B[i][j])
printf("%u %u %u\n",i+1,j+1,Dist[i][j]);
}
return 0;
}
test 4
观察一下最小最大元素，把多数点加个自环搞成 \(\text{最短路}=\text{次短路}\)，剩下的点嗯搞即可。
uint Dist2[10005],Dist[10005];
uint P[10005];
int main()
{
freopen("nm4.in","r",stdin);
freopen("nm4.out","w",stdout);
uint n,k,p;scanf("%u%u%u",&n,&k,&p);
for(uint i=0;i<n;i++)scanf("%u",Dist2+i),P[i]=i;
// fprintf(stderr,"%u %u\n",
// *std::min_element(Dist2,Dist2+n),*std::max_element(Dist2,Dist2+n));
std::sort(P+1,P+n,[&](uint a,uint b){return Dist2[a]<Dist2[b];});
printf("%u %u %u\n",n,p,k);
for(uint i=1;i<n;i++)
Dist[P[i]]=std::min(Dist2[P[i]],Dist[P[i-1]]+20000),
printf("%u %u %u\n",P[i-1]+1,P[i]+1,Dist[P[i]]-Dist[P[i-1]]),p--;
for(uint i=1;i<n;i++)
printf("%u %u %u\n",i+1,i+1,Dist2[i]-Dist[i]),p--;
for(uint i=1;i<n;i++)if(Dist2[0]-Dist[i]<=20000)
{
printf("%u 1 %u\n",i+1,Dist2[0]-Dist[i]);
break;
}
printf("%u 1 20000\n",P[n-1]);
return 0;
}
test 5
显然。
uint P[10005];
int main()
{
freopen("nm5.in","r",stdin);
freopen("nm5.out","w",stdout);
uint n,k,p;scanf("%u%u%u",&n,&k,&p);
for(uint i=0;i<n;i++)scanf("%u",P+i),P[i]--;
printf("%u %u %u\n",n,(n-p)*2,k);
for(uint i=0;i<n;i++)if(i!=P[i])
printf("%u %u 0\n",P[i]+1,i+1),
printf("%u %u 0\n",i+1,P[i]+1);
return 0;
}
test 6
注意到点数边数均为 \(8\)，直接对拍搞出所有集合划分即可。
FILE*fin,*fout;
uint P[15],n,p;
std::vector<std::vector<uint> >V;
voi dfs(uint p)
{
if(p==n)
{
V.push_back(std::vector<uint>(P,P+n));
return;
}
for(uint&e=P[p]=0;e<=p;e++)if(P[e]==e)
dfs(p+1);
}
int main()
{
fin=fopen("nm6.in","r");
uint k;fscanf(fin,"%u%u%u",&n,&k,&p);
fclose(fin);
dfs(0);
uint j=0;
while(j<V.size())
{
fout=fopen("nm6.out","w");
fprintf(fout,"%u %u %u\n",n,p,k);
std::vector<uint>T[15];
for(uint i=0;i<n;i++)
T[V[j][i]].push_back(i);
uint p0=p;
for(uint i=0;i<n;i++)if(T[i].size()>1)
{
for(uint j=1;j<T[i].size();j++)
fprintf(fout,"%u %u 0\n",T[i][j-1]+1,T[i][j]+1),p0--;
fprintf(fout,"%u %u 0\n",T[i].back()+1,i+1),p0--;
}
for(uint i=0;i<p0;i++)
fprintf(fout,"%u %u 0\n",i+1,i+1);
fclose(fout);
system("./code nm6.out > QAQ.err");
if(!system("diff QAQ.err nm6.in"))
break;
j++;
}
return 0;
}
test 7
注意到这个哈希函数有单调性，对拍一下，对前缀依次确定即可。
FILE*fin,*fout;
uint P[25];
int main()
{
fin=fopen("nm7.in","r");
uint n,k,p;ullt h;fscanf(fin,"%u%u%u%llu",&n,&k,&p,&h);
fclose(fin);
for(uint i=0;i<n;i++)P[i]=i;
for(uint u=0;u<n;u++)for(uint&v=P[u]=0;v<=u;v++)if(P[v]==v)
{
fout=fopen("nm7.out","w");
fprintf(fout,"%u %u %u\n",n,p,k);
std::vector<uint>T[25];
for(uint i=0;i<n;i++)T[P[i]].push_back(i);
uint p0=p;
for(uint i=0;i<n;i++)if(T[i].size()>1)
{
for(uint j=1;j<T[i].size();j++)
fprintf(fout,"%u %u 0\n",T[i][j-1]+1,T[i][j]+1),p0--;
fprintf(fout,"%u %u 0\n",T[i].back()+1,i+1),p0--;
}
for(uint i=0;i<p0;i++)
fprintf(fout,"%u %u 0\n",i+1,i+1);
fclose(fout);
system("./code nm7.out > QAQ.err");
ullt g;
fin=fopen("QAQ.err","r");
fscanf(fin,"%*u%*u%*u%llu",&g);
fclose(fin);
if(g>=h)break;
}
return 0;
}
test 8
显然。
int main()
{
freopen("nm8.in","r",stdin);
freopen("nm8.out","w",stdout);
uint n,k,p,w;scanf("%u%u%u%u",&n,&k,&p,&w);
printf("%u %u %u\n",n,p,k);
for(uint i=1;i<=n;i++)
for(uint j=1;j<=w;j++)
printf("%u %u 0\n",i,j);
return 0;
}
test 9
测试一下容易发现这个匈牙利是依次选还没匹配的，再往前增广。
那选当前对应的，连前面对应的，连更大还没连过的即可。
测了一下刚刚好。
uint P[105];
int main()
{
freopen("nm9.in","r",stdin);
freopen("nm9.out","w",stdout);
uint n,k,p;scanf("%u%u%u",&n,&k,&p);
for(uint i=0;i<n;i++)scanf("%u",P+i),P[i]--;
std::vector<std::pair<uint,uint> >V;
for(uint i=0;i<n;i++)V.push_back({i,P[i]}),p--;
for(uint i=0;i<n;i++)
{
static bol B[105];
for(uint j=0;j<n;j++)B[j]=true;
for(uint j=0;p&&j<i;j++)
V.push_back({i,P[j]}),p--,B[P[j]]=false;
for(uint j=P[i]+1;p&&j<n;j++)if(B[j])
V.push_back({i,j}),p--;
}
printf("%u %u %u\n",n,(uint)V.size(),k);
for(auto s:V)
printf("%u %u 0\n",s.first+1,s.second+1);
return 0;
}
test 10
Warning：默认按编号从小到大更新。
还不会。网上也没找到题解。
有没有会的大爷可以教教啊？
