Pagini recente » Cod sursa (job #257536) | Cod sursa (job #1805643) | Cod sursa (job #2158980) | Cod sursa (job #92225) | Cod sursa (job #1411470)
#include <bits/stdc++.h>
#define oo (1<<30)
#define pb push_back
#define mp make_pair
#define N 310
#define pii pair<int,int>
using namespace std;
vector<int>v[N];
priority_queue<pii, vector<pii>, greater<pii>>pq;
deque<int>q;
bitset<N>inq;
int fl[N][N], cost[N][N], cap[N][N], db[N], dd[N], dr[N], i, s, d, nod, cst, cv, tata[N], n, m, e, x, y, co, minflow, solflow, solcost;
void bellman()
{
for(i = 1; i <= d; i++)
db[i] = oo;
db[s] = 0;
inq[s] = 1;
q.pb(1);
while(q.size())
{
nod = q.front();
q.pop_front();
inq[nod] = 0;
for(auto it : v[nod])
if(db[it] > db[nod] + cost[nod][it] && fl[nod][it] < cap[nod][it])
{
db[it] = db[nod] + cost[nod][it];
if(!inq[it])
{
inq[it] = 1;
q.pb(it);
}
}
}
}
bool dijkstra()
{
for(i = 1; i <= d; i++)
dd[i] = oo;
dd[s] = 0;
pq.push(mp(0, s));
while(pq.size())
{
nod = pq.top().second;
cst = pq.top().first;
pq.pop();
if(dd[nod] < cst)
continue;
for(auto it : v[nod])
{
cv = cost[nod][it] + db[nod] - db[it];
if(dd[it] > dd[nod] + cv && fl[nod][it] < cap[nod][it])
{
dd[it] = dd[nod] + cv;
dr[it] = dr[nod] + cost[nod][it];
tata[it] = nod;
pq.push(mp(dd[it], it));
}
}
}
for(i = 1; i <= d; i++)
db[i] = dr[i];
return dd[d] != oo;
}
int main()
{
freopen("cmcm.in", "r", stdin);
freopen("cmcm.out", "w", stdout);
scanf("%d%d%d", &n, &m, &e);
for(; e; e--)
{
scanf("%d%d%d", &x, &y, &co);
y += n;
cost[x][y] = co;
cost[y][x] = -co;
cap[x][y] = 1;
v[x].pb(y);
v[y].pb(x);
}
s = 0;
d = n + m + 1;
for(i = 1; i <= n; i++)
{
v[s].pb(i);
cap[s][i] = 1;
}
for(i = n + 1; i <= n + m; i++)
{
v[i].pb(d);
cap[i][d] = 1;
}
bellman();
while(dijkstra())
{
minflow = oo;
for(x = d; x != tata[x]; x = tata[x])
minflow = min(minflow, cap[tata[x]][x] - fl[tata[x]][x]);
for(x = d; x != tata[x]; x = tata[x])
{
fl[tata[x]][x] += minflow;
fl[x][tata[x]] -= minflow;
}
solcost += db[d] * minflow;
solflow += minflow;
}
printf("%d %d\n", solflow, solcost);
return 0;
}