Pagini recente » Cod sursa (job #1733471) | Cod sursa (job #209291) | Cod sursa (job #163284) | Cod sursa (job #2864951) | Cod sursa (job #2876512)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("cmcm.in");
ofstream g("cmcm.out");
const int INF = 2e9;
int n, m, e;
int cap[605][605];
int cost[605][605];
int flow[605][605];
int dist[605];
int parent[605];
bool used[605];
bool inCuplaj[605][605];
vector < int > adj[605];
int BellmanFord(int source, int dest)
{
queue < int > q;
for (int i = 0; i <= n + m + 1; i++)
{
dist[i] = INF;
parent[i] = 0;
used[i] = false;
}
q.push(source);
dist[source] = 0;
used[source] = true;
while (!q.empty())
{
int node = q.front();
q.pop();
for (auto it : adj[node])
if (cap[node][it] - flow[node][it] > 0 && dist[node] + cost[node][it] < dist[it])
{
dist[it] = dist[node] + cost[node][it];
parent[it] = node;
if (!used[it])
{
q.push(it);
used[it] = true;
}
}
used[node] = false;
}
if (dist[dest] != INF)
{
int fmin = INF;
for (int i = dest; i != source; i = parent[i])
fmin = min(fmin, cap[parent[i]][i] - flow[parent[i]][i]);
if (fmin > 0)
for (int i = dest; i != source; i = parent[i])
{
flow[parent[i]][i] += fmin;
flow[i][parent[i]] -= fmin;
inCuplaj[parent[i]][i] = true;
}
return fmin * dist[dest];
}
return 0;
}
int main()
{
f >> n >> m >> e;
for (int i = 1; i <= e; i++)
{
int x, y, c; f >> x >> y >> c;
y += n;
adj[x].push_back(y);
adj[y].push_back(x);
cap[x][y] = 1;
cost[x][y] = c;
cost[y][x] = -c;
}
int source = 0;
int dest = n + m + 1;
for (int i = 1; i <= n; i++)
{
adj[source].push_back(i);
adj[i].push_back(source);
cap[source][i] = 1;
cost[source][i] = 0;
cost[i][source] = 0;
}
for (int i = n + 1; i <= n + m; i++)
{
adj[i].push_back(dest);
adj[dest].push_back(i);
cap[i][dest] = 1;
cost[i][dest] = 0;
cost[dest][i] = 0;
}
long long c = 0;
bool stop = false;
while (!stop)
{
int aux = BellmanFord(source, dest);
c += aux;
if (!aux)
stop = true;
}
int nr = 0;
for (int i = 1; i <= n + m; i++)
for (auto it : adj[i])
if (it != source && it != dest && inCuplaj[i][it])
nr++;
g << nr << " " << c << "\n";
return 0;
}