Участник:Andriygav/MSE06I

Материал из DISCOPAL
Перейти к: навигация, поиск
  • компилятор: gcc 8.3
#include <cstring>
#include <iostream>
using namespace std;
 
int src, snk, nNode, nEdge;
int fin[64], pre[64], dist[64];
int cap[1024], cost[1024], _next[1024], to[1024], from[1024];
 
void addEdge(int u, int v, int c, int e){
    from[nEdge] = u;
    to[nEdge] = v;
    cap[nEdge] = c;
    cost[nEdge] = e;
    _next[nEdge] = fin[u];
    fin[u] = nEdge++;
 
    from[nEdge] = v;
    to[nEdge] = u;
    cap[nEdge] = 0;
    cost[nEdge] =-e;
    _next[nEdge] = fin[v];
    fin[v] = nEdge++;
}
 
bool bellman(){
    int iter, u, v, i;
    bool flag = true;
    memset(dist, 127, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    dist[src] = 0;
    for(iter = 1; iter < nNode && flag; iter++){
        flag = false;
        for(u = 0; u < nNode; u++){
            for(i = fin[u]; i >= 0; i = _next[i]){
                v = to[i];
                if(cap[i] && dist[v] > dist[u] + cost[i]){
                    dist[v] = dist[u] + cost[i];
                    pre[v] = i;
                    flag = true;
                }
            }
        }
    }
    return (dist[snk] < 2139062143);
}
 
int mcmf(int &fcost) {
    int netflow, i, bot, u;
    netflow = fcost = 0;
    while(bellman()) {
        bot = 2139062143;
        for(u = pre[snk]; u >= 0; u = pre[from[u]]) bot = min(bot, cap[u]);
        for(u = pre[snk]; u >= 0; u = pre[from[u]]){
            cap[u] -= bot;
            cap[u^1] += bot;
            fcost += bot * cost[u];
        }
        netflow += bot;
    }
    return netflow;
}
 
int main() {
    int n, m, test = 0;
    cin >> n >> m;
    while(n + m){
        test++;
        memset(fin, -1, sizeof(fin));
        nEdge = 0;
        for(int i = 1; i < n - 1; i++){
            addEdge(i*2 - 1, i*2, 1, 0);
        }
        addEdge((n-1)*2-1, (n-1)*2, 2, 0);
        src = 0;
        snk = (n-1)*2;
        nNode = snk + 1;
        for(int i = 0; i < m; i++){
            int u, v, w;
            cin >> u >> v >> w;
            addEdge(2*u, 2*v-1, 1, w);
        }
        cout << "Instance #" << test <<":  ";
        int fcost;
        if(mcmf(fcost) == 2){
            cout << fcost << endl;
        }else{
            cout << "Not possible" << endl;
        }
        cin >> n >> m;
    }
    return 0;
}