Cod sursa(job #133833)

Utilizator raula_sanChis Raoul raula_san Data 9 februarie 2008 20:40:57
Problema Traseu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>

#define dim 64
#define inf 0x3f3f3f3f

using namespace std;

int degi[dim], dego[dim], x[dim][dim], st[dim], dr[dim], cap[dim][dim], f[dim][dim], dmin[dim][dim], d[dim], t[dim];
int n, m, src, dest, ret;

const char in[] = "traseu.in";
const char out[] = "traseu.out";

struct Comp
{
	bool operator()(int i, int j)
	{	return d[i] > d[j];
	}
};

vector <int> g[dim];
priority_queue <int, vector <int>, Comp> pq;
queue <int> q;

bool Bellman();
inline int Min(int i, int j)
{	return i < j ? i : j;
}

void ReadData()
{
	freopen(in, "rt", stdin);
	
	int i, a, b, c;
	
	for(scanf("%d %d", &n, &m), i=1; i<=m; ++i)
	{
		scanf("%d %d %d", &a, &b, &c);
		
		x[a][b] = c;
		
		ret += c;
		
		++ degi[b];
		++ dego[a];
		
		g[a].push_back(b);
	}
	
	fclose(stdin);
}

void Dijkstra(int s)
{
	memset(d, inf, sizeof(d));
	pq.push(s);
	
	vector <int> :: iterator it;

	for(it=g[s].begin(); it!=g[s].end(); ++it)
		d[*it] = x[s][*it];
	
	while(pq.empty() == false)
	{
		int nd = pq.top();
		pq.pop();
		
		for(it=g[nd].begin(); it!=g[nd].end(); ++it)
			if(d[*it] > d[nd] + x[nd][*it])
			{
				d[*it] = d[nd] + x[nd][*it];
				pq.push(*it);
			}
	}
	
	memcpy(dmin[s], d, sizeof(d));
}

void BuildNetwork()
{
	src = 0;
	dest = n + 1;
	
	int i, j;
	
	for(i=1; i<=n; ++i)
	{
		if(degi[i] > dego[i])
		{
			g[src].push_back(i);
			st[++st[0]] = i;
			cap[src][i] = degi[i] - dego[i];
		}
		if(degi[i] < dego[i])
		{
			g[i].push_back(dest);
			dr[++dr[0]] = i;
			cap[i][dest] = dego[i] - degi[i];
		}
		
		Dijkstra(i);
	}
	
	memset(x, 0, sizeof(x));
	
	for(i=1; i<=st[0]; ++i)
		for(j=1; j<=dr[0]; ++j)
		{
			x[st[i]][dr[j]] = dmin[st[i]][dr[j]];
			x[dr[j]][st[i]] = -dmin[st[i]][dr[j]];
			
			cap[st[i]][dr[j]] = inf;
		}
}

void Flow()
{
	while(Bellman())
	{
		int i, j, r;
		
		for(i=1; i<=n; ++i)
			if(f[i][dest] < cap[i][dest])
			{
				r = cap[i][dest] - f[i][dest];
				
				for(j=i; j!=0; j=t[j])
					r = Min(r, cap[t[j]][j]-f[t[j]][j]);
					
				if(!r) continue;
				
				f[i][dest] += r;
				f[dest][i] -= r;
				
				for(j=i; j!=0; j=t[j])
					f[t[j]][j] += r, f[j][t[j]] -= r;
					
//				ret += r * d[dest];
			}
	}
}

void WriteData()
{
	freopen(out, "wt", stdout);
	
	int i, j;
	for(i=1; i<=st[0]; ++i)
		for(j=1; j<=dr[0]; ++j)
			ret += x[st[i]][dr[j]] * f[st[i]][dr[j]];
			
	printf("%d", ret);
	
	fclose(stdout);
}

bool Bellman()
{
	memset(d, inf, sizeof(d));
	memset(t, 0, sizeof(t));
	q.push(src);
	d[src] = 0;
	
	while(q.empty() == false)
	{
		int nd = q.front();
		q.pop();
		
		vector <int> :: iterator it;
		
		for(it=g[nd].begin(); it!=g[nd].end(); ++it)
			if(f[nd][*it] < cap[nd][*it] && d[*it] > d[nd] + x[nd][*it])
			{
				d[*it] = d[nd] + x[nd][*it];
				t[*it] = nd;
				q.push(*it);
			}
	}
	
	return t[dest] != 0;
}

int main()
{
	ReadData();
	BuildNetwork();
	Flow();
	WriteData();
	
	return 0;
}