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