1  
   2  #include <stdio.h>
   3  #include <stdlib.h>
   4  #include <ctype.h>
   5  #include <sys/types.h>
   6  
   7  #define BUFSIZE 256
   8  
   9  typedef enum BType {
  10  	Nothing = 0,
  11  	BString,
  12  	BInt,
  13  	BList,
  14  	BDict
  15  } BType;
  16  
  17  struct Bencoding;
  18  
  19  typedef struct ListNode {
  20  	struct Bencoding *cargo;
  21  	struct ListNode *next;
  22  } ListNode;
  23  
  24  typedef struct DictNode {
  25  	char *key;
  26  	struct Bencoding *value;
  27  	struct DictNode *next;
  28  } DictNode;
  29  
  30  typedef struct Bencoding {
  31  	BType type;
  32  	union {
  33  		long long val;  // used when type == BInt
  34  		ListNode *list; // used when type == BList
  35  		char *str;      // used when type == BString
  36  		DictNode *dict;
  37  	} cargo; // data
  38  } Bencoding;
  39  
  40  Bencoding* parse_bencoding();
  41  
  42  Bencoding* new_bencoding()
  43  {
  44  	return malloc(sizeof(Bencoding));
  45  }
  46  
  47  ListNode* new_listnode()
  48  {
  49  	return malloc(sizeof(ListNode));
  50  }
  51  
  52  DictNode* new_dictnode()
  53  {
  54  	return malloc(sizeof(DictNode));
  55  }
  56  
  57  Bencoding* new_bint(int val)
  58  {
  59  	Bencoding *b = new_bencoding();
  60  	b->type = BInt;
  61  	b->cargo.val = val;
  62  	return b;
  63  }
  64  
  65  Bencoding* new_blist(ListNode *l)
  66  {
  67  	Bencoding *b = new_bencoding();
  68  	b->type = BList;
  69  	b->cargo.list = l;
  70  	return b;
  71  }
  72  
  73  Bencoding* new_bstring(char *s, int len)
  74  {
  75  	Bencoding *b = new_bencoding();
  76  	b->type = BString;
  77  	b->cargo.str = s;
  78  	return b;
  79  }
  80  
  81  Bencoding* new_bdict(DictNode *d)
  82  {
  83  	Bencoding *b = new_bencoding();
  84  	b->type = BDict;
  85  	b->cargo.dict = d;
  86  	return b;
  87  }
  88  
  89  void failed()
  90  {
  91  	printf("Parse FAILED\n");
  92  	exit(1);
  93  }
  94  
  95  char buf[BUFSIZE];
  96  int pos = 0;
  97  int buf_lim = 0;
  98  
  99  char reloadBuffer() 
 100  { 
 101  	buf_lim = fread(buf, 1, BUFSIZE, stdin);
 102  	pos = 0;
 103  }
 104  
 105  void checkBufReady()
 106  {
 107  	if (pos >= buf_lim)
 108  		reloadBuffer();
 109  }
 110  
 111  char peekChar()
 112  {
 113  	checkBufReady();
 114  	return buf[pos];
 115  }
 116  
 117  char getChar()
 118  {
 119  	checkBufReady();
 120  	return buf[pos++];
 121  }
 122  
 123  void matchChar(char c)
 124  {
 125  	if (getChar() != c)
 126  		failed();
 127  }
 128  
 129  Bencoding* parse_int() 
 130  {
 131  	matchChar('i');
 132  	long long val = 0;
 133  	while (isdigit(peekChar()))
 134  		val = val*10 + (getChar() - '0');
 135  	matchChar('e');
 136  
 137  	return new_bint(val);
 138  }
 139  
 140  Bencoding* parse_list()
 141  {
 142  	matchChar('l');
 143  	ListNode l;
 144  	ListNode *c = &l;
 145  	while (peekChar() != 'e') {
 146  		c->next = new_listnode();
 147  		c = c->next;
 148  		c->cargo = parse_bencoding();
 149  		c->next = 0;
 150  	}
 151  	matchChar('e');
 152  	return new_blist(l.next);
 153  }
 154  
 155  Bencoding* parse_string()
 156  {
 157  	int len = 0;
 158  	while (isdigit(peekChar()))
 159  		len = len*10 + (getChar() - '0');
 160  	matchChar(':');
 161  	char *s = malloc(sizeof(char)*(len+1));
 162  	int i;
 163  	for (i = 0; i < len; ++i)
 164  		s[i] = getChar();
 165  	s[len] = 0;
 166  	return new_bstring(s, len+1);
 167  }
 168  
 169  Bencoding* parse_dict()
 170  {
 171  	matchChar('d');
 172  	DictNode d;
 173  	DictNode *c = &d;
 174  	while (peekChar() != 'e') {
 175  		c->next = new_dictnode();
 176  		c = c->next;
 177  		Bencoding *s = parse_string();
 178  		c->key = s->cargo.str;
 179  		free(s);
 180  		c->value = parse_bencoding();
 181  		c->next = 0;
 182  	}
 183  	matchChar('e');
 184  	return new_bdict(d.next);
 185  }
 186  
 187  Bencoding* parse_bencoding()
 188  {
 189  	char c = peekChar();
 190  	switch (c) {
 191  		case 'd': return parse_dict();
 192  		case 'l': return parse_list();
 193  		case 'i': return parse_int();
 194  		default: return parse_string();
 195  	}
 196  }
 197  
 198  void print_indent(int indent)
 199  {
 200  	int i;
 201  	for (i = 0; i < indent; ++i)
 202  		printf("  ");
 203  }
 204  
 205  
 206  void print_bencoding(Bencoding *b, int indent)
 207  {
 208  	print_indent(indent);
 209  	switch (b->type) {
 210  		case BInt: 
 211  			printf("%lld\n", b->cargo.val);
 212  			break;
 213  		case BList:
 214  			printf("[\n");
 215  			ListNode *c = b->cargo.list;
 216  			while (c) {
 217  				print_bencoding(c->cargo, indent+1);
 218  				c = c->next;
 219  			}
 220  			print_indent(indent);
 221  			printf("]\n");
 222  			break;
 223  		case BString:
 224  			printf("%s\n", b->cargo.str);
 225  			break;
 226  		case BDict:
 227  			printf("{\n");
 228  			DictNode *d = b->cargo.dict;
 229  			while (d) {
 230  				print_indent(indent+1);
 231  				printf("%s ==>\n", d->key);
 232  				print_bencoding(d->value, indent+2);
 233  				d = d->next;
 234  			}
 235  			print_indent(indent);
 236  			printf("}\n");
 237  			break;
 238  	}
 239  }
 240  
 241  int main(int argc, char *argv[])
 242  {
 243  	Bencoding* b = parse_bencoding();
 244  
 245  	print_bencoding(b, 0);
 246  
 247  	return 0;
 248  }

   1  
   2  void dijkstra2(int s) {
   3  	int queue[GRAPHSIZE];
   4  	char inQueue[GRAPHSIZE];
   5  	int begq = 0,
   6  	    endq = 0;
   7  	int i, mini;
   8  	int visited[GRAPHSIZE];
   9  
  10  	for (i = 1; i <= n; ++i) {
  11  		d2[i] = INFINITY;
  12  		visited[i] = 0; /* the i-th element has not yet been visited */
  13  		inQueue[i] = 0;
  14  	}
  15  
  16  	d2[s] = 0;
  17  	queue[endq] = s;
  18  	endq = (endq + 1) % GRAPHSIZE;
  19  
  20  
  21  	while (begq != endq) {
  22  		mini = queue[begq];
  23  		begq = (begq + 1) % GRAPHSIZE;
  24  		inQueue[mini] = 0;
  25  
  26  		visited[mini] = 1;
  27  
  28  		for (i = 1; i <= n; ++i)
  29  			if (dist[mini][i])
  30  				if (d2[mini] + dist[mini][i] < d2[i]) { 
  31  					d2[i] = d2[mini] + dist[mini][i];
  32  					if (!inQueue[i]) {
  33  						queue[endq] = i;
  34  						endq = (endq + 1) % GRAPHSIZE;
  35  						inQueue[i] = 1;
  36  					}
  37  				}
  38  	}
  39  }

   1  
   2  #include <stdio.h>
   3  
   4  int n;
   5  float a[10][11];
   6  
   7  void forwardSubstitution() {
   8  	int i, j, k, max;
   9  	float t;
  10  	for (i = 0; i < n; ++i) {
  11  		max = i;
  12  		for (j = i + 1; j < n; ++j)
  13  			if (a[j][i] > a[max][i])
  14  				max = j;
  15  		
  16  		for (j = 0; j < n + 1; ++j) {
  17  			t = a[max][j];
  18  			a[max][j] = a[i][j];
  19  			a[i][j] = t;
  20  		}
  21  		
  22  		for (j = n; j >= i; --j)
  23  			for (k = i + 1; k < n; ++k)
  24  				a[k][j] -= a[k][i]/a[i][i] * a[i][j];
  25  
  26  /*		for (k = 0; k < n; ++k) {
  27  			for (j = 0; j < n + 1; ++j)
  28  				printf("%.2f\t", a[k][j]);
  29  			printf("\n");
  30  		}*/
  31  	}
  32  }
  33  
  34  void reverseElimination() {
  35  	int i, j;
  36  	for (i = n - 1; i >= 0; --i) {
  37  		a[i][n] = a[i][n] / a[i][i];
  38  		a[i][i] = 1;
  39  		for (j = i - 1; j >= 0; --j) {
  40  			a[j][n] -= a[j][i] * a[i][n];
  41  			a[j][i] = 0;
  42  		}
  43  	}
  44  }
  45  
  46  void gauss() {
  47  	int i, j;
  48  
  49  	forwardSubstitution();
  50  	reverseElimination();
  51  	
  52  	for (i = 0; i < n; ++i) {
  53  		for (j = 0; j < n + 1; ++j)
  54  			printf("%.2f\t", a[i][j]);
  55  		printf("\n");
  56  	}
  57  }
  58  
  59  int main(int argc, char *argv[]) {
  60  	int i, j;
  61  
  62  	FILE *fin = fopen("gauss.in", "r");
  63  	fscanf(fin, "%d", &n);
  64  	for (i = 0; i < n; ++i)
  65  		for (j = 0; j < n + 1; ++j)
  66  			fscanf(fin, "%f", &a[i][j]);
  67  	fclose(fin);
  68  	
  69  	gauss();
  70  	
  71  	return 0;
  72  }
  73  

   1  
   2  #include <stdio.h>
   3  
   4  #define GRAPHSIZE 2048
   5  #define INFINITY GRAPHSIZE*GRAPHSIZE
   6  #define MAX(a, b) ((a > b) ? (a) : (b))
   7  
   8  int e; /* The number of nonzero edges in the graph */
   9  int n; /* The number of nodes in the graph */
  10  long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */
  11  long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
  12  
  13  void printD() {
  14  	int i;
  15  	for (i = 1; i <= n; ++i)
  16  		printf("%10d", i);
  17  	printf("\n");
  18  	for (i = 1; i <= n; ++i) {
  19  		printf("%10ld", d[i]);
  20  	}
  21  	printf("\n");
  22  }
  23  
  24  void dijkstra(int s) {
  25  	int i, k, mini;
  26  	int visited[GRAPHSIZE];
  27  
  28  	for (i = 1; i <= n; ++i) {
  29  		d[i] = INFINITY;
  30  		visited[i] = 0; /* the i-th element has not yet been visited */
  31  	}
  32  
  33  	d[s] = 0;
  34  
  35  	for (k = 1; k <= n; ++k) {
  36  		mini = -1;
  37  		for (i = 1; i <= n; ++i)
  38  			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
  39  				mini = i;
  40  
  41  		visited[mini] = 1;
  42  
  43  		for (i = 1; i <= n; ++i)
  44  			if (dist[mini][i])
  45  				if (d[mini] + dist[mini][i] < d[i]) 
  46  					d[i] = d[mini] + dist[mini][i];
  47  	}
  48  }
  49  
  50  int main(int argc, char *argv[]) {
  51  	int i, j;
  52  	int u, v, w;
  53  
  54  	FILE *fin = fopen("dist.txt", "r");
  55  	fscanf(fin, "%d", &e);
  56  	for (i = 0; i < e; ++i)
  57  		for (j = 0; j < e; ++j)
  58  			dist[i][j] = 0;
  59  	n = -1;
  60  	for (i = 0; i < e; ++i) {
  61  		fscanf(fin, "%d%d%d", &u, &v, &w);
  62  		dist[u][v] = w;
  63  		n = MAX(u, MAX(v, n));
  64  	}
  65  	fclose(fin);
  66  
  67  	dijkstra(1);
  68  
  69  	printD();
  70  
  71  	return 0;
  72  }

   1  
   2  #include <stdio.h>
   3  
   4  typedef struct {
   5  	int u, v, w;
   6  } Edge;
   7  
   8  int n; /* the number of nodes */
   9  int e; /* the number of edges */
  10  Edge edges[1024]; /* large enough for n <= 2^5=32 */
  11  int d[32]; /* d[i] is the minimum distance from node s to node i */
  12  
  13  #define INFINITY 10000
  14  
  15  void printDist() {
  16  	int i;
  17  
  18  	printf("Distances:\n");
  19  
  20  	for (i = 0; i < n; ++i)
  21  		printf("to %d\t", i + 1);
  22  	printf("\n");
  23  
  24  	for (i = 0; i < n; ++i)
  25  		printf("%d\t", d[i]);
  26  
  27  	printf("\n\n");
  28  }
  29  
  30  void bellman_ford(int s) {
  31  	int i, j;
  32  
  33  	for (i = 0; i < n; ++i)
  34  		d[i] = INFINITY;
  35  
  36  	d[s] = 0;
  37  
  38  	for (i = 0; i < n - 1; ++i)
  39  		for (j = 0; j < e; ++j)
  40  			if (d[edges[j].u] + edges[j].w < d[edges[j].v])
  41  				d[edges[j].v] = d[edges[j].u] + edges[j].w;
  42  }
  43  
  44  int main(int argc, char *argv[]) {
  45  	int i, j;
  46  	int w;
  47  
  48  	FILE *fin = fopen("dist.txt", "r");
  49  	fscanf(fin, "%d", &n);
  50  	e = 0;
  51  
  52  	for (i = 0; i < n; ++i)
  53  		for (j = 0; j < n; ++j) {
  54  			fscanf(fin, "%d", &w);
  55  			if (w != 0) {
  56  				edges[e].u = i;
  57  				edges[e].v = j;
  58  				edges[e].w = w;
  59  				++e;
  60  			}
  61  		}
  62  	fclose(fin);
  63  
  64  	/* printDist(); */
  65  
  66  	bellman_ford(0);
  67  
  68  	printDist();
  69  
  70  	return 0;
  71  }

   1  
   2  #include <stdio.h>
   3  
   4  #define MAXWEIGHT 100
   5  
   6  int n = 3; /* The number of objects */
   7  int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
   8  				YOU PAY to take the object */
   9  int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
  10  				what YOU GET for taking the object */
  11  int W = 10; /* The maximum weight you can take */ 
  12  
  13  void fill_sack() {
  14  	int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
  15  				using at most i weight */
  16  	int last_added[MAXWEIGHT]; /* I use this to calculate which object were
  17  					added */
  18  	int i, j;
  19  	int aux;
  20  
  21  	for (i = 0; i <= W; ++i) {
  22  		a[i] = 0;
  23  		last_added[i] = -1;
  24  	}
  25  
  26  	a[0] = 0;
  27  	for (i = 1; i <= W; ++i)
  28  		for (j = 0; j < n; ++j)
  29  			if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
  30  				a[i] = a[i - c[j]] + v[j];
  31  				last_added[i] = j;
  32  			}
  33  
  34  	for (i = 0; i <= W; ++i)
  35  		if (last_added[i] != -1)
  36  			printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);
  37  		else
  38  			printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);
  39  
  40  	printf("---\n");
  41  
  42  	aux = W;
  43  	while ((aux > 0) && (last_added[aux] != -1)) {
  44  		printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
  45  		aux -= c[last_added[aux]];
  46  	}
  47  
  48  	printf("Total value added: %d$\n", a[W]);
  49  }
  50  
  51  int main(int argc, char *argv[]) {
  52  	fill_sack();
  53  
  54  	return 0;
  55  }

   1  
   2  #include <stdio.h>
   3  
   4  int n = 5; /* The number of objects */
   5  int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what
   6  				YOU PAY to take the object */
   7  int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.
   8  				what YOU GET for taking the object */
   9  int W = 15; /* The maximum weight you can take */
  10  
  11  void simple_fill() {
  12  	int cur_w;
  13  	float tot_v;
  14  	int i, maxi;
  15  	int used[10];
  16  
  17  	for (i = 0; i < n; ++i)
  18  		used[i] = 0; /* I have not used the ith object yet */
  19  
  20  	cur_w = W;
  21  	while (cur_w > 0) { /* while there's still room*/
  22  		/* Find the best object */
  23  		maxi = -1;
  24  		for (i = 0; i < n; ++i)
  25  			if ((used[i] == 0) &&
  26  				((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
  27  				maxi = i;
  28  
  29  		used[maxi] = 1; /* mark the maxi-th object as used */
  30  		cur_w -= c[maxi]; /* with the object in the bag, I can carry less */
  31  		tot_v += v[maxi];
  32  		if (cur_w >= 0)
  33  			printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
  34  		else {
  35  			printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
  36  			tot_v -= v[maxi];
  37  			tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
  38  		}
  39  	}
  40  
  41  	printf("Filled the bag with objects worth %.2f$.\n", tot_v);
  42  }
  43  
  44  int main(int argc, char *argv[]) {
  45  	simple_fill();
  46  
  47  	return 0;
  48  }

   1  
   2  #include <stdio.h>
   3  
   4  int n; /* Then number of nodes */
   5  int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if
   6  			it exists, or 0 if it does not */
   7  
   8  void printDist() {
   9  	int i, j;
  10  	printf("    ");
  11  	for (i = 0; i < n; ++i)
  12  		printf("%4c", 'A' + i);
  13  	printf("\n");
  14  	for (i = 0; i < n; ++i) {
  15  		printf("%4c", 'A' + i);
  16  		for (j = 0; j < n; ++j)
  17  			printf("%4d", dist[i][j]);
  18  		printf("\n");
  19  	}
  20  	printf("\n");
  21  }
  22  
  23  /*
  24  	floyd_warshall()
  25  
  26  	after calling this function dist[i][j] will the the minimum distance
  27  	between i and j if it exists (i.e. if there's a path between i and j)
  28  	or 0, otherwise
  29  */
  30  void floyd_warshall() {
  31  	int i, j, k;
  32  	for (k = 0; k < n; ++k) {
  33  		printDist();
  34  		for (i = 0; i < n; ++i)
  35  			for (j = 0; j < n; ++j)
  36  				/* If i and j are different nodes and if 
  37  					the paths between i and k and between
  38  					k and j exist, do */
  39  				if ((dist[i][k] * dist[k][j] != 0) && (i != j))
  40  					/* See if you can't get a shorter path
  41  						between i and j by interspacing
  42  						k somewhere along the current
  43  						path */
  44  					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
  45  						(dist[i][j] == 0))
  46  						dist[i][j] = dist[i][k] + dist[k][j];
  47  	}
  48  	printDist();
  49  }
  50  
  51  int main(int argc, char *argv[]) {
  52  	FILE *fin = fopen("dist.txt", "r");
  53  	fscanf(fin, "%d", &n);
  54  	int i, j;
  55  	for (i = 0; i < n; ++i)
  56  		for (j = 0; j < n; ++j)
  57  			fscanf(fin, "%d", &dist[i][j]);
  58  	fclose(fin);
  59  
  60  	floyd_warshall();
  61  
  62  	return 0;
  63  }
  64  

   1  
   2  #include <stdio.h>
   3  
   4  /*
   5  	The input file (weight.txt) look something like this
   6  		4
   7  		0 0 0 21
   8  		0 0 8 17
   9  		0 8 0 16
  10  		21 17 16 0
  11  
  12  	The first line contains n, the number of nodes.
  13  	Next is an nxn matrix containg the distances between the nodes
  14  	NOTE: The distance between a node and itself should be 0
  15  */
  16  
  17  int n; /* The number of nodes in the graph */
  18  
  19  int weight[100][100]; /* weight[i][j] is the distance between node i and node j;
  20  			if there is no path between i and j, weight[i][j] should
  21  			be 0 */
  22  
  23  char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum
  24  			spanning tree; 0 otherwise*/
  25  
  26  int d[100]; /* d[i] is the distance between node i and the minimum spanning
  27  		tree; this is initially infinity (100000); if i is already in
  28  		the tree, then d[i] is undefined;
  29  		this is just a temporary variable. It's not necessary but speeds
  30  		up execution considerably (by a factor of n) */
  31  
  32  int whoTo[100]; /* whoTo[i] holds the index of