「雅礼集训 2018 Day8」B

Posted on Edited on In

「雅礼集训 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);
}