Cod sursa(job #460974)
#include <queue>
#include <bitset>
#include <cstdlib>
#include <fstream>
#include <algorithm>
#define Nmax 711
#define oo 100000000
/*
*
*/
using namespace std;
struct vertex
{
int y, c, f, d, idx;
vertex *next, *inv;
vertex( void ) : y(0), c(0), f(0), d(oo), next(NULL), inv(NULL) {}
} *G[Nmax], *fp[Nmax];
int N, M, sink=700, source;
int d[Nmax];
bitset< Nmax > inH;
class cmp
{
public:
bool operator() ( const int& x, const int& y )
{
return d[x] > d[y];
}
};
priority_queue< int, vector< int >, cmp > pQ;
inline void Add( int x, int y, int d, int idx=0 )
{
vertex *p=new vertex, *q=new vertex;
p->y=x; q->y=y;
p->c=0; q->c=1;
p->idx=0; q->idx=idx;
p->d=-d; q->d=d;
p->next=G[y]; q->next=G[x];
G[y]=p; G[x]=q;
G[y]->inv=G[x]; G[x]->inv=G[y];
}
bool MinPath( void )
{
inH&=0;
int x;
vertex *p;
fill( d+1, d+N+M+1, oo );
d[sink]=oo;
d[source]=0;
fp[source]=NULL;
inH.set(source);
for( pQ.push(source); !pQ.empty(); )
{
x=pQ.top(); pQ.pop();
inH.flip(x);
for( p=G[x]; NULL != p; p=p->next )
if( p->c > p->f && d[p->y] > d[x]+p->d )
{
fp[p->y]=p;
d[p->y]=d[x]+p->d;
if( false == inH.test(p->y) )
{
pQ.push(p->y);
inH.set(p->y);
}
}
}
return oo != d[sink];
}
int main( void )
{
vertex *p;
int E, x, y, dd;
ifstream in( "cmcm.in" );
in>>N>>M>>E;
for( int idx=1; E; --E, ++idx )
{
in>>x>>y>>dd;
y+=N+1;
Add( x, y, dd, idx );
if( false == inH.test(x) )
{
Add( source, x, 0 );
inH.set(x);
}
if( false == inH.test(y) )
{
Add( y, sink, 0 );
inH.set(y);
}
}
for( x=y=0; MinPath(); ++x, y+=d[sink] )
{
for( p=fp[sink]; p; p=fp[p->inv->y] )
++p->f, --p->inv->f;
}
ofstream out( "cmcm.out" );
out<<x<<' '<<y<<'\n';
for( y=1; y <= N && x; ++y )
{
for( p=G[y]; p; p=p->next )
if( p->f > 0 )
{
--x;
out<<p->idx<<'\n';
break;
}
}
return EXIT_SUCCESS;
}