poj 1275 Cashier Employment - nazgul's Blog

poj 1275 Cashier Employment

nazgul posted @ 2010年10月21日 21:31 in POJ , 1717 阅读

 

差分约束系统(SPFA)  
对于差分约束系统,建立的不等式是>=则在SPFA中求最长路。A-B>=C,则从B连一条权为C的边到A。
反之求最短路。A-B<=C,则从B连一条权为C的边到A。
注意两者对DIS初始化的不同
具体分析见2006国家集训队论文冯威--数与图的完美结合---浅析差分约束系统 

#include <stdio.h>
#include <string.h>
#define MAXN 30
#define MAXE 100
#define INF 0x3fffffff

struct node
{
	int v, d, next; //
}pot[MAXE];
int g[MAXN], pl, r[MAXN], t[MAXN], c[MAXN];
int dis[MAXN], visit[MAXN], queue[MAXN], ans;

int spfa( int n, int s ) //点的个数,源点,汇点
{
	int top, tail, u, v, k;
	for ( u = 1; u <= 24; ++u )
		dis[u] = -INF;
	memset( visit, 0, sizeof( visit ) );
	memset( c, 0, sizeof( c ) );
	dis[s] = 0; top = 0; tail = 1;
	queue[0] = s; visit[s] = 1;
	while ( top != tail ) //循环队列
	{
		u = queue[top++]; visit[u] = 0;
		if ( top == n ) top = 0;
		for ( k = g[u]; k != -1; k = pot[k].next )
		{
			v = pot[k].v;
			if ( dis[v] - pot[k].d < dis[u] )
			{
				dis[v] = dis[u] + pot[k].d;
				if ( !visit[v] )
				{
					queue[tail] = v; visit[v] = 1;
					if ( ++c[v] > n ) return 0;
					if ( ++tail == n ) tail = 0;
				}
			}
		}
	}
	return ( dis[24] == ans );
}

void addEdge( int u, int v, int w )
{
	pot[pl].next = g[u];
	pot[pl].v = v; pot[pl].d = w;
	g[u] = pl++;
}

void ConstructGraph()
{
	int i;
	memset( g, -1, sizeof( g ) );
	pl = 0;
	for ( i = 1; i <= 16; ++i )
		addEdge( i, i+8, r[i+8] );
	for ( i = 1; i <= 8; ++i )
		addEdge( i+16, i, r[i]-ans );
	for ( i = 1; i <= 24; ++i )
		addEdge( i-1, i, 0 );
	for ( i = 1; i <= 24; ++i )
		addEdge( i, i-1, -t[i] );
	 //这句感觉应该是addEdge( 24, 0, -ans ),即S24-S0<=ans,但是错了,也许题目中“Note that there can be 
         //more cashiers than the least number needed for a specific slot. ”是一个提醒吧。。。
	addEdge( 0, 24, ans );
}

int main()
{
	int cases, m, i, x;
	scanf( "%d", &cases );
	while ( cases-- )
	{
		memset( t, 0, sizeof( t ) );
		for ( i = 1; i <= 24; ++i )
			scanf( "%d", &r[i] );
		scanf( "%d", &m );
		for ( i = 0; i < m; ++i )
		{
			scanf( "%d", &x );
			t[x+1]++;
		}
		for ( ans = 0; ans <= m; ++ans )
		{
			ConstructGraph();
			if ( spfa( 25, 0 ) ) break;
		}
		if ( ans <= m )
			printf( "%d\n", ans );
		else
			printf( "No Solution\n");
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee