creategraph.c

1995年ACM contest FINAL试题和源码

/*

1995-96 ACM International Collegiate Programming Contest
Southwestern European Regional Contest
ETH Zurich, Switzerland
December 9, 1995


Problem: Coloring

Idea:			Andreas Wolf, ETH Zurich
Implementation:	Manuel Bleichenbacher, Head Judge

Graph generation.

*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>


typedef enum {
	FALSE = 0,
	TRUE = 1
} bool;

#define MaxNode		101

static bool	edge[MaxNode][MaxNode];

typedef struct {
	int nNodes;
	int nEdges;
} GraphDesc;

static int nGraphs = 3;
static GraphDesc sGraph[3] =
	{ { 100, 7000 },
	  {  47,  800 },
	  {  23,   80 } };

int rand_number(int upper);
void SRand(int seed);
int Rand();


void SRand(int seed)
{
	srand(seed);
}

int Rand()
{
	return rand() & 0x7fff;
}

int rand_number(int upper)
{
	int num;
	num = (int)Rand() * upper / 32768;
	assert( num >= 0 && num < upper);
	return num;
}


int main(int argc, char* argv[])
{
	int nNodes, nEdges;
	int edgeCnt;
	int i, j;
	int from, to;
	FILE*	fout;
	
	SRand(867398);
	
	fout = fopen("coloring.in1", "w");
	assert(fout != 0);
		
	while (nGraphs > 0) {
		nGraphs--;
		
		nNodes = sGraph[nGraphs].nNodes;
		nEdges = sGraph[nGraphs].nEdges;
		
		for (i = 1; i < MaxNode; i++)
			for (j = 1; j < MaxNode; j++)
				edge[i][j] = FALSE;
		
		edgeCnt = nEdges;
		for (i = 0; i < edgeCnt; i++) {
			from = rand_number(nNodes) + 1;
			to = rand_number(nNodes) + 1;
			if ( from != to && !edge[from][to] ) {
				edge[from][to] = TRUE;
				edge[to][from] = TRUE;
				
			} else {	/* already existing edge */
				nEdges--;
			}
		}
		
		fprintf(fout, "%d %d\n", nNodes, nEdges);
		
		edgeCnt = 0;
		for (i = 1; i < MaxNode; i++)
			for (j = i; j < MaxNode; j++)
				if (edge[i][j]) {
					fprintf(fout, "%d %d\n", i, j);
					edgeCnt++;
				}
		
		assert(edgeCnt == nEdges);
	}
			
	fclose(fout);
	
	return 0;
}