救救孩子吧
查看原帖
救救孩子吧
167279
Danno0v0楼主2021/11/10 21:44

很诡异的是300WA但是100T掉了?

还是说这道题不能用纯费用流?

#include<bits/stdc++.h>
using namespace std;
#define maxx 2000001
#define S 1999999
#define T 2000000
#define opst 1000000
int fi[maxx],nx[maxx],to[maxx],val[maxx],co[maxx],pre[maxx],min_flow[maxx],in[maxx],dis[maxx],tot=1;
int min_cost,max_flow;
int L[1001][1001];
void link(int a,int b,int c,int d)
{
	nx[++tot]=fi[a];
	fi[a]=tot;
	to[tot]=b;
	val[tot]=c;
	co[tot]=d;
	nx[++tot]=fi[b];
	fi[b]=tot;
	to[tot]=a;
	val[tot]=0;
	co[tot]=-d;
}
bool spfa()
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	queue<int>que;
	que.push(S);
	min_flow[S]=0x7ffffff;
	in[S]=1;
	dis[S]=0;
	while(!que.empty())
	{
		int x=que.front();
		que.pop();
		in[x]=0;
		for(int i=fi[x];i;i=nx[i])
		{
			int v=to[i];
			if(dis[x]+co[i]<dis[v]&&val[i])
			{
				dis[v]=dis[x]+co[i];
				pre[v]=i;
				min_flow[v]=min(min_flow[x],val[i]);
				if(!in[v])
				{
					in[v]=1;
					que.push(v);
				}
			}
		}
	}
	return dis[T]<0x3f3f3f3f;
}
void ek()
{
	while(spfa())
	{
		min_cost+=dis[T]*min_flow[T];
		max_flow+=min_flow[T];
		int x=T;
		while(x!=S)
		{
			int i=pre[x];
			val[i]-=min_flow[T];
			val[i^1]+=min_flow[T];
			x=to[i^1];	
		}
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>L[i][j];
			link(S,i*1000+j,1,0);
			link(i*1000+j+opst,T,1,0);
		}
	}
	int k;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>k;
			for(int s=L[i][j];s<=k;s++)
			{
				for(int r=0;r<m;r++)
				{
					link(i*1000+j,s*1000+r+opst,1,2*(abs(s-i))+min(abs(j-r),m-abs(j-r)));
				}
			}
		}
	}
	ek();
	if(max_flow!=n*m)
	{
		cout<<"no solution";
	}
	else
	{
		cout<<min_cost<<endl;
	}
}
2021/11/10 21:44
加载中...