题目链接: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$$
这显然是上下界网络流的形式了,行列建边,判断可行流即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 */ |
Comments | 1 条评论
太强啦