Pagini recente » Cod sursa (job #1741399) | Cod sursa (job #2644654) | Cod sursa (job #2762308) | Cod sursa (job #1368920) | Cod sursa (job #719015)
Cod sursa(job #719015)
#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;
}