Poj Solution 3068

http://poj.org/problem?id=3068

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <algorithm>
using namespace std;

#include <vector>

using namespace std;

typedef int type;                //��������

const int size = 230;            //ͼ�Ķ���ģ
const type MAX_FEE = (1<<30);        //��������
const int MAX = (1<<30);            //�������
const int MAX_SIZE = size*size*2;

class minfee_flow
{

public:

    //ɾ�����б�
    void clear();
    //���һ���from��to ����Ϊc ��λ������Ϊw �ı�
    void insert_edge( int from, int to, int c, type w );
    
    //    ����С�����������ط���
    //    nodenum���� ( �����0,1...nodenum-1 )
    //    beginΪԴ��endΪ�㣬flow��4���������( NULL��ʾ������ )
    type min_fee_max_flow( int nodenum, int begin, int end, int *flow );


private:
    /*    needn't care*/

    struct edge
    {
        int c,f;
        type w;
        int to;
        edge* rev;
        edge* next;
    };                    //�ߵĶ���

    edge* e[size];                    //�ڽӱ�
    static edge edge_cache[MAX_SIZE];
    static int en;

    type fee, sum, dis[size+1], l[size];    //�ܷ��ã����·���úͣ�(dijstra)��̾��룬��4�޸ı�Ȩ�ı��
    bool sign[size];                        //(dijstra)�Ƿ�ȷ�����·
    edge *from[size];                        //(dijstra)���·���У��õ�����
    int pri[size];                            //(dijstra)..�õ��ǰ��
    int n, s, t;                            //������Դ����
    int maxflow, add;                        //�����ÿ�ε�����

    bool dijstra( );                    //(dijstra)
    void increse( edge *ep, int d );    //����*ep�����d
    void modify( );                        //�޸�l,�������·���

};

///////////////////////////////////////////////////////////////////////
//    ����ʵ��

int minfee_flow::en = 0;
minfee_flow::edge minfee_flow::edge_cache[MAX_SIZE];
///////////////////////////////////////////////////////////////////////
//    ����ʵ��

void minfee_flow::clear()
{
    int i;
    for( i=0; i<n; i++ )
        e[i] = 0;
    en = 0;
}

bool minfee_flow::dijstra( )
{
    int i, j, k, to, v;
    edge *p;

    for( i=0; i<=n; i++ )
        dis[i] = MAX_FEE;

    memset( sign, 0, sizeof(bool)*n );

    dis[ s ] = 0;

    for( i=0; i<n; i++ )
    {
        k = n;
        for( j=0; j<n; j++ )
            if( !sign[j] && dis[k] > dis[j] )
                k = j;

        if( k == n )
            break;

        sign[ k ] = true;

        for( p=e[k]; p != NULL ; p = p->next )
        if( p->f != p->c )
        {
            to = p->to;
            if( !sign[to] && dis[ to ] > ( v = dis[ k ] + l[k] - l[to] + p->w ) )
            {
                dis[ to ] = v;
                pri[ to ] = k;
                from[ to ] = p;
            }
        }
    }

    return sign[t] == true;
}

void minfee_flow::increse( edge *ep, int d )
{
    ep->f += d;
    ep->rev->f -= d;
}

void minfee_flow::modify( )
{
    int i, temp;

    add = MAX; sum = 0;
    for( i=t; i!=s; i = pri[i] )
    {
        sum += l[pri[i]] - l[i] + from[i]->w;
        if( ( temp = from[i]->c - from[i]->f ) < add )
            add = temp;
    }

    sum += l[t];

    for( i=t; i!=s; i = pri[i] )
        increse( from[i], add );

    for( i=0; i<n; i++ )
        l[i] += dis[i];

    return;
}

void minfee_flow::insert_edge( int from, int to, int c, type w )
{
    edge eg1 = { c, 0, w, to, edge_cache+en+1, e[from] }, 
         eg2 = { 0, 0, -w, from, edge_cache+en, e[to] };
    edge_cache[en] = eg1;
    edge_cache[en+1] = eg2;

    e[from] = edge_cache+en;
    e[to] = edge_cache+en+1;

    en += 2;
}

type minfee_flow::min_fee_max_flow( int nodenum, int begin, int end, int *flow )
{

    fee = 0; maxflow = 0;
    n = nodenum, s = begin, t = end;
    memset( l, 0, sizeof(type)*n );

    while( dijstra( ) )
    {
        modify( );
        fee += sum*add;
        maxflow += add;
    }
    
    if( flow )
        *flow = maxflow;

    return fee;
}

minfee_flow mf;

int main( ) {
    int n, m, a, b, v, i, ans, t = 0, fee;
    while( 1 ) {
        scanf( "%d%d", &n, &m );
        if( n == 0 && m == 0 )
            break;
        mf.clear( );
        
        for( i=0; i<m; i++ ) {
            scanf( "%d%d%d", &a, &b, &v );
            mf.insert_edge( a, b+n, 1, v );
        }

        for( i=1; i<n; i++ )
            mf.insert_edge( i+n, i, 1, 0 );
        mf.insert_edge( n, 0, 2, 0 );

        fee = mf.min_fee_max_flow( n*2, n, n*2-1, &ans );
        printf( "Instance #%d: ", ++t );

        if( ans < 2 )
            printf( "Not possiblen" );
        else
            printf( "%dn", fee );
    }
    return 0;
}