Cod sursa(job #555060)

Utilizator feelshiftFeelshift feelshift Data 15 martie 2011 11:32:17
Problema Cuplaj maxim de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.37 kb
// http://infoarena.ro/problema/cmcm
#include <fstream>
#include <bitset>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
using namespace std;

#define to first
#define cost second

const int maxSize = 611;
const int oo = 0x3f3f3f3f;
const int source = 0;
const int sink = 610;

ifstream in("cmcm.in");
ofstream out("cmcm.out");

int firstSize,secondSize,edges;
bitset<maxSize> visit;
int father[maxSize];
int dist[maxSize];
int capacity[maxSize][maxSize];
int currentFlow[maxSize][maxSize];
vector< pair<int,int> > edge;
vector< pair<int,int> > graph[maxSize];

bool bellmanFord();

int main() {
    in >> firstSize >> secondSize >> edges;
    edge.reserve(edges);

    int from,to,currentCost;
    for(int i=1;i<=edges;i++) {
        in >> from >> to >> currentCost;
        to += firstSize;

        graph[from].push_back(make_pair(to,currentCost));
        graph[to].push_back(make_pair(from,-currentCost));

        capacity[from][to] = 1;
        //edge[from][to] = i;
        edge.push_back(make_pair(from,to));
    }

    for(int i=1;i<=firstSize;i++) {
        graph[source].push_back(make_pair(i,0));
        graph[i].push_back(make_pair(source,0));
        capacity[source][i] = 1;
    }

    for(int i=firstSize+1;i<=firstSize+secondSize;i++) {
        graph[i].push_back(make_pair(sink,0));
        graph[sink].push_back(make_pair(i,0));
        capacity[i][sink] = 1;
    }

    int minCost = 0;
    while(bellmanFord()) {
        int minFlow = oo;
        for(int node=sink;node!=source;node=father[node])
            minFlow = min(minFlow,capacity[father[node]][node] - currentFlow[father[node]][node]);

        if(minFlow) {
            for(int node=sink;node!=source;node=father[node]) {
                currentFlow[father[node]][node] += minFlow;
                currentFlow[node][father[node]] -= minFlow;
            }

            minCost += minFlow * dist[sink];
        }
    }

    int matches = 0;
    vector< pair<int,int> >::iterator it,end;
    end = edge.end();

    for(it=edge.begin();it!=end;++it)
        if(capacity[it->first][it->second] && currentFlow[it->first][it->second])
            matches++;

    out << matches << " " << minCost << "\n";

    for(it=edge.begin();it!=end;++it)
        if(capacity[it->first][it->second] && currentFlow[it->first][it->second])
            out << it - edge.begin() + 1 << " ";
    out << "\n";

    in.close();
    out.close();

    return (0);
}

bool bellmanFord() {
    //memset(visit,false,sizeof(visit));
    visit.reset();
    visit[source] = true;

    memset(dist,oo,sizeof(dist));
    dist[source] = 0;

    int node;
    vector< pair<int,int> >::iterator it,end;

    queue<int> myQueue;
    myQueue.push(source);

    while(!myQueue.empty()) {
        node = myQueue.front();
        myQueue.pop();

        end = graph[node].end();
        for(it=graph[node].begin();it!=end;++it)
            if(capacity[node][it->to] > currentFlow[node][it->to] && dist[it->to] > dist[node] + it->cost) {
                dist[it->to] = dist[node] + it->cost;
                father[it->to] = node;

                if(!visit[it->to]) {
                    myQueue.push(it->to);
                    visit[it->to] = true;
                }
            }

        visit[node] = false;
    }

    return (dist[sink] != oo);
}