Vreau sa gasesc cea mai mare valoare intre 2 numere cunoscute de tip float. Acea valoare o voi scadea pe toate muchiile unui graf, astfel incat sa nu obtin ciclu negativ daca aplic algoritmul Bellman Ford.
Eu am incercat ceva si nu inteleg ce nu merge. Mie mijloc imi returneaza la final ca fiind 1.5 si eu trebuie sa obtin 1.75.Ma intereseaza cel mai mult de ce nu merge cand caut binar in main, in rest cred ca am facut bine. Iata sursa mea:
#include <cstdio>
#include <vector>
#include <list>
#include <utility>
#include <queue>
#include <cstring>
#include <iomanip>
#define inf 1000000
#define NMAX 1001
using namespace std;
typedef pair<int,float> pereche;
vector < list < pereche > > Graf;
queue < int > q;
int inQueue[NMAX],vizitat[NMAX];
vector < int > aparitii;
vector < float > d;
int n,m,scaderi;
float minim = inf;
void citesc(){
int x,y;
float c;
freopen("ciclu.in","r",stdin);
freopen("ciclu.out","w",stdout);
scanf("%d%d",&n,&m);
Graf.resize(n+1);
d.resize(n+1);
aparitii.resize(n+1);
for(register int i=1;i<=m;++i){
scanf("%d%d%f",&x,&y,&c);
Graf
- .push_back(pereche(y,c));
Graf[y].push_back(pereche(x,c));
if(c < minim)
minim = c;
}
}
void DFS(int nod){
vizitat[nod] = 1;
for(list < pereche >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
if(!vizitat[it->first]){
it->second -= minim;
DFS(it->first);
}}
int Bellman_Ford(int nod){
int top;
q.push(nod);
inQueue[nod] = 1;
++aparitii[nod];
d[nod] = 0;
while(!q.empty()){
top = q.front();
q.pop();
inQueue[top] = 0;
for(list <pereche>::iterator it = Graf[top].begin();it!=Graf[top].end();++it)
if(d[it->first] > d[top] + it->second){
d[it->first] = d[top] + it->second;
if(!inQueue[it->first]){
inQueue[it->first] = 1;
q.push(it->first);
}
++aparitii[it->first];
if(aparitii[it->first] >= n)
return 0;
}
}
return 1;
}
int main(){
citesc();
DFS(1);
scaderi++;
d.assign(n+1,inf);
while(Bellman_Ford(1)){
d.assign(n+1,inf);
memset(vizitat,0,sizeof(vizitat));
aparitii.assign(n+1,0);
DFS(1);
scaderi++;
}
float inceput = (scaderi-1)*minim;
float sfarsit = scaderi*minim;
float mijloc = 0;
while(inceput <= sfarsit){
memset(vizitat,0,sizeof(vizitat));
aparitii.assign(n+1,0);
d.assign(n+1,inf);
mijloc = (inceput+sfarsit)/2;
minim = mijloc;
DFS(1);
if(!Bellman_Ford(1))
sfarsit = mijloc-1;
else
inceput = mijloc+1;
}
printf("%d\n",scaderi);
printf("%f",mijloc);
return 0;
}