shinzAnmono @ 2023-08-15 16:10:40
#include<iostream>
#include<algorithm>
#include<limits>
#include<queue>
using ll=long long;
const int sz=110;
const ll inf=std::numeric_limits<ll>::max();
struct edge{
int nxt,to;
ll w;
}graph[sz*sz<<3];
int head[sz*sz],chead[sz*sz],hpp=1;
void addEdge(int from,int to,ll w){
graph[++hpp]=edge{head[from],to,w};
head[from]=hpp;
}
int dep[sz],n,m,s,t;
bool bfs(){
std::queue<int>qq;
std::fill(dep,dep+n*m+2,0);
std::copy(head,head+n*m+2,chead);
qq.push(s),dep[s]=1;
while(!qq.empty()){
int u=qq.front();
qq.pop();
for(int p=head[u];p;p=graph[p].nxt){
int v=graph[p].to;
if(dep[v]==0&&graph[p].w!=0)qq.push(v),dep[v]=dep[u]+1;
}
}
return dep[t]!=0;
}
ll dfs(int u,ll lim){
if(u==t||lim==0)return lim;
ll arc=0,path=0;
for(int p=chead[u];p&&lim;p=graph[p].nxt){
chead[u]=p;
int v=graph[p].to;
if(dep[v]==dep[u]+1&&graph[p].w!=0){
arc=dfs(v,std::min(lim,graph[p].w));
path+=arc,lim-=arc;
graph[p].w-=arc,graph[p^1].w+=arc;
}
}
return path;
}
ll dinic(){
ll ans=0;
while(bfs())ans+=dfs(s,inf);
return ans;
}
int id[sz][sz],cpp,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin>>n>>m,t=n*m+1;
ll sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)id[i][j]=++cpp;
for(int i=1;i<=n;i++){
for(int j=1,k;j<=m;j++){
std::cin>>k,sum+=k;
if(i+j&1){
addEdge(0,id[i][j],k),addEdge(id[i][j],0,0);
for(int p=0;p<4;p++){
int x=i+dx[p],y=j+dy[p];
if(x<1||x>n||y<1||y>m)continue;
addEdge(id[i][j],id[x][y],inf),addEdge(id[x][y],id[i][j],0);
}
}else addEdge(id[i][j],t,k),addEdge(t,id[i][j],0);
}
}
std::cout<<sum-dinic()<<"\n";
return 0;
}by xjsmsms @ 2023-08-15 16:25:17
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#define int long long
#define rep(x, a, b) for(int x = (a); x <= (b); ++x)
#define rop(x, a, b) for(int x = (a); x < (b); ++x)
#define per(x, a, b) for(int x = (a); x >= (b); --x)
using namespace std;
typedef long long LL;
typedef double DB;
struct Queue {
int Que[16888], hd, tl, mo;
Queue() {mo = 16383; hd = tl = 0;}
void push(int x) {Que[tl & mo] = x; ++tl;}
void pop() {++hd;}
int front() {return Que[hd & mo];}
int size() {return tl - hd;}
void clear() {hd = tl = 0;}
}Q;
struct graph {
int hd[10005], vr[200005], vl[200005], nt[200005], tt;
int s, t, vs[10005], ds[10005], cr[10005];
void push(int x, int y, int z) {
vr[++tt] = y; vl[tt] = z; nt[tt] = hd[x]; hd[x] = tt;
}
int dfs(int nw, int mf) {
if(nw == t) return mf;
int RS = mf;
for(int &i = cr[nw]; i; i = nt[i]) {
if(vl[i] == 0 || ds[vr[i]] != ds[nw] + 1) continue;
int K = dfs(vr[i], min(RS, vl[i]));
vl[i] -= K;
vl[i ^ 1] += K;
RS -= K;
if(RS == 0) return mf;
}
return mf - RS;
}
bool bfs() {
memset(ds, 0x3f, sizeof(ds));
ds[s] = 0;
Q.push(s);
while(Q.size()) {
int nw = Q.front();
Q.pop();
for(int i = hd[nw]; i; i = nt[i]) {
if(vl[i] == 0 || ds[vr[i]] <= ds[nw] + 1) continue;
ds[vr[i]] = ds[nw] + 1;
Q.push(vr[i]);
}
}
return ds[t] != 0x3f3f3f3f;
}
long long dinic() {
long long F = 0;
int fl = 0;
while(bfs()) {
memcpy(cr, hd, sizeof(hd));
F += dfs(s, 0x3f3f3f3f);
}
return F;
}
}G;
int n, m, x, y, z, w;
signed main() {
scanf("%d%d%d%d", &n, &m, &G.s, &G.t);
G.tt = 1;
rep(i, 1, m) {
scanf("%d%d%d", &x, &y, &z);
G.push(x, y, z);
G.push(y, x, 0);
}
cout << G.dinic();
return 0;
}by xjsmsms @ 2023-08-15 16:25:54
《萌新》
by K8He @ 2023-08-15 16:28:50
据我所知 80% 以上 Dinic TLE 都是因为当前弧优化假了。
by xjsmsms @ 2023-08-15 16:31:57
@K8He 可能吧，本蒟蒻也是第一次写，哪里不对多多指正QWQ
by K8He @ 2023-08-15 16:32:42
@shinzanmono
for(int p=chead[u];p&&lim;p=graph[p].nxt){
chead[u]=p;
int v=graph[p].to;
if(dep[v]==dep[u]+1&&graph[p].w!=0){
arc=dfs(v,std::min(lim,graph[p].w));
path+=arc,lim-=arc;
graph[p].w-=arc,graph[p^1].w+=arc;
}
}改成：
for(int& p=chead[u];p;p=graph[p].nxt){
chead[u]=p;
int v=graph[p].to;
if(dep[v]==dep[u]+1&&graph[p].w!=0){
arc=dfs(v,std::min(lim,graph[p].w));
if(!arc)dep[v]=0;
path+=arc,lim-=arc;
graph[p].w-=arc,graph[p^1].w+=arc;
if(lim<=0)break;
}
}试试
by K8He @ 2023-08-15 16:33:55
@xuchengkun 你这个当前弧优化好像挺对的吧
by K8He @ 2023-08-15 16:34:58
if(!arc)dep[v]=0;是无用点优化，不是当前弧优化。忘了说了。
by K8He @ 2023-08-15 16:36:35
艹原来楼主早就过了
by shinzAnmono @ 2023-08-15 18:57:21
好了，其实是 dep 开小了/qd