我把一个点拆成了两个 s−u−u′−t,s−u 表示选择文科,边权为收益,u′t 表示选择理科,边权为收益。
在处理相邻的情况时,有两种连边方式,一种只有50,另外一个AC
AC:
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int rd(){
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=8e4+5,M=N*15,INF=1e9;
int n,m,s,t;
struct node{
int to,nt,val;
}a[M<<3];
int head[N<<2],at=1;
void add(int u,int v,int w){
a[++at].nt=head[u],head[u]=at,a[at].val=w,a[at].to=v;
}
void Add(int u,int v,int w){
add(u,v,w);
add(v,u,0);
}
int now[N<<2],deep[N<<2];
bool bfs(){
for(int i=1;i<=t;i++) deep[i]=0,now[i]=head[i];
queue<int> q;int u,v,w;
q.push(s);deep[s]=1;
while(!q.empty()){
u=q.front();q.pop();
for(int i=head[u];i;i=a[i].nt){
v=a[i].to,w=a[i].val;
if(!deep[v]&&w){
deep[v]=deep[u]+1;
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dfs(int u,int flow){
if(u==t||!flow) return flow;
int v,w,tmp=0;
for(int i=now[u];i;i=a[i].nt){
v=a[i].to,w=a[i].val,now[u]=i;
if(deep[v]==deep[u]+1&&w){
int k=dfs(v,min(w,flow-tmp));
if(!k) deep[v]=0;
tmp+=k,a[i].val-=k,a[i^1].val+=k;
if(flow==tmp) break;
}
}
return tmp;
}
int Dinic(){
int ans=0;
while(bfs()) ans+=dfs(s,INF);
return ans;
}
int S(int k,int i,int j){
return k*n*m+(i-1)*m+j;
}
bool check(int i,int j){
if(i<1||j<1||i>n||j>m) return 0;
return 1;
}
int X[5]={0,-1,1,0,0};
int Y[5]={0,0,0,-1,1};
signed main(){
int sum=0,x;
n=rd(),m=rd();
s=n*m*4+1;t=s+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(s,S(0,i,j),x);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(S(1,i,j),t,x);
Add(S(0,i,j),S(1,i,j),INF);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(s,S(2,i,j),x);
for(int k=0;k<=4;k++){
int ii=i+X[k],jj=j+Y[k];
if(check(ii,jj)) Add(S(2,i,j),S(0,ii,jj),INF);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(S(3,i,j),t,x);
for(int k=0;k<=4;k++){
int ii=i+X[k],jj=j+Y[k];
if(check(ii,jj)) Add(S(1,ii,jj),S(3,i,j),INF);
}
}
}
printf("%lld\n",sum-Dinic());
return 0;
}
50:
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int rd(){
int x=0,f=1; char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
const int N=8e4+5,M=N*15,INF=1e9;
int n,m,s,t;
struct node{
int to,nt,val;
}a[M<<3];
int head[N<<2],at=1;
void add(int u,int v,int w){
a[++at].nt=head[u],head[u]=at,a[at].val=w,a[at].to=v;
}
void Add(int u,int v,int w){
add(u,v,w);
add(v,u,0);
}
int now[N<<2],deep[N<<2];
bool bfs(){
for(int i=1;i<=t;i++) deep[i]=0,now[i]=head[i];
queue<int> q;int u,v,w;
q.push(s);deep[s]=1;
while(!q.empty()){
u=q.front();q.pop();
for(int i=head[u];i;i=a[i].nt){
v=a[i].to,w=a[i].val;
if(!deep[v]&&w){
deep[v]=deep[u]+1;
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dfs(int u,int flow){
if(u==t||!flow) return flow;
int v,w,tmp=0;
for(int i=now[u];i;i=a[i].nt){
v=a[i].to,w=a[i].val,now[u]=i;
if(deep[v]==deep[u]+1&&w){
int k=dfs(v,min(w,flow-tmp));
if(!k) deep[v]=0;
tmp+=k,a[i].val-=k,a[i^1].val+=k;
if(flow==tmp) break;
}
}
return tmp;
}
int Dinic(){
int ans=0;
while(bfs()) ans+=dfs(s,INF);
return ans;
}
int S(int k,int i,int j){
return k*n*m+(i-1)*m+j;
}
bool check(int i,int j){
if(i<1||j<1||i>n||j>m) return 0;
return 1;
}
int X[5]={0,-1,1,0,0};
int Y[5]={0,0,0,-1,1};
signed main(){
int sum=0,x;
n=rd(),m=rd();
s=n*m*4+1;t=s+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(s,S(0,i,j),x);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(S(1,i,j),t,x);
Add(S(0,i,j),S(1,i,j),INF);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(s,S(2,i,j),x);
for(int k=0;k<=4;k++){
int ii=i+X[k],jj=j+Y[k];
if(check(ii,jj)) Add(S(2,i,j),S(1,ii,jj),INF); //1变为0
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=rd(),sum+=x;
Add(S(3,i,j),t,x);
for(int k=0;k<=4;k++){
int ii=i+X[k],jj=j+Y[k];
if(check(ii,jj)) Add(S(0,ii,jj),S(3,i,j),INF); //0变为1
}
}
}
printf("%lld\n",sum-Dinic());
return 0;
}
为啥啊?