Convertir C++ en C

algorithme de DINIC

19 mai 2017 à 13:47:59

bonjour est ce que quelqu'un peut m'aider à convertir ce programme en C.

Merci

#define MAX 500
	class Dinic {
	int n, m, head[MAXN], level[MAXN], s, t, work[MAXN];
	struct edge {
	int v, c, f, nxt;
	edge() {}
	edge(int v, int c, int f, int nxt): v(v), c(c), f(f), nxt(nxt) {}
	} e[MAXM];
	bool _bfs() {
	static int q[MAXN];
	memset(level, -1, sizeof(int) * n);
	int le = 0, ri = 0;
	q[ri++] = s;
	level[s] = 0;
	while(le < ri) {
	for(int k = q[le++], i = head[k]; i != -1; i = e[i].nxt) {
	if(e[i].f < e[i].c && level[e[i].v] == -1) {
	level[e[i].v] = level[k] + 1;
	q[ri++] = e[i].v;
	}
	}
	}
	return (level[t] != -1);
	}
	int _dfs(int u, int f) {
	if(u == t)
	return f;
	for(int& i = work[u]; i != -1; i = e[i].nxt) {
	if(e[i].f < e[i].c && level[u] + 1 == level[e[i].v]) {
	int minf = _dfs(e[i].v, min(f, e[i].c - e[i].f));
	if(minf > 0) {
	e[i].f += minf;
	e[i ^ 1].f -= minf;
	return minf;
	}
	}
	}
	return 0;
	}
	public:
	void init(int nn, int src, int dst) {
	n = nn;
	s = src;
	t = dst;
	m = 0;
	memset(head, -1, sizeof(int) * n);
	}
	void addEdge(int u, int v, int c, int rc) {
	assert(u < n);
	assert(v < n);
	e[m] = edge(v, c, 0, head[u]);
	head[u] = m++;
	e[m] = edge(u, rc, 0, head[v]);
	head[v] = m++;
	assert(m < MAXM);
	}
	int maxFlow() {
	int ret = 0;
	while(_bfs()) {
	memcpy(work, head, sizeof(int) * n);
	while(true) {
	int delta = _dfs(s, INF);
	if(delta == 0)
	break;
	ret += delta;
	}
	}
	return ret;
	}
	};

Padawel

19 mai 2017 à 15:25:24

Salut

J'ignore ce qui te bloque.. étant donné que tu as juste balancé un code sans qu'on ne sache quelle portion te pose problème.

Sinon, a part les struct a déclarer comme en C et la class a convertir struct et définir les fonctions qui feront office de méthodes associées, tu n'as rien de rien particulier, la seule fonction C++ que tu as ici, c'est assert() qui peut être facile "refaite" en C.

Ksass`Peuk

19 mai 2017 à 15:30:44

Lu'!

La MACRO assert est une fonctionnalité du langage C.

Pour le reste ce code c'est une bouillie infâme de C et de C++, c'est beaucoup plus du C qu'autre chose.

Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C

Lily59

22 mai 2017 à 20:37:29

En fait j'essaye d'implémenter l'algorithme de DINIC en c. Je dois construire le graphe d'ecart, trouver le plus court chemin en nombre d'arcs , trouver l'arc avec la capacité minimale et mettre à jour le graphe et le graphe d'écart.

JE suis parvenue à créer cette structure mais je sais pas comment l'utiliser.

#if ! defined (DINIC_H)

#defineDINIC_H 1

/* IMPLANTATION */

struct maillon_arc

{ int cap;

int flow;

int ecart;

struct maillon_arc* next;

};

struct struc_sommet

{ int nbsucc;

struct maillon_arc* tete;

};

struct struct_reseau

{ int nbsommet;

int nbarcs;

int source;

int puit;

struct_sommet* sommet

};

/* PROTOTYPES DES FONCTIONS (TYPE ABSTRAIT)*/

extern void init_struct_reseau ();

extern void clear_struct_reseau ();

extern void buildGRAPH();

extern void buildRG();

extern void shortestPath();

extern void minCap();

extern void updateFlowInNet();

extern void updateFlowInRG();

#endif

Convertir C++ en C

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.

× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.

Convertir C++ en C

algorithme de DINIC

Convertir C++ en C

Supprimer

Modérer

Signaler le message aux modérateurs