# 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;                            //������Դ����

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 )
}

sum += l[t];

for( i=t; i!=s; i = pri[i] )

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( );
}

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;
}

```
This entry was posted in poj. Bookmark the permalink.