个人网站制作手机版,网站开发新闻怎么写,互联网保险产品有哪些,上海有哪些外贸进出口公司题目描述 输入输出格式 输入格式#xff1a; 第一行两个数n、m#xff0c;表示矩阵的大小。 接下来n行#xff0c;每行m列#xff0c;描述矩阵A。 最后一行两个数L#xff0c;R。 输出格式#xff1a; 第一行#xff0c;输出最小的答案#xff1b; 输入输出样例 输入样…题目描述 输入输出格式 输入格式 第一行两个数n、m表示矩阵的大小。 接下来n行每行m列描述矩阵A。 最后一行两个数LR。 输出格式 第一行输出最小的答案 输入输出样例 输入样例#1 2 2
0 1
2 1
0 1 输出样例#1 1 说明 对于100%的数据满足N,M200,0LR1000,0A_{ij}Aij1000 题解 这题的转换实在是太TM的神奇了首先题目要求的其实是最大值最小那么我们可以二分将其转换为判断性问题乍一看这个式子一脸懵逼再乍一看其实就是要我们“最小化每行每列所有元素与给定矩阵差的和的绝对值中的最大值”然后先设h[i]为第i行的和l[i]为第i列的和那么如果要满足二分出来的mid那么一定要满足B矩阵的第i行总和为[r[i]-mid,midr[i]]同列的话也是一样的那么我们就可以把每列每行的看成一个点原点向每个行点连边上下界为[r[i]-mid,midr[i]]列点向汇点连边上下界为[c[i]-mid,midc[i]]然后行列之间连边上下界为[L,R]这样的话问题就可以转换为是否存在二分图中是否存在一个可行流那么跑一遍上下界网络流就好了代码 1 #include cstdio2 #include iostream3 #include cstring4 #include queue5 #include algorithm6 using namespace std;7 const int N510;8 const int inf0x3f3f3f3f;9 int n,m,cnt,s,t,S,T,head[N],dis[N],cur[N],d[N],h[N],l[N],L,R,num[N][N];
10 struct edge{int to,from,v;}e[N*N*2];
11 queueint Q;
12 void insert(int x,int y,int v)
13 {
14 e[cnt].toy,e[cnt].fromhead[x],e[cnt].vv,head[x]cnt;
15 e[cnt].tox,e[cnt].fromhead[y],e[cnt].v0,head[y]cnt;
16 }
17 int dfs(int x,int maxf)
18 {
19 if (xT||!maxf) return maxf;
20 int ret0;
21 for (int icur[x];i;ie[i].from)
22 if (e[i].vdis[e[i].to]dis[x]1)
23 {
24 int fdfs(e[i].to,min(e[i].v,maxf-ret));
25 e[i].v-f,e[i^1].vf,retf;
26 if (maxfret) break;
27 }
28 return ret;
29 }
30 bool bfs()
31 {
32 for (int is;iT;i) dis[i]0;
33 while (!Q.empty()) Q.pop();
34 dis[S]1,Q.push(S);
35 while (!Q.empty())
36 {
37 int uQ.front(); Q.pop();
38 for (int ihead[u];i;ie[i].from)
39 if (e[i].v!dis[e[i].to])
40 {
41 dis[e[i].to]dis[u]1;
42 if (e[i].toT) return 1;
43 Q.push(e[i].to);
44 }
45 }
46 return 0;
47 }
48 int dinic()
49 {
50 int ans0;
51 while (bfs())
52 {
53 for (int i0;iT;i) cur[i]head[i];
54 ansdfs(S,inf);
55 }
56 return ans;
57 }
58 bool check(int x)
59 {
60 cnt1,memset(d,0,sizeof(d)),memset(head,0,sizeof(head)),s0,tnm1,Snm2,Tnm3;
61 insert(t,s,inf);
62 for (int i1;in;i)
63 for (int j1;jm;j)
64 insert(i,jn,R-L),d[i]-L,d[jn]L,num[i][j]cnt;
65 for (int i1;in;i)
66 {
67 int pmax(0,h[i]-x),qxh[i];
68 insert(s,i,q-p),d[s]-p,d[i]p;
69 }
70 for (int i1;im;i)
71 {
72 int pmax(0,l[i]-x),qxl[i];
73 insert(in,t,q-p),d[in]-p,d[t]p;
74 }
75 int tot0;
76 for (int is;it;i) if (d[i]0) insert(S,i,d[i]),totd[i]; else if (d[i]0) insert(i,T,-d[i]);
77 return dinic()tot;
78 }
79 int main()
80 {
81 scanf(%d%d,n,m);
82 for (int i1,x;in;i) for (int j1;jm;j) scanf(%d,x),h[i]x,l[j]x;
83 scanf(%d%d,L,R);
84 int l0,r200000;
85 while (lr)
86 {
87 int midlr1;
88 if (check(mid)) rmid-1; else lmid1;
89 }
90 printf(%d,r1);
91 } 转载于:https://www.cnblogs.com/Comfortable/p/10304186.html
