Pagini recente » Cod sursa (job #3191328) | Cod sursa (job #1234641) | Cod sursa (job #2467433) | Cod sursa (job #2759530) | Cod sursa (job #3041420)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//ifstream cin("cmcm.in");
//ofstream cout("cmcm.out");
const int MAX = 610;
const int inf = 1e9 + 1;
int cap[MAX][MAX] , flow[MAX][MAX] , n , m , x , y , e , cost[MAX][MAX] , c, sink ,source;
int dist[MAX] , pre[MAX];
bool in_q[MAX];
vector <int> g[MAX];
bool bf(){
queue<int>q;
q.push(source);
for(int i = source ; i <= sink ; i++){
dist[i] = inf;
pre[i] = 0;
in_q[i] = 0;
}
in_q[source] = 1;
dist[source] = 0;
while(!q.empty()){
x = q.front();
q.pop();
in_q[x] = 0;
for(auto it : g[x]){
if(cap[x][it] - flow[x][it] > 0 && dist[it] > dist[x] + cost[x][it]){
dist[it] = dist[x] + cost[x][it];
pre[it] = x;
if(!in_q[it]){
in_q[it] = 1;
q.push(it);
}
}
}
}
return (dist[sink]!=inf);
}
int main()
{
cin >> n >> m >> e;
while(e--){
cin >> x >> y >> c;
y += n;
cost[x][y] = c;
cost[y][x] = -c;
cap[x][y] = 1;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 1 ; i <= n ; i++){
cap[0][i] = 1;
g[0].push_back(i);
g[i].push_back(0);
}
sink = m+n+1;
source = 0;
for(int j = 1 ; j <= m ; j++){
int i = j + n;
cap[i][sink] = 1;
g[sink].push_back(i);
g[i].push_back(sink);
}
int nr = 0 , k = 0;
while(bf()){
nr++;
k+=dist[sink];
int aux = sink;
while(pre[aux]){
flow[pre[aux]][aux]++;
flow[aux][pre[aux]]--;
aux = pre[aux];
}
}
cout << nr << ' ' << k << '\n';
return 0;
}