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