【网络流24题】餐巾计划问题

标签：费用流

Solution

由于每天餐厅需要 \(r_i\) 份餐巾，产生 \(r_i\) 份需清洗餐巾，考虑将每天拆成两个点 \(X_i\) 与 \(Y_i\) ，其中 \(X_i\) 需要向汇点 \(T\) 汇入 \(r_i\) 份餐巾，\(Y_i\) 向 \(X_j\) 汇入清洗过的餐巾。

从源点 \(S\) 向 \(X_i\) 连一条容量无限，单位费用为 \(p\) 的边，表示购买餐巾；向 \(Y_i\) 连一条容量为 \(r_i\)，单位费用为 \(0\) 的边，表示该天用过的餐巾。

此外，\(Y_i\) 向 \(Y_{i+1}\) 连一条容量无限，单位费用为 \(0\) 的边，表示延期清洗餐巾；分别向 \(X_{i+m}\)，\(X_{i+n}\) 连容量无限，单位费用分别为 \(f\)，\(p\) 的边，表示快洗与慢洗餐巾。

最后跑一边最小费用最大流即可。

Code

#include
#define M 4005
using namespace std;
typedef long long ll;
typedef double db;
char IO;
int rd(){
	int num=0;bool f=0;
	while(IO=getchar(),IO<48||IO>57)if(IO=='-')f=1;
	do num=(num<<1)+(num<<3)+(IO^48);
	while(IO=getchar(),IO>=48&&IO<=57);
	return f?-num:num;
}
bool f2;
int n,m,S,T;
int to[M*12],nxt[M*12],hd[M],cnte=1;
ll val[M*12],cost[M*12];
void Adde(int u,int v,ll w,ll c){
	to[++cnte]=v;val[cnte]=w;cost[cnte]=c;
	nxt[cnte]=hd[u];hd[u]=cnte;
}
void Add(int u,int v,ll w,ll c){
	Adde(u,v,w,c);Adde(v,u,0,-c);
}
ll dep[M];
int cur[M];
bool vis[M];
queue Q;
bool SPFA(){
	memset(dep,63,sizeof(dep));
	memcpy(cur,hd,sizeof(cur));
	dep[S]=1;Q.push(S);
	int u,v;
	while(!Q.empty()){
		u=Q.front();Q.pop();
		vis[u]=0;
		for(int i=hd[u];i;i=nxt[i]){
			v=to[i];
			if(val[i]&&dep[u]+cost[i]0){
			val[i]-=f;val[i^1]+=f;
			res+=f;flow-=f;
			micost+=f*cost[i];
		}
	}
	vis[u]=0;
	return res;
}
ll C[M];
bool f1;
int main(){
//	cout<<1.0*(&f1-&f2)/1024.0/1024.0<