同一个类，2195最小费用最大流能过

#include <limits>

void ruin()
{
	int *tp = 0;
	*tp = 1;
}

template<class T, int N> class cMinimumCostNFlow
{
public:
	T shortest[N];
	T smap[N][N];
	T wmap[N][N];
	T cmap[N][N];
	T fmap[N][N];
	int n;
	int trace[N];

	cMinimumCostNFlow()
	{
		reset();
	}

	void reset()
	{
		resetc();
		resetf();
		resetw();
		resets();
	}

	void resetc()
	{
		memset( cmap, 0, sizeof cmap );
	}
	void resetf()
	{
		memset( fmap, 0, sizeof fmap );
	}
	void resetw()
	{
		memset( wmap, 0, sizeof wmap );
	}
	void resets()
	{
		memset( smap, 0, sizeof smap );
	}
	void resett()
	{
		for( int i=0; i<N; i++ )
			trace[i] = i;
	}

	void calculateMinCostFlow( T *maxFlow, T *minCost )
	{
		while( 1 )
		{
			resets();

			for( int i=0; i<n; i++ )
				for( int j=0; j<n; j++ )
				{
					if( cmap[i][j] > fmap[i][j] )
					{
						smap[i][j] = wmap[i][j];
					}
					if( fmap[i][j] > 0 )
					{
						smap[j][i] = -wmap[i][j];
					}
				}

			for( int i=0; i<n; i++ )
				shortest[i] = std::numeric_limits<T>::max();
			shortest[0] = 0;
			resett();

			bool c = true;
			while( 1 )
			{
				c = false;
				for( int i=0; i<n; i++ )
					for( int j=0; j<n; j++ )
						if( cmap[i][j]>fmap[i][j] || fmap[j][i]>0 ) // BUG2: smap[i][j]. shall fail when w[i][j] = 0
						{
							if( shortest[i] == std::numeric_limits<T>::max() )
								continue;

							if( shortest[i] + smap[i][j] < shortest[j] ) // !! calculation overflow!!
							{
								trace[j] = i;

								c = true;
								shortest[j] = shortest[i] + smap[i][j];
							}
						}
				if( !c ) break;
			}

			if( shortest[n-1] == std::numeric_limits<T>::max() )
			{
				*minCost = 0;
				for( int i=0; i<n; i++ )
					for( int j=0; j<n; j++ )
						if( fmap[i][j] )
							*minCost += wmap[i][j] * fmap[i][j];
				*maxFlow = 0;
				for( int i=0; i<n; i++ )
					*maxFlow += fmap[i][n-1];

				return;
			}

			T mindf = std::numeric_limits<T>::max();
			int lnode = n-1;
			while( lnode != trace[lnode] )
			{
				int node = lnode;
				lnode = trace[lnode];

				if( fmap[node][lnode] > 0 && cmap[lnode][node]>fmap[lnode][node] )
					ruin();
				if( fmap[node][lnode] == 0 && cmap[lnode][node] == fmap[lnode][node] )
					ruin();

				if( fmap[node][lnode] > 0 )
					if( fmap[node][lnode] < mindf )
						mindf = fmap[node][lnode];
				if( cmap[lnode][node] > fmap[lnode][node] )
					if( mindf > cmap[lnode][node]-fmap[lnode][node] )
						mindf = cmap[lnode][node] - fmap[lnode][node];
			}

			if( mindf <= 0 )
			ruin();

			lnode = n-1;
			while( lnode != trace[lnode] )
			{
				int node = lnode;
				lnode = trace[lnode];

				if( fmap[node][lnode] > 0 && cmap[lnode][node]>fmap[lnode][node] )
					ruin();
				if( fmap[node][lnode] == 0 && cmap[lnode][node] == fmap[lnode][node] )
					ruin();

				if( fmap[node][lnode] > 0 )
					fmap[node][lnode] -= mindf;
				if( cmap[lnode][node] > fmap[lnode][node] )
					fmap[lnode][node] += mindf;
			}

		} // while 1
	}
};


cMinimumCostNFlow< int, 120 > flow;

#include <iostream>
using namespace std;

int order[50][50];
int storage[50][50];

int main()
{
	int N,M,K;
	while( 1 )
	{
		cin>>N>>M>>K;
		if( !N && !M && !K )
			break;
		
		for( int i=0; i<N; i++ )
			for( int j=0; j<K; j++ )
				cin>>order[i][j];
		for( int i=0; i<M; i++ )
			for( int j=0; j<K; j++ )
				cin>>storage[i][j];

		int total = 0;
		bool noa = false;
		for( int ik = 0; ik < K; ik++ )
		{
			if( noa )
				break;

			flow.reset();
			flow.n = N+M+2;
			for( int i=1; i<=M; i++ )
				flow.cmap[0][i] = storage[i-1][ik];
			for( int i=1; i<=M; i++ )
				for( int j=M+1; j<=M+N; j++ )
					flow.cmap[i][j] = 100;
			for( int i=M+1; i<=M+N; i++ )
				flow.cmap[i][N+M+1] = order[i-M-1][ik];

			for( int i=0; i<N; i++ )
				for( int j=0; j<M; j++ )
					cin>>flow.wmap[j+1][i+M+1];

			int maxFlow, minCost;
			flow.calculateMinCostFlow( &maxFlow, &minCost );
			total += minCost;
			for( int i=0; i<N; i++ )
				if( flow.fmap[i+M+1][N+M+1] != order[i][ik] )
				{
					noa = true;
					break;
				}
		} // for ik

		if( noa )
			cout<<-1<<endl;
		else cout<<total<<endl;

	}
	return 0;
}

• 各位大牛高抬贵眼。。 此问题遗留两个月拉 严重影响了社会主义科学技术发展 (2) Nat 2008-11-13 10:37:27
• 此问题遗留了整整5个月了，我看过N遍，仍然钻不出。。。。 (2) Nat 2009-04-13 18:39:39