ULR1 B. 【ULR #1】光伏元件

一个n∗nn∗n的0101矩阵ai,jai,j，有些位置可以修改，代价为ci,jci,j。要求进行一些修改之后满足：设clicli为第ii行的11的个数，cricri为第ii列的11的个数，要求cli,cri∈[dli,dri],|cli−cri|≤kicli,cri∈[dli,dri],|cli−cri|≤ki。

问最少代价。

保证有解。

n≤100n≤100

不错的网络流练习题。

建立两排点分别表示行列，两两连边表示一个格子。不可以修改显然，如果可以修改，ai,j=0ai,j=0时连(i,j′,0,1,ci,j)(i,j′,0,1,ci,j)，ai,j=1ai,j=1时先连(i,j′,1,1,0)(i,j′,1,1,0)，再连(j′,i,0,1,ci,j)(j′,i,0,1,ci,j)表示退流。

循序渐进思考，假设ki=0ki=0，也就是行列相同，那么可以连(i,i,0,∞,0)(i,i,0,∞,0)，求最小费用可行流。

扩展一下，可以这么连：建立源点汇点，连边(S,i,dl,dl+k,0),(i′,T,dl,dl+k,0),(i′,i,0,dr−dl−k,0)(S,i,dl,dl+k,0),(i′,T,dl,dl+k,0),(i′,i,0,dr−dl−k,0)。

从SS和i′i′流进ii的可以看做clicli，从i′i′流出到TT和ii的可以看做cricri。

可以发现一定满足cli,cri∈[dl,dr]cli,cri∈[dl,dr]。|cli−cri|=|(f(S,i)+f(i′,i))−(f(i′,T)+f(i′,i))|=|f(S,i)−f(i′,T)|≤k|cli−cri|=|(f(S,i)+f(i′,i))−(f(i′,T)+f(i′,i))|=|f(S,i)−f(i′,T)|≤k。

题解说如果用EK的话需要增广O(n2)O(n2)次，SPFA增广一次是O(nm)O(nm)所以是O(n5)O(n5)，用Dij增广一次是O(n2)O(n2)（不写堆优化）所以是O(n4)O(n4)。

习惯性地些了zkw费用流很自然地TLE80了，有时间去补一下Dij费用流。

下面的代码是80分的代码。

using namespace std;

#include <bits/stdc++.h>

#define N 105

#define ll long long

int n,all;

int S,T,ss,tt;

int a[N][N],c[N][N];

int dl[N],dr[N],dk[N];

struct EDGE{

	int to,c,w;

	EDGE *las;

} e[200005];

int ne;

EDGE *last[N*2];

void link(int u,int v,int c,int w){

//	printf("%d %d %d %d\n",u,v,c,w);

	e[ne]={v,c,w,last[u]};

	last[u]=e+ne++;

}

#define rev(ei) (e+(int((ei)-e)^1))

ll dis[N*2],maxflow,mincost;

bool vis[N*2];

ll dfs(int x,int s){

	if (x==tt){

		maxflow+=s;

		mincost+=s*dis[ss];

		return s;

	}

	int have=0;

	vis[x]=1;

	for (EDGE *ei=last[x];ei;ei=ei->las)

		if (ei->c && !vis[ei->to] && dis[x]==dis[ei->to]+ei->w){

			ll t=dfs(ei->to,min(ei->c,s-have));

			ei->c-=t,rev(ei)->c+=t,have+=t;

			if (have==s)

				return s;

		}

	return have;

}

bool change(){

	ll d=LLONG_MAX;

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

		if (vis[i])

			for (EDGE *ei=last[i];ei;ei=ei->las)

				if (ei->c && !vis[ei->to])

					d=min(d,dis[ei->to]+ei->w-dis[i]);

	if (d==LLONG_MAX)

		return 0;

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

		if (vis[i])

			dis[i]+=d;

	return 1;

}

void flow(){

	do

		do

			memset(vis,0,sizeof(bool)*(all+1));

		while (dfs(ss,INT_MAX));

	while (change());

}

void lk(int u,int v,int l,int r,int w){

	if (r-l)

		link(u,v,r-l,w),link(v,u,0,-w);

	if (l){

		link(ss,v,l,w),link(v,ss,0,-w);

		link(u,tt,l,0),link(tt,u,0,0);

	}

}

int ans[N][N];

void check(){

	ll sum=0;

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

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

			if (ans[i][j]!=a[i][j])

				sum+=c[i][j];

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

		int cl=0,cr=0;

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

			cl+=ans[i][j],cr+=ans[j][i];

		assert(cl<=dr[i] && cl>=dl[i]);

		assert(cr<=dr[i] && cr>=dl[i]);

		assert(abs(cl-cr)<=dk[i]);

	}

	assert(sum==mincost);

}

EDGE *p[N][N];

int main(){

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

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

	scanf("%d",&n);

	S=n+n+1,T=n+n+2,ss=n+n+3,tt=n+n+4;

	all=n+n+4;

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

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

			scanf("%d",&a[i][j]);

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

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

			scanf("%d",&c[i][j]);

			if (c[i][j]==-1){

				if (a[i][j]==1)

					lk(i,j+n,1,1,0);

			}

			else{

				if (a[i][j]==0){

					p[i][j]=e+ne;

					lk(i,j+n,0,1,c[i][j]);

				}

				else{

					lk(i,j+n,1,1,0);

					p[i][j]=e+ne+1;

					lk(j+n,i,0,1,c[i][j]);

//					link(j+n,i,1,c[i][j]);

//					link(i,j+n,0,-c[i][j]);

				}

			}

		}

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

		scanf("%d%d%d",&dl[i],&dr[i],&dk[i]);

		dk[i]=min(dk[i],dr[i]-dl[i]);

		lk(S,i,dl[i],dl[i]+dk[i],0);

		lk(i+n,T,dl[i],dl[i]+dk[i],0);

		lk(i+n,i,0,dr[i]-dl[i]-dk[i],0);

	}

	lk(T,S,0,INT_MAX,0);

	flow();

	printf("%lld\n",mincost);

	for (int i=1;i<=n;++i,printf("\n"))

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

			if (c[i][j]==-1)

				ans[i][j]=a[i][j];

			else

				ans[i][j]=rev(p[i][j])->c;

			printf("%d ",ans[i][j]);

		}

	check();

	return 0;

}

巴特西

ULR1 B. 【ULR #1】光伏元件

最新文章

热门文章