题目中只选取k个点更新,因此只要保证有一个点只连到非k点即可
注意:题目要求连通图!!比赛的时候没看到,WA了,只要改下输出顺序即可保证联通。
/* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; int vis[305]; int main() { int n,k,m; while(~scanf("%d%d%d",&n,&m,&k)) { int i,t,j; memset(vis,0,sizeof(vis)); for(i=0;i<k;i++) { scanf("%d",&t); vis[t]=1; } int Max=n-k+(n-1)*(n-2)/2; if(k==n||m>Max)puts("-1"); else { int f=1,last; while(!vis[f])f++; for(i=1;i<=n&&m;i++) { if(vis[i])continue; printf("%d %d\n",f,i); //先输出一组保证错误 last=i; m--; break; } for(i=1;i<=n&&m;i++) { if(i==f)continue; for(j=i+1;j<=n&&m;j++) { if(j==f)continue; printf("%d %d\n",i,j); //保证联通 m--; } } for(i=last+1;i<=n&&m;i++) { if(vis[i])continue; printf("%d %d\n",f,i); m--; } } } }