弱爆了，典型的行列建模方式，居然想不到，题做少了，总结少了。。。。。。
二分答案mid
s----------------------->i行----------------------->j列----------------------------->t
[si-mid,si+mid] [L,R] [s[j]-mid,s[j]+mid]
即对每一行建一个点,每一列建一个点,用边来表示某一行某一列上的东西.
这种建模方式一般要整体考虑行或列的某些信息.
/**************************************************************
Problem: 2406
User: idy002
Language: C++
Result: Accepted
Time:396 ms
Memory:4576 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#define min(a,b) ((a)<(b)?(a):(b))
#define oo 0x3f3f3f3f
#define N 510
#define S 100010 struct Dinic {
int n, src, dst;
int head[N], dest[S], flow[S], next[S], etot;
int dep[N], cur[N], qu[N], bg, ed; void init( int n, int src, int dst ) {
memset( head, -, sizeof(head) );
etot = ;
this->n = n;
this->src = src;
this->dst = dst;
}
void adde( int u, int v, int f ) {
// fprintf( stderr, "Dinic::adde( %d %d %d )\n", u, v, f );
next[etot]=head[u]; flow[etot]=f; dest[etot]=v; head[u]=etot++;
next[etot]=head[v]; flow[etot]=; dest[etot]=u; head[v]=etot++;
}
bool bfs() {
memset( dep, , sizeof(dep) );
qu[bg=ed=] = src;
dep[src] = ;
while( bg<=ed ) {
int u=qu[bg++];
for( int t=head[u]; ~t; t=next[t] ) {
int v=dest[t], f=flow[t];
if( f && !dep[v] ) {
dep[v] = dep[u]+;
qu[++ed] = v;
}
}
}
return dep[dst];
}
int dfs( int u, int a ) {
if( u==dst || a== ) return a;
int remain=a, past=, na;
for( int &t=cur[u]; ~t; t=next[t] ) {
int v=dest[t], &f=flow[t], &vf=flow[t^];
if( f && dep[v]==dep[u]+ && (na=dfs(v,min(remain,f))) ) {
f -= na;
vf += na;
remain -= na;
past += na;
if( !remain ) break;
}
}
return past;
}
int maxflow() {
int f = ;
while( bfs() ) {
for( int u=; u<=n; u++ ) cur[u]=head[u];
f += dfs( src, oo );
}
// fprintf( stderr, "maxflow() = %d\n", f );
return f;
}
};
struct TopBot {
int n;
int head[N], dest[S], top[S], bot[S], next[S], etot;
int sin[N], sout[N];
Dinic D;
void init( int n ) {
this->n = n;
etot = ;
memset( head, , sizeof(head) );
memset( sin, , sizeof(sin) );
memset( sout, , sizeof(sout) );
}
void adde( int u, int v, int t, int b ) {
// fprintf( stderr, "TopBot::adde( %d %d [%d,%d] )\n", u, v, b, t );
etot++;
dest[etot] = v;
top[etot] = t;
bot[etot] = b;
next[etot] = head[u];
head[u] = etot;
sin[v] += b;
sout[u] += b;
}
bool ok() {
int src=n+, dst=n+;
D.init( n+, src, dst );
for( int u=; u<=n; u++ )
for( int t=head[u]; t; t=next[t] ) {
int v=dest[t];
D.adde( u, v, top[t]-bot[t] );
}
int sumf = ;
for( int u=; u<=n; u++ ) {
if( sin[u]>sout[u] )
D.adde( src, u, sin[u]-sout[u] );
else if( sin[u]<sout[u] ) {
D.adde( u, dst, sout[u]-sin[u] );
sumf += sout[u]-sin[u];
}
}
// fprintf( stderr, "sumf=%d\n", sumf );
return D.maxflow()==sumf;
}
}T; int n, m;
int w[N][N], L, R;
int s[][N]; bool ok( int mid ) {
int src = n+m+, dst = n+m+;
int st=, sb=;
T.init(dst);
for( int i=; i<=n; i++ ) {
int t=s[][i]+mid, b=s[][i]-mid;
b = b< ? : b;
T.adde( src, i, t, b );
st += t;
sb += b;
}
for( int i=; i<=n; i++ )
for( int j=; j<=m; j++ )
T.adde( i, n+j, R, L );
for( int i=; i<=m; i++ ) {
int t=s[][i]+mid, b=s[][i]-mid;
b = b< ? : b;
T.adde( n+i, dst, t, b );
}
T.adde( dst, src, st, sb );
return T.ok();
}
int main() {
scanf( "%d%d", &n, &m );
for( int i=; i<=n; i++ )
for( int j=; j<=m; j++ ) {
scanf( "%d", &w[i][j] );
s[][i] += w[i][j];
s[][j] += w[i][j];
}
scanf( "%d%d", &L, &R );
int lf=, rg=;
while( lf<rg ) {
int mid=lf+((rg-lf)>>);
if( ok(mid) ) rg=mid;
else lf=mid+;
}
printf( "%d\n", lf );
}