poj1275差分约束

设num[i]  为在i时刻可以工作的应聘人数

x[i]  在i时刻招聘的人数

m[i] 在i时刻要求最少的工作人数

由题意建立起约束：

(1)0 <= x[i] <= num[i]

(2)x[i-7] + x[i-6 ]+.....+ x[i] >= m[i] (因为工作8小时) (i<7时要特殊考虑)

设s[i] = x[1] + x[2] + .....+ x[i]  从第0时刻到第i时刻招聘的总人数

将约束转化为 差分形式:

由(1):

s[i] - s[i-1] >= 0  1 <= i <= 24  ( 第i时刻可能不招人)

s[i-1] - s[i] >= -num[i]    1 <= i <= 24 

由(2):

s[i] - s[i-8] >= m[i]  9 <= i <= 24 (不受一天的影响)

s[i] - s[i+16] >= m[i] - s[24] 1 <= i <= 8 (受上一天的影响)

特加条件: s[24] - s[0] >= ans 

不妨假设s[24]为ans,以0点为源点跑最长路有解,且s[24]=ans。说明此解有效。

所以最长路作为二分搜索的判断条件。搜索可行解。

#include 
#include 
#include 
#include 
#include 
#define MAX_N 25
#define INF 0x7fffffff
using namespace std;
struct edge{int to,val;
};
bool inque[MAX_N];
int dist[MAX_N];
int vis[MAX_N];
int s[MAX_N];
int num[MAX_N];
int m[MAX_N];
vector g[MAX_N];
int init()
{for(int i=0;i= 0// s[i-1] – s[i] >= –num[i]// s[i] – s[i-8] >= r[i], 9 <= i <= 24// s[i] – s[i+16] >= r[i] – s[24],  1<= i <= 8// s[24] – s[0] >= ansfor(int i=1;i<=24;++i)add_edge(i-1,i,0);for(int i=1;i<=24;++i)add_edge(i,i-1,-num[i]);for(int i=9;i<=24;++i)add_edge(i-8,i,m[i]);for(int i=1;i<=8;++i)add_edge(i+16,i,m[i]-ans);add_edge(0,24,ans);
}
bool spfa(int start,int res)
{queue que;for(int i=0;iMAX_N) return false;for(int i=0;i=1){int mid=(rb+lb)/2;init();bulidGraph(mid);if(spfa(0,mid))rb=mid;else lb=mid+1;}return rb;
}
int main()
{int t;scanf("%d",&t);while(t--){for(int i=1;i<=24;++i)scanf("%d",&m[i]);int n;memset(num,0,sizeof(n));scanf("%d",&n);int u,rb=0;for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！