这个问题出在哪啊？
这是一个无向简单图的编程，首先要感谢乌鸦大哥的帮忙，编出了程序，但是我发觉还是有点小小的问题——虽然说是编译成功了，但是，无法进行输入数据运行，问题出在在哪呢，我看不出来，所以请大家帮帮忙看看，谢谢！内容有点长，没办法，请耐心，谢谢！
原题：
Lance博士目前正在被他的资料所困扰，事情是这样的： Lance博士一直致力于无向简单图性质的研究，他把他曾经研究过的图都用图的度序列纪录下来，无向简单图上的一个顶点所连的边的个数称为该顶点的度，所有顶点的度排列在一起构成图的度序列。例如图1的度序列就可以是：（2，1，1，3，1），度序列内部是没有顺序关系的，即图1的度序列同样可以表示成（1，2，3，1，1）。然后不久前，Lance博士的助手不小心将部分其他的数字序列混入到这些度序列纪录中，Lance博士无法分辨哪些是他原来的纪录，他于是聘请你帮他编写一个程序来辨别哪些数字序列是真正的度序列，即存在符合这个度序列的无向简单图。
输入文件：
如果该数字序列不是度序列，只需在第一行输出“No！”;
如果该数字序列是一个度序列，首先在第一行输出“Yes！”；然后在接下来的若干行里输出一个符合该度序列的图所有边，每行一条边。
我们默认一个图的顶点编号为1至T，如果顶点i与j之间有一条边，我们表示为“i j”。例如图一就可以表示为：
图形：[IMG]http://sfgd.ik8.com/1.JPG.jpg[/IMG]
1 3
2 4
3 4
4 5
输入样例1：
5
3 2 1 1 1
输出样例1：
Yes!
1 3
2 4
3 4
3 5
输入样例2：
No!
说明：若连接结点之间的边可以不止一条，这样的图称为多重图。一个结点如果有指向自己的边，这条边被称为自环。无向简单图是指无自环的非多重图。
乌鸦大哥的回帖如下：
这个题目我说说自己的想法和证明,如果有错,请大家指出,
对于输入数据 (4,2,2,1,1)
该图可以这么构造:
因为第一个点的数字为4那么它肯定和后面的点中4个相连
现在从图中去掉该点和对应的边,残量图也对应一个度序列:(0,1,1,0,0)
我们可以按照这个方法对残量图进行继续重复操作,直到残量图为(0,0,0,0,0)如果能够达到这样的结果,者对应的图肯定存在否则不存在.
但是现在出现一个问题:
构造残量图的方法不是唯一的:
比如 (2,2,2,1,1)消掉第一个点后可能的残量图度序列有:
(0,1,1,1,1);(0,1,2,0,1)等等等等,这些不同的构造路径中只要有一个成功,显然结果就是Yes.
想到这里我想到了搜索,但是很显然搜索的规模很大,而且楼主没给出数据范围,我猜想数据范围是可以很大的,于是开始想其它办法.
这时候我想到了残量图的构造过程,如果剩下 (3,2,0,0)这种是肯定不行了,那么不行的原因是3和2不同,从大体上来说可以这么猜想:该图的度序列如果波动越小,那么构造成功的可能性越大.
由此猜想出一个贪心算法:
对于每个图,
消去度最大的那个点,消去的方法假设度最大的点分别与度第二大,度第三大,...度第N大的点连有边(N刚好满足把该点的度消为0),如此消去该图,一直这么操作,如果可以把所有的点的度都消为0,就YES,否则NO;
对该算法的证明:
证明的目标是:对于任意一个从大到小排列的度序列(a1,a2,a3,a4..an),现在要消去其中度最大的一个点,对于消法A:有一个对应的效法B满足,B和A中要减掉的点只有一个不同,A为x变为x-1,B为y变为y-1(x>y)
例如对于(3,2,2,1,1)消2,
A方按:(2-2,2-1,2-1,1-1,1);
B方按:(2-2,2-1,2,1-1,1-1);只有2-1,与1-1一项不同.
显然A方按的结果为(.....,x-1,y);B方按的结果为(......,x,y-1)前面为相同部分如果B方案操作后有满足条件的图G,那么因为x>y所以,x>(y-1),如此肯定G中存在一个点,它只与x对应的点相连而不与(y-1)对应的点相连,把该点与x对应的点的边去掉,再加上一条该边与(y-1)相连的边,得到的新图对应的度序列为(.....,x-1,y)!!!!!
由此可知B方案可行A方案就一定可行,即A方案比B方案更"优".将各种可能的方案列出,显然贪心方案是最"优"的，因为如果它是B方案,找不出和它对应的A方案,故贪心算法是正确的
下面是代码,算法复杂度为O(N^2),考虑空间问题我采用了两次检查(第一次检查,第二次输出)的方法,空间复杂度为O(N);如果一次检查过程并记录的话空间复杂度为O(N^2),因为根据时间复杂度,N可以高达100000,故选择前者保证足够的空间:
#include <stdio.h>
#include <string.h>
FILE *fi,*fo;
#define DMAX 1000
long data[DMAX],n,p[DMAX];
long tmp_data[DMAX],tmp_p[DMAX];
long part(long l,long r)
{/*间接对p[]:记录data的下标的数组,进行从大到小排序*/
long tmp,key=data[p[(l+r)>>1]];
while(1){
while(data[p[l]]>key)
++l;
while(data[p[r]]<key)
--r;
if(l>=r) return r;
tmp=p[l];p[l]=p[r];p[r]=tmp;
++l;--r;
}
}
void q_sort(long l,long r)
{/*快排*/
long mid;
if(l>=r) return;
mid=part(l,r);
q_sort(l,mid);
q_sort(mid+1,r);
}
void init()
{/*数据初始化 */
long i;
for(i=0;i<n;i++){
fscanf(fi,"%ld",&data[i]);p[i]=i;
}
q_sort(0,n-1);
memcpy(tmp_data,data,sizeof(data));
memcpy(tmp_p,p,sizeof(p));
}
void resort(long begin,long end)
{/*从新将新序列排序*/
long i,j,tmp;
for(i=end;i>begin;i--){
for(j=i+1;j<n&&data[p[j-1]]<data[p[j]];j++){
tmp=p[j-1];p[j-1]=p[j];p[j]=tmp;
}
}
}
int ok(unsigned char print)
{/*检查并且打印,print决定是否边检查边输出*/
long i,j,jmax;
for(i=0;i<n;i++){
jmax=i+data[p[i]];
if(jmax>=n) return 0;
for(j=i+1;j<=jmax;j++)
if(!data[p[j]]) return 0;
else {
data[p[j]]--;
if(print) fprintf(fo,"%ld %ld\n",p[i]+1,p[j]+1);
}
resort(i,jmax);
}
return 1;
}
int main(void)
{
//fi=stdin; /*选择键盘输入方式*/
fi=fopen("input.txt","r");
//fo=fopen("ouput.txt","w");/*选择文件输出方式*/
fo=stdout;
while(fscanf(fi,"%ld",&n)==1){
init();
if(ok(0)){
fprintf(fo,"Yes!\n");
memcpy(data,tmp_data,sizeof(data));
memcpy(p,tmp_p,sizeof(p));
ok(1);
}
else fprintf(fo,"No!\n");
}
getch();/*文件输出的时候这个应该去掉*/
fclose(fi);
//fclose(fo);
return 0;
}
难道这个题目没有问题吗，那为什么我在运行的时候就是不对呢
不是离散问题吧，好象