FUDforum
Fast Uncompromising Discussions. FUDforum will get your users talking.
Home » Imported messages » comp.lang.php » terminate a PHP script
Show: Today's Messages :: Polls :: Message Navigator
Return to the default flat view Create a new topic Submit Reply
Re: terminate a PHP script [message #172598 is a reply to message #172595] Tue, 22 February 2011 02:45 Go to previous messageGo to previous message
n00m is currently offline  n00m
Messages: 25
Registered: February 2011
Karma:
Junior Member
The same Assignment Problem (hungarian algorithm):
====================================================

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

#define N 100
int res_sum;
int res_table[N][N];
int v[N][N], u[N][N], cross[N][N];
int row[N], col[N];
int rowround[N], colround[N];
int userow[N];
int vmax = 0;
size_t n;

void pivot() {
int umin;
size_t i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
vmax = std::max(vmax, v[i][j]);
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
u[i][j] = v[i][j];
for (i = 0; i < n; ++i) {
umin = u[i][0];
for (j = 1; j < n; ++j)
umin = std::min(umin, u[i][j]);
for (j = 0; j < n; ++j)
u[i][j] -= umin;
}
for (j = 0; j < n; ++j) {
umin = u[0][j];
for (i = 1; i < n; ++i)
umin = std::min(umin, u[i][j]);
for (i = 0; i < n; ++i)
u[i][j] -= umin;
}
}

void mark() {
size_t i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
cross[i][j] = 0;
for (i = 0; i < n; ++i)
row[i] = col[i] = 0;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (u[i][j] == 0)
if (row[i] == 0 && col[j] == 0) {
cross[i][j] = 1;
row[i] = col[j] = 1;
}
else
cross[i][j] = -1;
}

int findcouple(size_t k) {
size_t i, j = 0;
while (cross[k][j] != 1) ++j;
for (i = 0; i < n; ++i)
if (cross[i][j] == -1 && !userow[i]) {
if (!row[i]) {
row[i] = 1;
cross[i][j] = 1;
cross[k][j] = -1;
return 1;
}
else {
userow[i] = 1;
if (findcouple(i)) {
cross[i][j] = 1;
cross[k][j] = -1;
return 1;
}
}
}
return 0;
}

int upcouple() {
size_t i, j;
for (i = 0; i < n; ++i)
userow[i] = 0;
for (j = 0; j < n; ++j)
if (!col[j])
for (i = 0; i < n; ++i)
if (cross[i][j] == -1) {
userow[i] = 1;
if (findcouple(i)) {
col[j] = 1;
cross[i][j] = 1;
return 1;
}
else
userow[i] = 0;
}
return 0;
}

void maxcouple() {
while (upcouple());
}

int fin() {
for (size_t i = 0; i < n; ++i)
if (!row[i])
return 0;
return 1;
}

void minsupport() {
size_t i, j;
for (i = 0; i < n; ++i)
rowround[i] = colround[i] = 0;
for (i = 0; i < n; ++i)
rowround[i] = 1 - row[i];
bool b = true;
while (b) {
b = false;
for (i = 0; i < n; ++i)
if (rowround[i])
for (j = 0; j < n; ++j)
if (cross[i][j] == -1)
colround[j] = 1;
for (j = 0; j < n; ++j)
if (colround[j])
for (i = 0; i < n; ++i)
if (cross[i][j] == 1 && !rowround[i]) {
b = true;
rowround[i] = 1;
}
}
}

void rotate() {
size_t i, j;
int vmin = vmax;
for (i = 0; i < n; ++i)
if (rowround[i])
for (j = 0; j < n; ++j)
if (!colround[j])
if (vmin > u[i][j])
vmin = u[i][j];
for (i = 0; i < n; ++i)
if (!rowround[i])
for (j = 0; j < n; ++j)
u[i][j] += vmin;
for (j = 0; j < n; ++j)
if (!colround[j])
for (i = 0; i < n; ++i)
u[i][j] -= vmin;
}

void hungarian() {
pivot();
while (true) {
mark();
maxcouple();
if (fin()) break;
minsupport();
rotate();
}
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j)
if (cross[i][j] == 1) {
res_table[i][j] = v[i][j];
res_sum += v[i][j];
break;
}
}
}

int main() {
n = 5;
srand(time(NULL));
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
v[i][j] = rand() % 100;
col[j] += v[i][j];
printf("%3d", v[i][j]);
}
putchar('\n');
}

hungarian();

putchar('\n');
for (size_t i = 0; i < n; ++i) {
for (size_t j = 0; j < n; ++j) {
printf("%3d", res_table[i][j]);
}
putchar('\n');
}
printf("\nres_sum = %d\n\n", res_sum);
system("pause");
return 0;
}


===================================================
Output:
===================================================

44 79 18 39 70
45 82 84 7 52
71 63 56 55 94
21 67 86 5 67
5 39 67 68 86

0 0 18 0 0
0 0 0 0 52
0 63 0 0 0
0 0 0 5 0
5 0 0 0 0

res_sum = 143

Press any key to continue . . .

Report message to a moderator

[Message index]
 
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Read Message
Previous Topic: Extralight browser-webserver communication via cookies (+)
Next Topic: Storing multiple character set types (or a representation of em) in a table column
Goto Forum:
  

-=] Back to Top [=-
[ Syndicate this forum (XML) ] [ RSS ]

Current Time: Tue Nov 26 23:23:11 GMT 2024

Total time taken to generate the page: 0.04419 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.1.3.
Copyright ©2001-2023 FUDforum Bulletin Board Software