BZOJ.4819.[SDOI2017]新生舞会(01分数规划 费用流SPFA)

时间：2023-03-09 08:02:57
BZOJ.4819.[SDOI2017]新生舞会(01分数规划 费用流SPFA)

BZOJ

洛谷

裸01分数规划。二分之后就是裸最大费用最大流了。

写的朴素SPFA费用流，洛谷跑的非常快啊，为什么有人还T成那样。。

当然用二分也很慢，用什么什么迭代会很快。

[Update] 19.2.15

下午写的zkw费用流在BZOJ上T了= =

然而在洛谷上和以前写的跑的差不多快

当然还可以写整数二分或者KM...

输出的时候最好加个eps，不然可以被卡比如BZOJ discuss里的数据。

第一次写的代码：

//3624kb	4016ms

#include <queue>

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

#define eps 1e-7

#define INF 1e14

const int N=205,M=90000;

int n,src,des,Enum,H[N],to[M],fr[M],nxt[M],cap[M],pre[N];

bool inq[N];

double Ans,dis[N],A[N][N],B[N][N],cost[M];

std::queue<int> q;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline void AddEdge(int u,int v,int w,double c)

{

	to[++Enum]=v, nxt[Enum]=H[u], fr[Enum]=u, H[u]=Enum, cap[Enum]=w, cost[Enum]=c;

	to[++Enum]=u, nxt[Enum]=H[v], fr[Enum]=v, H[v]=Enum, cap[Enum]=0, cost[Enum]=-c;

}

bool SPFA()

{

	for(int i=1; i<=des; ++i) dis[i]=-INF;

	q.push(src), dis[src]=0;

	while(!q.empty())

	{

		int x=q.front();q.pop();

		inq[x]=0;

		for(int v,i=H[x]; i; i=nxt[i])

			if(dis[to[i]]<dis[x]+cost[i] && cap[i])

			{

				dis[v=to[i]]=dis[x]+cost[i], pre[v]=i;

				if(!inq[v]) inq[v]=1,q.push(v);

			}

	}

	return dis[des]>-INF;

}

void MCMF(){

	for(int i=des; i!=src; i=fr[pre[i]])

		--cap[pre[i]], ++cap[pre[i]^1], Ans+=cost[pre[i]];

}

bool pre_Check(double C)

{

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j)

			/*if(i!=j) j是女生，不是自己。。*/

			AddEdge(i,j+n,1,A[i][j]-C*B[i][j]);

	for(int i=1; i<=n; ++i) AddEdge(src,i,1,0),AddEdge(i+n,des,1,0);

	Ans=0;

	while(SPFA()){

		MCMF();

		if(Ans<0) break;

	}

	return Ans>=0;

}

bool Check(double C)

{

	int cnt=1;

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j)

			cap[++cnt]=1, cost[cnt]=A[i][j]-C*B[i][j], cap[++cnt]=0, cost[cnt]=-A[i][j]+C*B[i][j];

	for(int i=1; i<=n; ++i)

		cap[++cnt]=1, cost[cnt]=0, cap[++cnt]=0, cost[cnt]=0,

		cap[++cnt]=1, cost[cnt]=0, cap[++cnt]=0, cost[cnt]=0;

	Ans=0;

	while(SPFA()){

		MCMF();

		if(Ans<0) break;

	}

	return Ans>=0;

}

int main()

{

	n=read(),Enum=1,src=0,des=n<<1|1;

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j) A[i][j]=read();

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j) B[i][j]=read();

	double l=0,r=10000.0,mid;

	if(pre_Check(mid=(l+r)*0.5)) l=mid;

	else r=mid;

	while(r>l+eps)

		if(Check(mid=(l+r)*0.5)) l=mid;

		else r=mid;

	printf("%.6lf",l+eps);

	return 0;

}

第二次写的代码：（BZOJ上T掉的zkw= =）

#include <queue>

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define eps 1e-7

#define gc() getchar()

typedef long long LL;

const int N=207,M=(N*N+N)*2;

const double INF=1ll<<61;

int T,Enum,cur[N],H[N],to[M],nxt[M],cap[M],A[103][103],B[103][103];

bool vis[N];

double Cost,cost[M],dis[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-48,c=gc());

	return now;

}

inline void AE(int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;

}

void PreBuild(int n)

{

	Enum=1;

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j) AE(i,j+n);

	for(int i=1; i<=n; ++i) AE(0,i), AE(i+n,T);

}

bool BFS()

{

	static bool inq[N];

	static std::queue<int> q;

	for(int i=1; i<=T; ++i) dis[i]=-INF;

	q.push(0), dis[0]=0;

	while(!q.empty())

	{

		int x=q.front(); q.pop();

		inq[x]=0;

		for(int i=H[x],v; i; i=nxt[i])

			if(dis[v=to[i]]<dis[x]+cost[i] && cap[i])

				dis[v]=dis[x]+cost[i], !inq[v]&&(q.push(v),inq[v]=1);

	}

	return dis[T]>-INF;

}

bool DFS(int x)

{

	if(x==T) return 1;

	vis[x]=1;//!!

	for(int &i=cur[x]; i; i=nxt[i])

		if(!vis[to[i]] && cap[i] && dis[to[i]]==dis[x]+cost[i] && DFS(to[i]))

			return --cap[i], ++cap[i^1], Cost+=cost[i], 1;

	return 0;

}

bool MCMF()

{

	Cost=0;

	while(BFS())

	{

		memset(vis,0,T+1), memcpy(cur,H,T+1<<2);

		while(DFS(0) && Cost>=0);

		if(Cost<0) break;

	}

	return Cost>=0;

}

bool Check(int n,double x)

{

	int now=1;

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j)

			cap[++now]=1, cost[now]=A[i][j]-x*B[i][j], cap[++now]=0, cost[now]=-cost[now-1];

	for(int i=1; i<=n; ++i) cap[++now]=1, cap[++now]=0, cap[++now]=1, cap[++now]=0;

	return MCMF();

}

int main()

{

	freopen("ball.in","r",stdin);

	freopen("ball.out","w",stdout);

	int n=read(); T=n+n+1;

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j) A[i][j]=read();

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=n; ++j) B[i][j]=read();

	PreBuild(n);

	double l=0,r=1e4+1e-4,mid;

	while(l+eps<r)

		if(Check(n,mid=(l+r)*0.5)) l=mid;

		else r=mid;

	printf("%.6lf\n",l+eps);

	return 0;

}

相关文章