题解 CF350E 【Wrong Floyd】

# 前言： #### 趁着还没有题解，赶紧水一波$qwq$ #### 这题其实真的不难 ------------ # 回归正题: 我们首先要明白$floyd$的思想，相信你都来做这道~~水~~题了，肯定不陌生，简单的手玩后，我们可以发现： 只要有任意一个点只跟非标记点相连的话，是更新不出它到另外的标记点的距离的，并且题目中$k>=2$是很关键的，光说不清楚，举个例子： $n=5,m=4,k=2$，标记点为$1,5$时： 只需要如下连： $1-2,1-3,1-4,4-5$，就能够$hack$，为什么呢，我们看到题目中是以标记点为中间点来更新最短距离 那么以$1$为标记点时，能更新出：$2-3,2-4,3-4$的最短距离，而以$5$为标记点时,什么都不能更新出，所以$1-5$的最短距离就不能算出来 那么总结一下连边的规律： $1$、随便选一个点（下面代码选的是随机的标记点），只跟非标记点相连 $2$、把所有未加入图中的点加入，向除了上面选的点的点连边 $3$、如果边数不满$m$的话，想怎么连就怎么连$qwq$，前提还是不和上面的点相连 那么输出$-1$的情况呢？？ $1$、当所有点都是标记点的时候，其实就是一个完整的$floyd$，难道你能$hack$吗，~~（逃）~~ $2$、当$m$很大，让你不能够腾出一个点只跟非标记点相连的时候，输出$-1$，具体的话是$(n-1)*(n-2)/2+n-k$，为什么呢？其实是我们要保证一个点只跟非标记点连边，那么连的边数就是$n-k$，那么其他的点随便怎么连，但是最多就是个完全图，也就是$(n-1)*(n-2)/2$了，相加即可 接下来是美滋滋的代码时间~~~ ~~~cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define N 307 using namespace std; int n,m,k,it,it1,line; bool g[N][N],mark[N],vis[N]; int main() { scanf("%d%d%d",&n,&m,&k); if((k==n)||(m>(n-1)*(n-2)/2+n-k)) { printf("-1"); return 0; } for(int i=1;i<=k;++i) { int in; scanf("%d",&in); mark[in]=1; it=in; } vis[it]=1; for(int i=1;i<=n;++i) g[i][i]=1; for(int i=1;i<=n;++i) { if(i==it||mark[i]) continue; printf("%d %d\n",i,it); ++line; vis[i]=1; g[i][it]=g[it][i]=1; it1=i; if(line==m) return 0; } for(int i=1;i<=n;++i) { if(line==m) return 0; if(vis[i]) continue; printf("%d %d\n",i,it1); ++line; g[i][it1]=g[it1][i]=1; vis[i]=1; } for(int i=1;i<=n;++i) { if(line==m) return 0; if(i==it) continue; for(int j=1;j<=n;++j) { if(j==it||g[i][j]) continue; if(line==m) return 0; printf("%d %d\n",i,j); g[i][j]=g[j][i]=1; ++line; } } return 0; } ~~~