求助-玄学问题
查看原帖
求助-玄学问题
921364
123456xwd楼主2024/7/4 11:54

我把一个点拆成了两个 s−u−u′−ts-u-u'-t,s−us-u 表示选择文科,边权为收益,u′tu'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;	
}

为啥啊?

2024/7/4 11:54
加载中...