题目链接:https://cn.vjudge.net/contest/281959#problem/E
建图真真完全没搞懂,,照着题解不知道咋回事就过了。。。
不想看了留坑开学后再说吧
参考题解:https://www.cnblogs.com/hongyj/p/8646446.html
https://blog.csdn.net/qq_33229466/article/details/70159372
#include <iostream> #include <bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; struct node { int next,to,dis; }edge[600030]; int head[100010],cur[100010],deep[100010]; int n,m,cnt=2,maxflow; int nextt[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; ///核心代码无需改动--start void addedge(int from,int to,int dis) { edge[cnt].to=to; edge[cnt].dis=dis; edge[cnt].next=head[from]; head[from]=cnt++; edge[cnt].to=from; edge[cnt].dis=0; edge[cnt].next=head[to]; head[to]=cnt++; } bool bfs(int s,int t) { memset(deep,0,sizeof(deep)); queue<int>q; while(!q.empty()) q.pop(); memcpy(cur,head,sizeof(head)); deep[s]=1; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=edge[i].next) { if(!deep[edge[i].to]&&edge[i].dis) { deep[edge[i].to]=deep[now]+1; q.push(edge[i].to); } } } return deep[t]; } int dfs(int now,int t,int limit) { if(!limit||now==t) return limit; int flow=0; for(int i=cur[now];i!=-1;i=edge[i].next) { if(edge[i].dis&&deep[edge[i].to]==deep[now]+1) { int d=dfs(edge[i].to,t,min(limit,edge[i].dis)); flow+=d; limit-=d; edge[i].dis-=d; edge[i^1].dis+=d; } } if(!flow)deep[now]=0; return flow; } void dinic(int s,int t) { while(bfs(s,t)) maxflow+=dfs(s,t,inf); } ///核心代码--end int hashh[111][111],tot=0,mp[111][111]; int main() { ios::sync_with_stdio(false); memset(head,-1,sizeof(head)); int summ=0; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { hashh[i][j]=++tot; cin>>mp[i][j]; } } cnt=2; int s,t; s=0; t=tot*2+1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(mp[i][j]<0) { int mx=0; int tx=i,ty=j; int op=-mp[i][j]-1; while(1) { tx+=nextt[op][0]; ty+=nextt[op][1]; if(tx>n||ty>m||!tx||!ty) break; mx=max(mx,mp[tx][ty]); } summ+=mx; if(op<2) addedge(s,hashh[i][j],inf); else addedge(tot+hashh[i][j],t,inf); tx=i; ty=j; while(1) { int lp=tx,lq=ty; tx+=nextt[op][0]; ty+=nextt[op][1]; if(tx>n||ty>m||!tx||!ty) break; if(op<2)addedge(hashh[lp][lq],hashh[tx][ty],mx-max(0,mp[lp][lq])); else addedge(hashh[tx][ty]+tot,hashh[lp][lq]+tot,mx-max(mp[lp][lq],0)); } } else addedge(hashh[i][j],tot+hashh[i][j],inf); } } maxflow=0; dinic(s,t); cout<<summ-maxflow<<endl; return 0; }