50分 TLE求救
查看原帖
50分 TLE求救
617078
zhouyuxuan3501楼主2024/8/31 20:57
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

struct I{int W,s,L;double C;}c[21000];
int n,m,k[210],N[210],s=1,S1,S2;
double D[210];
bool r[210],z[210][210];
queue<int> q;
bool spfa()
{
	memcpy(N,k,sizeof k);
	int i,l,h;
	for(i=0;i<=S2;i++)D[i]=-1;
	q.push(S1);
	D[S1]=1.0;
	while(!q.empty())
	{
		l=q.front();
		q.pop();
		r[l]=0;
		for(i=k[l];i;i=c[i].s)
		{
			h=c[i].W;
			if(c[i].L>0&&D[h]<D[l]*c[i].C)
			{
				D[h]=D[l]*c[i].C;
				if(!r[h])
				{
					r[h]=1;
					q.push(h);
				}
			}
		}
	}
	return D[S2]>0;
}
int dfs(int l=S1,int H=2e9)
{
	if(l==S2||H==0)return H;
	int i,h,w,P=H;
	r[l]=1;
	for(i=N[l];i&&P;i=c[i].s)
	{
		N[l]=i;
		h=c[i].W;
		if(c[i].L>0&&(!r[h])&&abs(D[h]-D[l]*c[i].C)<1e-6)
		{
			w=dfs(h,min(P,c[i].L));
			c[i].L-=w;
			c[i^1].L+=w;
			P-=w;
		}
	}
	r[l]=0;
	return H-P;
}
int main()
{
	auto J=[&](int j,int h,int w,double C)
	{
		s++;
		c[s].W=h;
		c[s].s=k[j];
		c[s].L=w;
		c[s].C=C;
		k[j]=s;
	};
	int i,j,h;
	scanf("%d%d",&n,&m);
	S1=n+m+1;
	S2=S1+1;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			scanf("%d",&h);
			if(h)
			{
				J(i,j+n,1,h*0.01);
				J(j+n,i,0,100.0/h);
			}
		}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&h);
		J(S1,i,h,1);
		J(i,S1,0,1);
	}
	for(j=1;j<=m;j++)
	{
		scanf("%d",&h);
		J(j+n,S2,h,1);
		J(S2,j+n,0,1);
	}
	while(spfa())dfs();
	for(i=1;i<=n;i++)
		for(j=k[i];j;j=c[j].s)
			if(!c[j].L)
				z[i][c[j].W-n]=1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)printf("%d",z[i][j]);
		puts("");
	}
	return 0;
}
2024/8/31 20:57
加载中...