题意：给定一个数s,构造一个无向图，使得任意两点的最短路径和为s。
思路：二分找到n，满足n×(n-1)/2<=s，且n尽可能大。这样的图，相当于n个点每两个点都连一条边。窝们考虑这样一种构造方法，
假设现在有n个点，我们按照逆时针方向(顺时针也行)排序编号,那么我们间隔删去不相邻点的的边，比如5个点，我们删去
1–3,1–4,…,1–n-2,1—n-1,保留2，删3–5,3–6,…3–n-2,3—-n-1,保留4，删5–7,5–8,…,5–n-1。这样可以保证每删一条边最短路径和+1。
那么n个点最多可删去(n-3)+(n-2)+…+1=(n-3)×(n-2)/2。我们发现(n+1)×n/2-n×(n-1)/2=n，(n-3)×(n-2)/2>=n —>n>=6，即15以上的值均
可按照这种方法构造。s<15的，除了2和5无法构造，，都可以在上述的图基础上再删去边构成即可。详见代码：
/********************************************************* file name: C.cpp author : kereo create time: 2015年02月02日 星期一 18时45分37秒*********************************************************/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<set>#include<map>#include<vector>#include<stack>#include<cmath>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int sigma_size=26;const int N=1000+50;const int MAXN=100000+50;const int inf=0x3fffffff;const double eps=1e-8;const int mod=100000000+7;#define L(x) (x<<1)#define R(x) (x<<1|1)#define PII pair<int, int>#define mk(x,y) make_pair((x),(y))int n,m;int dp[N][N];int binary(int x){int l=1,r=N,ans=0;while(l<=r){int mid=(l+r)>>1;if(mid*(mid-1)/2<=x)ans=mid,l=mid+1;elser=mid-1;}return ans;}int main(){while(~scanf("%d",&m)){if(m == 1){printf("2 1\n");printf("1 2\n");continue;}if(m == 2 || m == 5){printf("Impossible\n");continue;}if(m == 4){printf("3 2\n");printf("1 2\n");printf("1 3\n");continue;}memset(dp,-1,sizeof(dp));n=binary(m);m-=n*(n-1)/2;int cnt=(n+1)/2; cnt=(cnt+1)/2;//int num=0;for(int i=1;i<=cnt*2-1;i+=2){for(int j=1;j<=n-3-num && m;j++){dp[i][i+j+1]=0; dp[i+j+1][i]=0;m–;}if(m == 0)break;num++;}if(m){dp[1][n]=dp[n][1]=0;m–;}if(m){int k=(n+1)/2+1;dp[k][k+1]=dp[k+1][k]=0;}int ans=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(dp[i][j] == -1)ans++;printf("%d %d\n",n,ans);for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(dp[i][j] == -1)printf("%d %d\n",i,j);}return 0;}
未经一番寒彻骨，焉得梅花扑鼻香
