「雅礼集训 2018 Day8」B

Solution1

设到达一个点的时间为$T_u$，从这个点出去的时间为$T_u’$

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

对于一条边满足$T_v\ge T’_u$，二分答案之后，容易发现这是一个线性规划问题

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

Loj Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#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\n",res);
}

Solution2

二分答案$\text{lim}$，问题转化为求最小花费

设每个点减少了$x_i$

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

$\text{minimize:} \sum x_i\cdot c_i$

$\displaystyle \forall p\in paths , \sum x_{p_i}\ge \sum t_{p_i}-\text{lim}$

$-x_i\ge -t_i$

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

$\text{maximize}:\sum y_p\cdot (\sum t_{p_i}-\text{lim})-z_i\cdot t_i$

$\displaystyle \forall i\in[1,n], \sum_{p\in paths,i\in p} y_p-z_i\leq c$

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

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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\n",res);
}