WA10pts求助
查看原帖
WA10pts求助
160839
Prean楼主2021/2/26 14:01

RT,样例过了,求助/kel

#include<cstring>
#include<cstdio>
#include<queue>
const int M=605;
int n,m,s,t,ans,cnt=1,h[M],d[M],cur[M];bool vis[M];
struct Edge{
	int to,nx,val,flow;
}e[M*120];
std::queue<int>q;
inline int min(const int&a,const int&b){
	return a>b?b:a;
}
inline void Add(const int&u,const int&v,const int&val,const int&flow){
	e[++cnt]=(Edge){v,h[u],val,flow};h[u]=cnt;
	e[++cnt]=(Edge){u,h[v],-val,0};h[v]=cnt;
}
bool SPFA(){
	int u,v,E;
	memset(d,0x3f,sizeof d);memcpy(cur,h,sizeof h);
	q.push(s);vis[s]=true;d[s]=0;
	while(!q.empty()){
		vis[u=q.front()]=false;q.pop();
		for(E=h[u];E;E=e[E].nx){
			v=e[E].to;
			if(d[u]+e[E].val<d[v])if(e[E].flow){
				d[v]=d[u]+e[E].val;
				if(!vis[v])q.push(v),vis[v]=true;
			}
		}
	}
	return d[t]^0x3f3f3f3f;
}
int DFS(int u,int flow){
	if(!flow)return 0;
	if(u==t)return flow;
	int v,f,res=flow;vis[u]=true;
	for(int&E=cur[u];E;E=e[E].nx)if(e[E].flow){
		v=e[E].to;
		if(!vis[v]&&d[u]+e[E].val==d[v]){
			f=DFS(v,min(e[E].flow,res));
			res-=f;e[E].flow-=f;e[E^1].flow+=f;
			if(!f)d[v]=-0x3f3f3f3f;
			if(!res)return vis[u]=false,flow;
		}
	}
	return vis[u]=false,cur[u]=h[u],flow-res;
}
inline int Solve(){
	int ans=0;
	while(SPFA()){
		while(int f=DFS(s,0x3f3f3f3f))ans+=d[t]*f;
	}
	return ans;
}
signed main(){
	register int i,j,k,val;
	scanf("%d%d",&m,&n);s=0;t=n*(m+1)+1;
	for(i=1;i<=n;++i){
		Add(0,i,0,1);
		for(j=1;j<=m;++j){
			scanf("%d",&val);Add(i*m+j,t,0,1);
			for(k=1;k<=n;++k)Add(i,j*n+k,val*k,1);
		}
	}
	printf("%.2lf",1.0*Solve()/n);
}
2021/2/26 14:01
加载中...