Informatika gyűjtemény

Egy szinttel feljebb Megoldas

2004050607080910

NézetNyomtat

Algoritmus

A "nem-ismer" élek mentén, szélességi kereséssel A-B párokat csinálunk, majd a párokon belüli különbségek összegét (exponenciális) algoritmussal minimalizáljuk, az előjelek megfelelő megválasztásával. Csak azokat a komponenseket vesszük be, a nyers-erő optimalizálásba, ahol az A és B elemszámának különbsége több, mit egy. Így legfeljebb $2^{25}$ lépést kell az optimális előjelezés megtalálásához végezni.

Kódok

mb_teams.c (Mészáros Balázs, C)