BZOJ 3280 小R的烦恼

需要充分利用题目性质的一道好题。

由于题目数据范围较小，同时情况复杂限制条件多，我们考虑使用网络流来描述这个问题。

显然，每天都会有 (a_i) 个研究生进入濒死状态，因此，我们可以采用提前计算的方法钦定每天都会有 (a_i) 个研究生进入救治。因此，我们为每天建立一个点，为每天单独建立一个点，从原点往这样一个点连接容量为当天新产生濒死研究生数量，同时从这点往之后的天数连边，表示有些研究生通过医院在那些天复活了，同时限定费用。

我们把每天往汇点连接需要研究生数量条边，我们要求每条边满流。

因此，我们从原点往第一天连边，由于只要买了一个研究生那他就永远属于你了，那不如在第一天就买好，同时从每一天往下一天连边。

正确性显然能保证。

代码如下：

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

template <typename T>
void read(T &x) {
	T f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
	while(s>='0'&&s<='9') {x=(x<<3)+(x<<1)+(s^'0');s=getchar();}
	x *= f;
} 

const int MAXN = 1e6 + 5;
const int MAXM = 1e6 + 6;
const int inf = 1e15;

int head[MAXN] , to[MAXM << 1] , nxt[MAXM << 1] , edge[MAXM << 1] , val[MAXM << 1] , cnt = 1;
void add(int u , int v , int c , int w) {
	nxt[++cnt] = head[u];head[u] = cnt;to[cnt] = v;edge[cnt] = c;val[cnt] = w;
	nxt[++cnt] = head[v];head[v] = cnt;to[cnt] = u;edge[cnt] = 0;val[cnt] = -w;
} 

int s , t , pre[MAXN] , las[MAXN] , dis[MAXN] , flow[MAXN] , vis[MAXN] , num;

struct MinCostMaxFlow {
	int MaxFlow , MinCost;
	bool bfs() {
		queue <int> q;
		q.push(s);
		int flag = 0;
		while(!q.empty()) {
			int x = q.front();
			q.pop();
			vis[x] = 0;
			for (int i = head[x]; i; i = nxt[i]) {
				int v = to[i];
				if(!edge[i]) continue;
				if(dis[v] > dis[x] + val[i]) {
					las[v] = i;
					pre[v] = x;
					dis[v] = dis[x] + val[i];
					flow[v] = min(flow[x] , edge[i]);
					if(v == t) {
						flag = 1;
						continue;
					}
					if(!vis[v]) q.push(v) , vis[v] = 1;
				}
			}
		}
		return flag;
	}
	
	void MVMC() {
		MinCost = MaxFlow = 0;
		for (int i = 1; i <= num; ++i) dis[i] = inf , vis[i] = 0 , flow[i] = 0;
		flow[s] = inf;
		dis[s] = 0;
		while(bfs()) {
			MinCost += flow[t] * dis[t];
			MaxFlow += flow[t];
			int now = t;
			while(now != s) {
				edge[las[now]] -= flow[t];
				edge[las[now] ^ 1] += flow[t];
				now = pre[now];
			}
			for (int i = 1; i <= num; ++i) dis[i] = inf , vis[i] = 0 , flow[i] = 0;
			flow[s] = inf;
			dis[s] = 0;
		}
	}
}MIN;


struct MaxCostMaxFlow {
	int MaxFlow , MaxCost;
	bool bfs() {
		queue <int> q;
		q.push(s);
		int flag = 0;
		while(!q.empty()) {
			int x = q.front();
			q.pop();
			vis[x] = 0;
			for (int i = head[x]; i; i = nxt[i]) {
				int v = to[i];
				if(!edge[i]) continue;
				if(dis[v] < dis[x] + val[i]) {
					las[v] = i;
					pre[v] = x;
					dis[v] = dis[x] + val[i];
					flow[v] = min(flow[x] , edge[i]);
					if(v == t) {
						flag = 1;
						continue;
					}
					if(!vis[v]) q.push(v) , vis[v] = 1;
				}
			}
		}
		return flag;
	}
	
	void MVMC() {
		MaxCost = MaxFlow = 0;
		for (int i = 1; i <= num; ++i) dis[i] = -inf , vis[i] = 0 , flow[i] = 0;
		flow[s] = inf;
		dis[s] = 0;
		while(bfs()) {
			MaxCost += flow[t] * dis[t];
			MaxFlow += flow[t];
			int now = t;
			while(now != s) {
				edge[las[now]] -= flow[t];
				edge[las[now] ^ 1] += flow[t];
				now = pre[now];
			}
			for (int i = 1; i <= num; ++i) dis[i] = -inf , vis[i] = 0 , flow[i] = 0;
			flow[s] = inf;
			dis[s] = 0;
		}
	}
}MAX;

int a[MAXN] , day[MAXN] , d[MAXN] , q[MAXN];

signed main() {
	int T , P = 0;
	read(T);
	while(T -- > 0) {
		int n , m , k;
		read(n),read(m),read(k);
		s = 1 , t = 2 , num = 2;
		int tot = 0;
		for (int i = 1; i <= n; ++i) {
			read(a[i]);
			day[i] = ++num;
			add(day[i] , t , a[i] , 0);
			tot += a[i];
		}
		for (int i = 2; i <= n; ++i) add(day[i - 1] , day[i] , inf , 0);
		for (int i = 1; i <= m; ++i) {
			int l , p;
			read(l),read(p);
			add(s , day[1] , l , p);
		}
		for (int i = 1; i <= k; ++i) read(d[i]),read(q[i]),d[i]++;
		for (int i = 1; i <= n; ++i) {
			++num;
			add(s , num , a[i] , 0);
			for (int j = 1; j <= k; ++j) {
				if(i + d[j] <= n) add(num , day[i + d[j]] , inf , q[j]);
			}
		}
		printf("Case %lld: " , ++P);
		MIN.MVMC();
		if(MIN.MaxFlow != tot) puts("impossible");
		else printf("%lld
" , MIN.MinCost);
		cnt = 1;
		for (int i = 1; i <= num; ++i) head[i] = 0;
	}
	
	return 0;
}