「雅礼集训 2018 Day8」B

Solution1

设到达一个点的时间为(T_u)，从这个点出去的时间为(T_u')

那么显然满足(T_uleq T_u'leq T_u+t_u)，答案就是(sum (t_u-(T'_u-T_u))cdot c_u)

对于一条边满足(T_vge T'_u)，二分答案之后，容易发现这是一个线性规划问题

可以暴力单纯形解决掉(当然是水的，但是好像还挺快。。)

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=630,P=1e9+7;
const db eps=1e-9;

int n,m,W,t[N],c[N];
int U[N],V[N];
db A[N][N];


db Simplex(int n){
	srand(time(NULL));
	auto Pivot=[&](int x,int y) {
		static int P[N],C;
		rep(i,0,n) A[y][i]=-A[x][i]/A[x][y];
		A[y][x]=1/A[x][y],A[y][y]=0;
		rep(i,0,n) A[x][i]=0;
		C=0;
		rep(i,0,n) if(abs(A[y][i])>eps) P[++C]=i;
		rep(i,0,n) if(abs(A[i][y])>eps) {
			db t=A[i][y]; A[i][y]=0;
			rep(j,1,C) A[i][P[j]]+=t*A[y][P[j]];
		}
	};
	vector <int> V;
	rep(i,1,n) V.pb(i);
	//random_shuffle(V.begin(),V.end());
	while(1) {
		int u=0,v=0;
		for(int i:V) if(!u || A[i][0]<A[u][0]) u=i;
		if(A[u][0]>-eps) break;
		for(int i:V) if(A[u][i]>eps) v=i;
		if(!v) return puts("Infeasible"),0;
		Pivot(u,v);
	}

	while(1) {
		int u=0,v=0;
		for(int i:V) if(!v || A[0][i]>A[0][v]) v=i;
		if(A[0][v]<eps) break;
		for(int i:V) if(A[i][v]<-eps) if(!u || (A[i][0]/A[i][v] > A[u][0]/A[u][v])) u=i;
		if(!u) return puts("Unbounded"),0; 
		Pivot(u,v); 
	}
	return A[0][0];
}
int outd[N];
int Check(int lim) {
	memset(A,0,sizeof A);
	int cnt=n*2;
	rep(i,1,n) A[0][i+n]=c[i],A[0][i]=-c[i],A[0][0]-=t[i]*c[i];
	rep(i,1,n) {
		A[++cnt][i]=-1; A[cnt][i+n]=1;
		A[++cnt][i]=1; A[cnt][i+n]=-1; A[cnt][0]=t[i];
	}
	rep(i,1,m) A[++cnt][U[i]+n]=-1,A[cnt][V[i]]=1;
	rep(i,1,n) if(!outd[i]) A[++cnt][0]=lim,A[cnt][i+n]=-1;
	db res=-Simplex(cnt);
	return res<=W+eps;
}

int main(){
	freopen("soft.in","r",stdin),freopen("soft.out","w",stdout);
	n=rd(),m=rd(),W=rd();
	int l=0,r=0,res=-1;
	rep(i,1,n) t[i]=rd(),r+=t[i];
	rep(i,1,n) c[i]=rd();
	rep(i,1,m) U[i]=rd(),V[i]=rd(),outd[U[i]]++;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(Check(mid)) r=mid-1,res=mid;
		else l=mid+1;
	}
	printf("%d
",res);
}

[ ]

Solution2

二分答案( ext{lim})，问题转化为求最小花费

设每个点减少了(x_i)

考虑限制有两种，一种是路径长度的限制，一种是每个点大小的限制

( ext{minimize:} sum x_icdot c_i)

(displaystyle forall pin paths , sum x_{p_i}ge sum t_{p_i}- ext{lim})

(-x_ige -t_i)

对偶一下，设对于路径(p)，(sum x_{p_i})的对偶变量为(y_p)，(-x_i)的对偶变量为(z_i)

( ext{maximize}:sum y_pcdot (sum t_{p_i}- ext{lim})-z_icdot t_i)

(displaystyle forall iin[1,n], sum_{pin paths,iin p} y_p-z_ileq c)

考虑对偶变量(y_p)和(z_i)有什么意义

此时，选择一条路径(y_p)，会使得关于路径上的点的限制+1 ，使得答案增加(sum t_{p_i}- ext{lim})

(z_i)是关于每个单点的变量，可以用(t_i)代价使得每个(i)的限制-1

那么可以考虑转化为一个路径覆盖问题，选择一条路径覆盖路径上的点，且得到(sum t_{p_i}- ext{lim})的价值

限制式子转化为：每个点被覆盖次数大于(c)时，再选择就要付出(t_i)的代价令(z_i)加一

带权的路径覆盖容易转化为费用流模型，可以把每个点拆成入点出点，每个点被覆盖前(c_i)次，价值为(t_i)，之后就为0

因此每个点的入点向出点连((c_i,t_i),(infty,0))两条边即可，路径的( ext{-lim})可以在源点前加入

求一次最大费用可行流，最终得到的答案是原问题的最小代价

~~是我EK写得太丑的说~~: Loj Submission

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

enum{N=10101,INF=1<<30};

int n,m,W;
int c[N],t[N],X[N],Y[N];
struct Edge{
	int to,nxt,w,c;
} e[N];
int head[N],ecnt=1;
int V,S,T;
void AddEdge(int u,int v,int w,int c){ e[++ecnt]=(Edge){v,head[u],w,c},head[u]=ecnt; }
void Link(int u,int v,int w,int c){ AddEdge(u,v,w,c),AddEdge(v,u,0,-c); }

int pre[N],dis[N],inq[N];
int SPFA(int lim){
	rep(i,1,V) dis[i]=-INF;
	static queue <int> que;
	dis[S]=-lim,que.push(S);
	while(!que.empty()) {
		int u=que.front(); que.pop(),inq[u]=0;
		for(int i=head[u];i;i=e[i].nxt) {
			int v=e[i].to;
			if(!e[i].w || dis[v]>=dis[u]+e[i].c) continue;
			dis[v]=dis[u]+e[i].c,pre[v]=i;
			if(!inq[v]) que.push(v),inq[v]=1;
		}
	}
	return dis[T]>0;
}

int Check(int lim){
	S=++V,T=++V;
	rep(i,1,n) {
		Link(S,++V,INF,0);
		Link(V,V+1,c[i],t[i]);
		Link(V,V+1,INF,0);
		Link(++V,T,INF,0);
	}
	rep(i,1,m) Link(X[i]*2+2,Y[i]*2+1,INF,0);
	int ans=0;
	while(SPFA(lim)){
		int w=INF;
		for(int i=T;i!=S;i=e[pre[i]^1].to) cmin(w,e[pre[i]].w);
		for(int i=T;i!=S;i=e[pre[i]^1].to) e[pre[i]].w-=w,e[pre[i]^1].w+=w;
		ans+=dis[T]*w;
	}
	rep(i,1,V) head[i]=0;
	ecnt=1,V=0;
	return ans<=W;
}

int main(){
	freopen("soft.in","r",stdin),freopen("soft.out","w",stdout);
	n=rd(),m=rd(),W=rd();
	int l=0,r=0,res=-1;
	rep(i,1,n) r+=t[i]=rd();
	rep(i,1,n) c[i]=rd();
	rep(i,1,m) X[i]=rd(),Y[i]=rd();
	for(int mid;l<=r;) Check(mid=(l+r)>>1)?r=mid-1,res=mid:l=mid+1;
	printf("%d
",res);
}