3
28
2016
0

Diary of March 28th

今天做了三道看过题解就是SB题的题
ZJOI DAY1T2做了一晚上
不开森

二分每头熊带多少货物
然后把每条边都除去这个值
那么每条边的权值就变成了最多能通过多少头熊
跑网络流验证一下就可以了
二分80次
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define eps 1e-9
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=55,M=505;
double L=0,R=0;
int cnt,to[M<<1],next[M<<1],cap[M<<1],Cap[M<<1],head[N];
void AddEdge(int u,int v,int w){
	to[cnt]=v;next[cnt]=head[u];Cap[cnt]=w;head[u]=cnt++;
	to[cnt]=u;next[cnt]=head[v];Cap[cnt]=0;head[v]=cnt++; 
}
int n,m,x,Tm[N],De[N],T,q[N],h,t;
bool BFS(){
	h=1,t=0;
	T++;
	Tm[1]=T,De[1]=1;
	q[++t]=1;
	while (h<=t){
		int u=q[h++];
		Cross(i,u) if (cap[i]!=0&&Tm[to[i]]<T){
			int v=to[i];
			Tm[v]=T;
			De[v]=De[u]+1;
			q[++t]=v;
		}
	}
	return Tm[n]==T;
}
int DFS(int u,int Flow){
	if (u==n||!Flow) return Flow;
	int ret=0,F;
	Cross(i,u){
		int v=to[i];
		if (De[v]==De[u]+1&&(F=DFS(v,min(Flow,cap[i])))){
			ret+=F,Flow-=F;
			cap[i]-=F,cap[i^1]+=F;
		}
	}
	return ret;
}
int Dinic(){
	T=0;
	int Flow=0;
	while (BFS()){
		int F=0;
		while (F=DFS(1,oo)) Flow+=F;
	}
	return Flow;
}
double Solve(){
	double l=1e-5,r=1e6;
	Rep(it,1,80){
		double mid=(l+r)/2;
		memset(Tm,0,sizeof Tm);
		Rep(i,0,cnt-1) cap[i]=min((int)(Cap[i]/mid),1000000);
		int f=Dinic();
		if (f>=x) l=mid;else r=mid;
	}
	return l;
}
int main(){
	n=IN(),m=IN(),x=IN();
	memset(head,-1,sizeof head);
	Rep(i,1,m){
		int u=IN(),v=IN(),w=IN();
		AddEdge(u,v,w);
	}
	printf("%.10lf\n",Solve()*x);
}
斜率优化DP
$DP_i$表示处理到第 $i$ 个为止,所有的任务的最小费用和
$T_i$ 和 $F_i$ 表示前缀和
$DP_i=min\{DP_j+(S+T_i-T_j)*(F_n-F_j)$
把 $DP_j+(S-T_j)*(F_n-F_j)$ 当做 $y$
把 $F_j-F_n$ 当做 $x$(没打错)
把 $T_i$ 当做 $k$,把 $DP_i$ 当做 $b$
$kx+b=y$,$x$ 递增,$k$ 不固定,
维护单调栈,每次二分就可以了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=300005;
int n,S;
ll T[N],F[N],Dp[N],Y[N],X[N];
long double GK(int a,int b){
	if (X[a]==X[b]){
		if (Y[a]>Y[b]) return 1e9;
		else return -1e9;
	}
	return (long double)(Y[a]-Y[b])/(X[a]-X[b]);
}
int Top,St[N];
int GetAns(long double K){
	if (Top==1) return St[1];
	if (GK(St[Top],St[Top-1])<K) return St[Top];
	int l=1,r=Top-1;
	while (l<r){
		int mid=l+r>>1;
		if (GK(St[mid+1],St[mid])<K) l=mid+1;
			else r=mid;
	}
	return St[l];
}
int main(){
	n=IN(),S=IN();
	Rep(i,1,n) T[i]=T[i-1]+IN(),F[i]=F[i-1]+IN();
	X[0]=-F[n],Y[0]=S*F[n];
	Top=0,St[++Top]=0;
	Rep(i,1,n){
		int Bt=GetAns(T[i]);
		Dp[i]=Y[Bt]-T[i]*X[Bt];
		X[i]=F[i]-F[n];
		Y[i]=Dp[i]+(S-T[i])*(F[n]-F[i]);
		while (Top>1&&GK(St[Top],St[Top-1])>=GK(i,St[Top])) Top--;
		St[++Top]=i;
	}
	OUT(Dp[n]);
}
分治
讲道理这是我第一次写堆优化的dijkstra
一开始用系统的优先队列狂WA不止 而且后面几个点又WA又T
然后就改成手写堆
然后卡卡常
一个晚上就过去了。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
#define y1 sdjfklajsdlkfs
#define y2 fsdafsdsdjfaskdls
#define ID(a,b) ((a-1)*m+b)
using namespace std;
#define S 100000
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,stdin),p2==p1)?-1:*p1++)
inline int IN(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=20005,Q=100005;
int n,m,q;
int Dt[N],Vs[N],Ans[Q],r[N],c[N];
struct Query{
	int x1,y1,x2,y2,id;
}a[Q],b[Q];
int min(int a,int b){return a<b?a:b;} 
int H[N<<2],Ps[N],Nm;
void PushDown(int Cur){
	int Zx=H[Cur],Ds=Dt[Zx];
	while ((Cur<<1)<=Nm){
		int Nx=Cur<<1;
		if (Nx<Nm&&Dt[H[Nx|1]]<Dt[H[Nx]]) Nx|=1;
		if (Dt[H[Nx]]<Ds){
			H[Cur]=H[Nx];
			Ps[H[Cur]]=Cur;
			Cur=Nx;
		}
		else break;
	}
	H[Cur]=Zx,Ps[Zx]=Cur;
}
void PushUp(int Cur){
	int Zx=H[Cur],Ds=Dt[Zx];
	while (Cur!=1&&Dt[H[Cur>>1]]>Ds){
		H[Cur]=H[Cur>>1];
		Ps[H[Cur]]=Cur;
		Cur>>=1;
	}
	H[Cur]=Zx,Ps[Zx]=Cur;
}
void Dijkstra(int sx,int sy,int x1,int x2,int y1,int y2){
	int s=ID(sx,sy);
	H[1]=s,Ps[s]=1;
	Nm=1;
	Rep(i,x1,x2) Rep(j,y1,y2){
		int Lt=ID(i,j);
		Vs[Lt]=0,Dt[Lt]=oo;
		if (Lt!=s){H[++Nm]=Lt;Ps[Lt]=Nm;}
	}
	Dt[s]=0;
	Drp(i,Nm,1){
		int u=H[1];H[1]=H[Nm--];PushDown(1);
		Vs[u]=1;
		int tx=(u-1)/m+1,ty=(u-1)%m+1,It=ID(tx,ty);
		if (tx>x1&&Dt[It]+c[It-m]<Dt[It-m]) Dt[It-m]=Dt[It]+c[It-m],PushUp(Ps[It-m]);
		if (ty>y1&&Dt[It]+r[It-1]<Dt[It-1]) Dt[It-1]=Dt[It]+r[It-1],PushUp(Ps[It-1]);
		if (tx<x2&&Dt[It]+c[It]<Dt[It+m]) Dt[It+m]=Dt[It]+c[It],PushUp(Ps[It+m]);
		if (ty<y2&&Dt[It]+r[It]<Dt[It+1]) Dt[It+1]=Dt[It]+r[It],PushUp(Ps[It+1]);
	}
}
void Solve(int x1,int x2,int y1,int y2,int l,int r){
	if (l>r) return;
	if (x2-x1>y2-y1){
		int mid=x1+x2>>1;
		Rep(i,y1,y2){
			Dijkstra(mid,i,x1,x2,y1,y2);
			Rep(j,l,r) Ans[a[j].id]=min(Ans[a[j].id],Dt[ID(a[j].x1,a[j].y1)]+Dt[ID(a[j].x2,a[j].y2)]);
		}
		int L=l-1,R=r+1;
		Rep(i,l,r){
			if (a[i].x1<mid&&a[i].x2<mid) b[++L]=a[i];
			if (a[i].x1>mid&&a[i].x2>mid) b[--R]=a[i];
		}
		Rep(i,l,L) a[i]=b[i];Solve(x1,mid-1,y1,y2,l,L);
		Rep(i,R,r) a[i]=b[i];Solve(mid+1,x2,y1,y2,R,r);
	}
	else{
		int mid=y1+y2>>1;
		Rep(i,x1,x2){
			Dijkstra(i,mid,x1,x2,y1,y2);
			Rep(j,l,r) Ans[a[j].id]=min(Ans[a[j].id],Dt[ID(a[j].x1,a[j].y1)]+Dt[ID(a[j].x2,a[j].y2)]);
		}
		int L=l-1,R=r+1;
		Rep(i,l,r){
			if (a[i].y1<mid&&a[i].y2<mid) b[++L]=a[i];
			if (a[i].y1>mid&&a[i].y2>mid) b[--R]=a[i];
		}
		Rep(i,l,L) a[i]=b[i];Solve(x1,x2,y1,mid-1,l,L);
		Rep(i,R,r) a[i]=b[i];Solve(x1,x2,mid+1,y2,R,r);
	}
}
int main(){
	n=IN(),m=IN();
	Rep(i,1,n) Rep(j,1,m-1) r[ID(i,j)]=IN();
	Rep(i,1,n-1) Rep(j,1,m) c[ID(i,j)]=IN();
	q=IN();
	Rep(i,1,q){
		a[i].x1=IN(),a[i].y1=IN(),a[i].x2=IN(),a[i].y2=IN();
		a[i].id=i;
	}
	memset(Ans,127,sizeof Ans);
	Solve(1,n,1,m,1,q);
	Rep(i,1,q) OUT(Ans[i]),putchar('\n');
}

 

Category: Diary | Tags: 分治 图论 网络流 DP 凸包 | Read Count: 223

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com