Pagini recente » Cod sursa (job #1254997) | Istoria paginii runda/225200/clasament | Cod sursa (job #1625006) | Cod sursa (job #2212218) | Cod sursa (job #1374288)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
#define Nmax 605
#define inf 0x3f3f3f3f
using namespace std;
ifstream in("cmcm.in");
ofstream out("cmcm.out");
struct cmp
{
bool operator() (const pair<int, int> &x, const pair<int, int> &y)
{
return x.first > y.first;
}
};
int oldD[Nmax], newD[Nmax], D[Nmax];
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp > PQ;
vector<int> G[Nmax];
vector<pair<int, int> > edges;
int Capacity[Nmax][Nmax], Cost[Nmax][Nmax], parent[Nmax], initialCapacity[Nmax][Nmax];
bool dijkstra(int source, int destination)
{
bool inQueue[Nmax];
memset(inQueue, false, sizeof(inQueue));
memset(D, inf, sizeof(D));
D[source] = 0;
PQ.push(make_pair(0, source));
while (!PQ.empty())
{
int node = PQ.top().second;
int cost = PQ.top().first;
PQ.pop();
if (node == destination || D[node] != cost) continue;
for (int i = 0; i < G[node].size(); i++)
{
int nextNode = G[node][i];
int newCost = D[node] + oldD[node] - oldD[nextNode] + Cost[node][nextNode];
if (Capacity[node][nextNode] && newCost < D[nextNode])
{
parent[nextNode] = node;
D[nextNode] = newCost;
newD[nextNode] = newD[node] + Cost[node][nextNode];
PQ.push(make_pair(D[nextNode], nextNode));
}
}
}
memcpy(oldD, newD, sizeof(D));
if (D[destination] != inf) return true;
return false;
}
void bellmanFord(int source)
{
queue<int> Q;
bool inQueue[Nmax];
memset(oldD, inf, sizeof(oldD));
memset(inQueue, false, sizeof(inQueue));
inQueue[source] = true;
oldD[source] = 0;
Q.push(source);
while (!Q.empty())
{
int node = Q.front();
Q.pop();
for (int i = 0; i < G[node].size(); i++)
{
int nextNode = G[node][i];
int cost = Cost[node][nextNode];
if (Capacity[node][nextNode] && oldD[node] + cost < oldD[nextNode])
{
D[nextNode] = oldD[node] + cost;
if (!inQueue[nextNode])
{
Q.push(nextNode);
inQueue[nextNode] = true;
}
}
}
inQueue[node] = false;
}
}
int main()
{
int N1, N2, M, source, destination;
in >> N1 >> N2 >> M;
for (int i = 1; i <= M; i++)
{
int x, y, c;
in >> x >> y >> c;
edges.push_back(make_pair(x, y));
G[x].push_back(y + N1);
G[y + N1].push_back(x);
Capacity[x][y + N1] = 1;
Cost[x][y + N1] = c;
Cost[y + N1][x] = -c;
}
source = 0;
for (int i = 1; i <= N1; i++)
{
G[source].push_back(i);
Cost[source][i] = 0;
Capacity[source][i] = 1;
}
destination = N1 + N2 + 1;
for (int i = 1; i <= N2; i++)
{
G[N1 + i].push_back(destination);
Cost[N1 + i][destination] = 0;
Capacity[N1 + i][destination] = 1;
}
bellmanFord(source);
int totalCost = 0, totalFlow = 0;
while (dijkstra(source, destination))
{
int node = destination, flow = inf, cost = 0;
while (node != source)
{
flow = min(flow, Capacity[parent[node]][node]);
node = parent[node];
}
node = destination;
while (node != source)
{
Capacity[parent[node]][node] -= flow;
Capacity[node][parent[node]] += flow;
cost += flow * Cost[parent[node]][node];
node = parent[node];
}
totalFlow += flow;
totalCost += cost;
}
out << totalFlow << " " << totalCost << "\n";
for (int i = 0; i < edges.size(); i++)
{
int node1 = edges[i].first;
int node2 = edges[i].second + N1;
if (Capacity[node1][node2] == 0)
out << i + 1 << " ";
}
}