【过题记录】8.4(robocom补题，网络流)

其实就是一个求最大子矩阵和的板子题
利用最大子段和的思想
枚举矩阵中的上下界
压成一维后利用最大子段和$O(n)$处理
复杂度$O(n^3\ast k)$
k为执行次数

#include<bits/stdc++.h>
using namespace std;#define int long longconst int N = 5010;
int a[N][N];
int n;
int sum[N][N];
int maxn = 0;
int s[N][N],ss[N][N];
int tot = 0;
int stx,sty,edx,edy,xx,XX,yy,YY;
int cnt = 0;void Swap(){xx = sty; XX = edy; yy = stx; YY = edx;
} 
int ce =0 ;
bool Work(){for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){s[j][i] = s[j][i-1]+a[i][j];ss[j][i] = ss[j][i-1];if (a[i][j] == 0) ss[j][i]++; }int maxx = 0;xx = n+1; yy = n+1; XX = n+1; YY = n+1;for (stx = 1; stx <= n; stx++){for (edx = stx; edx <= n; edx++){int sum = 0;sty = 1;for (edy = 1; edy <= n; edy++){if (sum > maxx) Swap();int now = s[edy][edx]-s[edy][stx-1];int nowz = ss[edy][edx]-ss[edy][stx-1];if (nowz!=0){sty = edy+1;sum = 0;continue;}if (sum < 0){sum = 0;sty = edy;}sum+=now;if (sum > maxx) maxx = sum,Swap();if (sum == maxx){if (sty < xx) Swap();else if (sty == xx&&stx < yy) Swap();else if (sty == xx && stx == yy&&edy < XX) Swap();else if (sty == xx && stx == yy&&edy == XX && edx < YY) Swap();}}}}if (maxx == 0) return 0;tot+=maxx;printf("(%lld, %lld) (%lld, %lld) %lld\n",xx,yy,XX,YY,maxx);swap(xx,yy); swap(XX,YY);int delx = XX-xx+1;for (int i = xx-1; i >= 1; i--)for (int j = yy; j <= YY; j++)a[i+delx][j] = a[i][j];for (int i = 1; i <= delx; i++)for (int j = yy; j <= YY; j++) a[i][j] = 0;cnt++;bool f = 0;return 1;
}signed main(){cin>>n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){cin>>a[i][j];if (a[i][j] > 0) maxn+=a[i][j],ce++;}while (Work()); cout<<tot<<endl;
}

一道最大权值闭合图的板子题
按如下方式连边：

最大全职就是$sum-maxflow$
证明尚未完全理清
等我理清了来补

#include<bits/stdc++.h>
using namespace std;const int N = 7e3+100,inf = 1e9+7;
struct Node{int y,Next,v;
}e[2*N];
int len,Linkk[N];
int st,ed;void Insert(int x,int y,int v){e[++len] = (Node){y,Linkk[x],v};Linkk[x] = len;
}queue < int > q;
int d[N];bool bfs(){for (int i = 1; i <= ed; i++) d[i] = 0;while (q.size()) q.pop();d[st] = 1; q.push(st);while (q.size()){int x = q.front(); q.pop();for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v ||d[y]) continue;d[y] = d[x]+1; q.push(y);if (y == ed) return 1;}}return 0;
}int dinic(int x,int flow){if (x == ed) return flow;int re = flow , k;for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v || d[y] != d[x]+1) continue;k = dinic(y,min(re,e[i].v));if (!k) d[y] = 0;re-=k;e[i].v-=k; e[i^1].v+=k;}return flow-re;
}int n,m;
int main(){cin.tie(0);ios::sync_with_stdio(false);cin>>m>>n; len = 1;st = n+m+1; ed = n+m+2;int sum = 0;for (int i = 1; i <= m; i++){int v; cin>>v; sum+=v;Insert(st,i,v); Insert(i,st,0);int x;cin>>x;while (x){Insert(i,x+m,inf); Insert(x+m,i,0);cin>>x;}}for (int i = m+1,x; i <= m+n; i++)cin>>x,Insert(i,ed,x),Insert(ed,i,0);int flow;int maxf = 0;while (bfs())while (flow = dinic(st,inf)) maxf+=flow;cout<<sum-maxf<<endl;return 0;
}

与上体一样
所多的就是输出方案
这里最大流用的是dinic算法
如果最后对于一个点i，d[i]不为0，说明这个点在分层图中出现，并且用上了
那么就说明这个仪器用上了

#include<bits/stdc++.h>
using namespace std;const int N = 7e3+100,inf = 1e9+7;
struct Node{int y,Next,v;
}e[2*N];
int len,Linkk[N];
int st,ed;void Insert(int x,int y,int v){e[++len] = (Node){y,Linkk[x],v};Linkk[x] = len;
}queue < int > q;
int d[N];bool bfs(){for (int i = 1; i <= ed; i++) d[i] = 0;while (q.size()) q.pop();d[st] = 1; q.push(st);while (q.size()){int x = q.front(); q.pop();for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v ||d[y]) continue;d[y] = d[x]+1; q.push(y);if (y == ed) return 1;}}return 0;
}int dinic(int x,int flow){if (x == ed) return flow;int re = flow , k;for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v || d[y] != d[x]+1) continue;k = dinic(y,min(re,e[i].v));if (!k) d[y] = 0;re-=k;e[i].v-=k; e[i^1].v+=k;}return flow-re;
}int flag;
int re(){char c;int r=0;while (c<'0' || c>'9') c=getchar();while (c>='0' && c<='9'){r=r*10+c-'0';c=getchar();}if (c=='\r') flag=1;return r;
}int n,m;
int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);scanf("%d %d",&m,&n); len = 1;st = n+m+1; ed = n+m+2;int sum = 0;for (int i = 1; i <= m; i++){int v; scanf("%d",&v); sum+=v;Insert(st,i,v); Insert(i,st,0);int x; flag = 0;while (getchar() == ' '){scanf("%d",&x);Insert(i,x+m,inf); Insert(x+m,i,0); 
//			cout<<"x = "<<x<<endl; }}
//	cout<<"OK";for (int i = m+1,x; i <= m+n; i++)scanf("%d",&x),Insert(i,ed,x),Insert(ed,i,0);int flow;int maxf = 0;while (bfs())while (flow = dinic(st,inf)) maxf+=flow;for (int i = 1; i <= m; i++) if (d[i]) cout<<i<<' ';cout<<endl;for (int i = 1; i <= n; i++) if (d[i+m]) cout<<i<<' '; cout<<endl;cout<<sum-maxf<<endl;return 0;
}