Cod sursa(job #719015)

Utilizator deividFlorentin Dumitru deivid Data 21 martie 2012 12:22:33
Problema Cuplaj maxim de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.18 kb
#include<stdio.h>
#include<vector>
#include<queue>

#define maxn 305
#define maxe 50005
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define INF 0x3f3f3f3f

using namespace std;

FILE*f=fopen("cmcm.in","r");
FILE*g=fopen("cmcm.out","w");

const int dif = 300;
const int S = 601,D = 602;
int n,m,e;
int X[maxe],Y[maxe],inq[maxn<<1],dist[maxn<<1];
int L,H[maxn<<1],Poz[maxn<<1],C[maxn<<1],T[maxn<<1];
int Cp[maxn<<1][maxn<<1],F[maxn<<1][maxn<<1];
vector< pii >G[maxn<<1];
queue<int>Q;

inline void citire () {
	
	fscanf(f,"%d %d %d",&n,&m,&e);
	
	int x,y,c;
	for ( int i = 1 ; i <= e ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&c); y += dif;
		G[x].pb(mp(y,c));
		G[y].pb(mp(x,-c));
		Cp[x][y] = 1;
		X[i] = x; Y[i] = y;
	}
}

inline void adauga_muchii () {
	
	for ( int i = 1 ; i <= n ; ++i ){
		G[S].pb(mp(i,1));
		Cp[S][i] = 1;
	}
	
	for ( int i = 1 ; i <= m ; ++i ){
		int x = i + dif;
		G[x].pb(mp(D,1)); G[D].pb(mp(x,-1));
		Cp[x][D] = 1;
	}
}

inline void bellman_ford () {
	int nod;
	
	Q.push(S); inq[S] = 1;
	memset(dist,INF,sizeof(dist));
	dist[S] = 0;
	
	while ( !Q.empty() ){
		nod = Q.front(); Q.pop(); inq[nod] = 0;
		
		for ( vector< pii >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			int nodvcn = itt->first; int cost = itt->second;
			if ( dist[nodvcn] > dist[nod] + cost && Cp[nod][nodvcn] > F[nod][nodvcn] ){
				dist[nodvcn] = dist[nod] + cost;
				
				if ( !inq[nodvcn] ){
					Q.push(nodvcn); inq[nodvcn] = 1;
				}
			}
		}
	}
}

inline void swap ( int &a , int &b ){
	int aux = a ; a = b ; b = aux;
}

inline void urca ( int poz ){
	
	while ( poz > 1 && dist[H[poz>>1]] > dist[H[poz]] ){
		swap(H[poz>>1],H[poz]);
		swap(Poz[H[poz>>1]],Poz[H[poz]]);
		poz >>= 1;
	}
}

inline void coboara ( int x ){
	int y = 0;
	
	while ( x != y ){
		y = x;
		
		if ( 2*y <= L && dist[H[2*y]] < dist[H[x]] ){
			x = 2*y;
		}
		if ( 2*y+1 <= L && dist[H[2*y+1]] < dist[H[x]] ){
			x = 2*y+1;
		}
		
		swap(H[x],H[y]);
		swap(Poz[H[x]],Poz[H[y]]);
	}
}

inline void insert ( int nod ){
	
	H[++L] = nod; Poz[nod] = L;
	urca(L);
}

inline int pop () {
	int nod = H[1];
	
	swap(H[1],H[L]); swap(Poz[H[1]],Poz[H[L]]);
	H[L] = Poz[H[L]] = 0; --L;
	coboara(1);
	
	return nod;
}

inline bool dijkstra () {
	int nod;
	
	memset(dist,INF,sizeof(dist)); dist[S] = 0;
	insert(S);
	
	while ( L ){
		nod = pop();
		
		for ( vector< pii >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			int nodvcn = itt->first; int cost = itt->second;
			
			if ( dist[nodvcn] > dist[nod] + cost && Cp[nod][nodvcn] > F[nod][nodvcn] ){
				dist[nodvcn] = dist[nod] + cost; T[nodvcn] = nod;
				
				if ( Poz[nodvcn] ){
					urca(Poz[nodvcn]);
				}
				else{
					insert(nodvcn);
				}
			}
		}
	}
	
	return dist[D] != INF;
}

inline void update_costuri () {
	
	for ( int i = 1 ; i <= n ; ++i ){
		for ( vector< pii >::iterator itt = G[i].begin() ; itt != G[i].end() ; ++itt ){
			int nodvcn = itt->first; int cost = itt->second;
			itt->second = cost + dist[i] - dist[nodvcn];
		}
	}
	
	for ( int i = 1 ; i <= m ; ++i ){
		int j = i + dif;
		for ( vector< pii >::iterator itt = G[j].begin() ; itt != G[j].end() ; ++itt ){
			int nodvcn = itt->first; int cost = itt->second;
			itt->second = cost + dist[j] - dist[nodvcn];
		}
	}
	
	for ( vector< pii >::iterator itt = G[S].begin() ; itt != G[S].end() ; ++itt ){
		int nodvcn = itt->first; int cost = itt->second;
		itt->second = cost + dist[S] - dist[nodvcn];
	}
	
	for ( vector< pii >::iterator itt = G[D].begin() ; itt != G[D].end() ; ++itt ){
		int nodvcn = itt->first; int cost = itt->second;
		itt->second = cost + dist[D] - dist[nodvcn];
	}
}


inline void cmcm () {
	int toD = 0,cuplaj = 0,nod,cost = 0;
	
	bellman_ford(); update_costuri(); toD = dist[D];
	
	while ( dijkstra() ){
		
		for ( nod = D ; T[nod] ; nod = T[nod] ){
			++F[T[nod]][nod];
			--F[nod][T[nod]];
		}
		
		++cuplaj; cost += dist[D] + toD; toD += dist[D];
		update_costuri();
	}
	
	fprintf(g,"%d %d\n",cuplaj,cost);
}

int main () {
	
	citire();
	adauga_muchii();
	cmcm();
	
	fclose(f);
	fclose(g);
	
	return 0;
}