#include?
#include?
#include?
#include?
#include?
#include?
#include?

#define?mvn?1026
#define?Infinte?9999
#define?TRUE?1
#define?FALSE?0

typedef?struct?ArcNode{
	int?adjvex;
	struct?ArcNode?*nextarc;
	int?w;
}ArcNode;

typedef?struct?VNode{
	int?data;
	int?d;
	VNode?*parent;
	ArcNode?*firstarc;
}VNodeAdjList[mvn];

typedef?struct?{
	AdjList?vex;
	int?vexnumarcnum;
}ALGraph;

void?CreatG（ALGraph?&G）{
	int?ijk;
	int?v1v2v3;
	struct?ArcNode?*p;
	printf（“Please?input?the?number?of?Vertexes.\n“）;
	scanf（“%d“&G.vexnum）;
	printf（“Please?input?the?number?of?Arcs.\n“）;
	scanf（“%d“&G.arcnum）;
	for（i=1;i<=G.vexnum;++i）{?
		G.vex[i].data=i;
		G.vex[i].firstarc=NULL;
		G.vex[i].parent=NULL;
	}
	for（k=1;k<=G.arcnum;k++）{
		printf（“Please?input?Arc?No.%d?Sample:?12?\n“k）;
		scanf（“%d%d“&v1&v2）;
		printf（“Please?input?its?w\n“）;
		scanf（“%d“&v3）;
		i=v1;
		j=v2;
		p=（ArcNode?*）?malloc?（sizeof?（ArcNode））;
		p->adjvex=j;
		p->nextarc=G.vex[i].firstarc;
		p->w=v3;
		G.vex[i].firstarc=p;?
	}
}

int?check（ALGraph?&Gint?iint?j）{
	if（i==j）?return?FALSE;
	ArcNode?*p;
	p=G.vex[i].firstarc;
	while（p!=NULL）{
		if（p->adjvex==j）?return?FALSE;
		p=p->nextarc;
	}
	return?TRUE;
}

void?CreatG2（ALGraph?&Gint?nint?runtype）{
	int?ijkw;
	struct?ArcNode?*p;
	G.vexnum=n;
	G.arcnum=（int）n*（log（n）/log（2））;
	for（i=1;i<=G.vexnum;i++）{?
		G.vex[i].data=i;
		G.vex[i].firstarc=NULL;
		G.vex[i].parent=NULL;
	}
	for（k=2;k<=G.vexnum;k++）{
		i=rand（）%（k-1）+1;
		w=rand（）%100;
		j=k;
		p=（ArcNode?*）?malloc?（sizeof?（ArcNode））;
		p->adjvex=j;
		p->nextarc=G.vex[i].firstarc;
		p->w=w;
		G.vex[i].firstarc=p;
		p=（ArcNode?*）?malloc?（sizeof?（ArcNode））;
		p->adjvex=i;
		p->nextarc=G.vex[j].firstarc;
		p->w=w;
		G.vex[j].firstarc=p;
		if（runtype==1）{
			printf（“Arc?No.%d:?%d%d\n“（k-1）ij）;
			printf（“Its?w:?%d\n“w）;
			printf（“\n“）;
		}
	}
	for（;k<=（G.arcnum+1）;k++）{
		do{
			i=rand（）%（G.vexnum）+1;
			j=rand（）%（G.vexnum）+1;
		}while（check（Gij）==FALSE）;
//		printf（“OK\n“）;
		w=rand（）%100;		
		p=（ArcNode?*）?malloc?（sizeof?（ArcNode））;
		p->adjvex=j;
		p->nextarc=G.vex[i].firstarc;
		p->w=w;
		G.vex[i].firstarc=p;
		p=（ArcNode?*）?malloc?（sizeof?（ArcNode））;
		p->adjvex=i;
		p->nextarc=G.vex[j].firstarc;
		p->w=w;
		G.vex[j].firstarc=p;
		if（runtype==1）{
			printf（“Arc?No.%d:?%d%d\n“（k-1）ij）;
			printf（“Its?w:?%d\n“w）;
			printf（“\n“）;
		}
	}
}

void?Compute（ALGraph?&GALGraph?&G2）{
	int?ij;
	ArcNode?*p;
	for（i=1;i<=G.vexnum;i++）
		G2.vex[i]=G.vex[i];
	G2.vex[i].firstarc=NULL;
	p=（ArcNode?*）?malloc?（sizeof?（ArcNode））;
	for（j=1;j<=G.vexnum;j++）{
		p=（ArcNode?*）?malloc?（sizeof?（ArcNode））;
		p->adjvex=j;
		p->nextarc=G2.vex[i].firstarc;
		p->w=0;
		G2.vex[i].firstarc=p;
	}
	G2.vex[i].data=i;
	G2.vexnum=G.vexnum+1;
	G2.arcnum=G.arcnum+G.vexnum;

}


void?IntializeSingleS