3
28
2016
1

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: 788
KBPE Question Paper 说:
Aug 29, 2022 06:18:39 PM SCERT Kerala Model Paper 2023 Pdf Download for Pareeksha Bhavan and Samagra Shiksha designed and suggested Model Question Bank or Question Pool for Theory, Objective (MCQ) and Bit Questions to 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (SSLC), 11 & 12 (+1 & +2) HSC Malayalam Medium & English Medium students. KBPE Question Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

登录 *


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