BZOJ 2406 矩阵

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2406

题意：给一个矩阵 A，构造另一个元素都在 [l,r] 的矩阵 B，矩阵 C=A-B。记 t1=C 每一列的元素和的绝对值的最大值，t2=C 每一行的元素和的绝对值的最大值。记 T=max(t1,t2)，试构造矩阵 B 使得 T 最小。

我这题意简述的真是好啊...

最大值最小显然就是二分答案了，考虑 t2 的情况，合法的 mid 是这样的：

$$\left | \sum a_i-\sum b_i \right |\leq mid$$

即：

$$\sum a_i-mid\leq \sum b_i\leq \sum a_i+mid$$

这显然是上下界网络流的形式了，行列建边，判断可行流即可。

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 410
#define M 100010
#define ll long long
#define inf 1000000000
using namespace std;
inline int read() 
{ 
    int x=0,f=1;char ch=getchar(); 
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 
    return x*f; 
}
struct zgz
{
	int next,to,val;
}edge[M];
int cnt=2,head[N];
void add(int f,int t,int v)
{
	edge[cnt].to=t;
	edge[cnt].val=v;
	edge[cnt].next=head[f];
	head[f]=cnt++;
}
void ins(int f,int t,int v)
{add(f,t,v),add(t,f,0);}
int n,m,S,T,SS,TT;
int x[N],ans,ans_flow,tot_flow,tot_in,tot_out;
int sum_line[N],sum_row[N],L,R;
int a[N][N];
int d[N];
queue<int> q;
bool bfs()
{
	memset(d,0,sizeof(d));
	d[SS]=1,q.push(SS);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=edge[i].next)
		{
			int to=edge[i].to,val=edge[i].val;
			if(!d[to]&&val)
			{
				d[to]=d[x]+1;
				q.push(to);
			}
		}
	}
	return d[TT];
}
int dfs(int x,int v)
{
	if(x==TT||v==0)return v;
	int ret=0;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to,val=edge[i].val;
		if(d[to]==d[x]+1)
		{
			int f=dfs(to,min(val,v));
			edge[i].val-=f,edge[i^1].val+=f;
			v-=f,ret+=f;
			if(!v)break;
		}
	}
	if(!ret)d[x]=-1;
	return ret;
}
bool ck(int mid)
{
	ans_flow=0;tot_flow=0,tot_in=0,tot_out=0;
	cnt=2;memset(head,0,sizeof(head));
	memset(x,0,sizeof(x));
	for(int i=1;i<=n;i++)
	{
		ins(S,i,2*mid);
		x[S]-=sum_line[i]-mid;
		x[i]+=sum_line[i]-mid;
	}
	for(int i=1;i<=m;i++)
	{
		ins(n+i,T,2*mid);
		x[T]+=sum_row[i]-mid;
		x[n+i]-=sum_row[i]-mid;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		ins(i,n+j,R-L);
		x[i]-=L,x[n+j]+=L;
	}
	ins(T,S,inf);
	for(int i=S;i<=T;i++)
    {
        if(x[i]>0)ins(SS,i,x[i]),tot_in+=x[i];
        if(x[i]<0)ins(i,TT,-x[i]),tot_out-=x[i];
    }
    if(tot_in!=tot_out)return 0;
	while(bfs())ans_flow+=dfs(SS,inf);
	tot_flow=tot_in;
	if(ans_flow==tot_flow)return 1;
	return 0;
}
int main()
{
	n=read(),m=read();S=0,T=n+m+1,SS=T+1,TT=SS+1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		a[i][j]=read();
		sum_row[i]+=a[i][j];
		sum_line[j]+=a[i][j];
	}
	L=read(),R=read();
	int l=0,r=2000000;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(ck(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
}
/*
2 2 0 1 2 1 0 1
*/

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 410

#define M 100010

#define ll long long

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

struct zgz

{

int next,to,val;

}edge[M];

int cnt=2,head[N];

void add(int f,int t,int v)

{

edge[cnt].to=t;

edge[cnt].val=v;

edge[cnt].next=head[f];

head[f]=cnt++;

}

void ins(int f,int t,int v)

{add(f,t,v),add(t,f,0);}

int n,m,S,T,SS,TT;

int x[N],ans,ans_flow,tot_flow,tot_in,tot_out;

int sum_line[N],sum_row[N],L,R;

int a[N][N];

int d[N];

queue<int> q;

bool bfs()

{

memset(d,0,sizeof(d));

d[SS]=1,q.push(SS);

while(!q.empty())

{

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

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(!d[to]&&val)

{

d[to]=d[x]+1;

q.push(to);

}

return d[TT];

}

int dfs(int x,int v)

{

if(x==TT||v==0)return v;

int ret=0;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(d[to]==d[x]+1)

{

int f=dfs(to,min(val,v));

edge[i].val-=f,edge[i^1].val+=f;

v-=f,ret+=f;

if(!v)break;

}

if(!ret)d[x]=-1;

return ret;

}

bool ck(int mid)

{

ans_flow=0;tot_flow=0,tot_in=0,tot_out=0;

cnt=2;memset(head,0,sizeof(head));

memset(x,0,sizeof(x));

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

{

ins(S,i,2*mid);

x[S]-=sum_line[i]-mid;

x[i]+=sum_line[i]-mid;

}

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

{

ins(n+i,T,2*mid);

x[T]+=sum_row[i]-mid;

x[n+i]-=sum_row[i]-mid;

}

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

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

{

ins(i,n+j,R-L);

x[i]-=L,x[n+j]+=L;

}

ins(T,S,inf);

for(int i=S;i<=T;i++)

{

if(x[i]>0)ins(SS,i,x[i]),tot_in+=x[i];

if(x[i]<0)ins(i,TT,-x[i]),tot_out-=x[i];

}

if(tot_in!=tot_out)return 0;

while(bfs())ans_flow+=dfs(SS,inf);

tot_flow=tot_in;

if(ans_flow==tot_flow)return 1;

return 0;

}

int main()

{

n=read(),m=read();S=0,T=n+m+1,SS=T+1,TT=SS+1;

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

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

{

a[i][j]=read();

sum_row[i]+=a[i][j];

sum_line[j]+=a[i][j];

}

L=read(),R=read();

int l=0,r=2000000;

while(l<=r)

{

int mid=(l+r)>>1;

if(ck(mid))ans=mid,r=mid-1;

else l=mid+1;

}

printf("%d\n",ans);

}

2 2 0 1 2 1 0 1

zgz233

BZOJ 2406 矩阵

BZOJ 2055 80 人环游世界

BZOJ 4894 天赋

l1ll5

Comments | 1 条评论

feng, fengchang 博主

zgz233