样例过了 wa15 猫娘求主
  • 板块P4313 文理分科
  • 楼主AndyC
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/18 12:31
  • 上次更新2024/8/18 15:25:35
查看原帖
样例过了 wa15 猫娘求主
366430
AndyC楼主2024/8/18 12:31
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long inf=2005020600;
inline int read(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}return x*f;}
int n,s,t,u,v;
int w,ans,dis[520010];
int tot=1,now[520010],head[520010]; 
int f,d;
struct node {
	int to,net;
	long long val;
} e[520010];

void add(int u,int v,long long w) {
	e[++tot].to=v;
	e[tot].val=w;
	e[tot].net=head[u];
	head[u]=tot;
}

int bfs() {  //在惨量网络中构造分层图 
	for(int i=s;i<=n;i++) dis[i]=inf;
//	memset(dis,inf,sizeof(dis));
	queue<int> q; while(!q.empty()) q.pop();
	q.push(s);
	dis[s]=1;
	now[s]=head[s];
	while(!q.empty()) {
		int x=q.front(); q.pop();
		for(int i=head[x];i;i=e[i].net) {
			int v=e[i].to;
			if(e[i].val>0&&dis[v]==inf) {
				q.push(v);
				now[v]=head[v];
				dis[v]=dis[x]+1;
//				if(v==t) return 1;
			}
		}
	}
	if(dis[t]==inf) return false;
	return true;
}

inline int dfs(int x,long long sum) {  //sum是整条增广路对最大流的贡献
	if(x==t) return sum;
	long long k,res=0;  //k是当前最小的剩余容量 
	for(int i=now[x];i&&sum;i=e[i].net) {
		now[x]=i;  //当前弧优化 
		int v=e[i].to;
		if(e[i].val>0&&(dis[v]==dis[x]+1)) {
			k=dfs(v,min(sum,e[i].val));
			if(k==0) dis[v]=inf;  //剪枝,去掉增广完毕的点 
			e[i].val-=k;
			e[i^1].val+=k;
			res+=k;  //res表示经过该点的所有流量和(相当于流出的总量) 
			sum-=k;  //sum表示经过该点的剩余流量 
		}
	}
	return res;
}

void dinic(){
//	cout<<"D";
	while(bfs()) {
//		cout<<"F";
		ans+=dfs(s,inf);  //流量守恒(流入=流出) 
//		cout<<ans<<endl;
	}
}
int N,M,sum;
bool check(int x,int y){
	if(x<1||x>N||y<1||y>M) return false;
	return true;
}

int art[102][102],science[102][102],same_art[102][102],same_science[102][102];
signed main() {
	N=read(),M=read();
	n=N*M;
	s=1,t=N*M+1;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			art[i][j]=read();
			sum+=art[i][j];
			int A=(i-1)*M+j;
			add(s,A,art[i][j]);
			add(A,s,0);
		} 
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			science[i][j]=read();
			sum+=science[i][j];
			int A=(i-1)*M+j;
			add(A,t,science[i][j]);
			add(t,A,0);
		} 
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			same_art[i][j]=read();
			int A=(i-1)*M+j;
			sum+=same_art[i][j];
			add(s,++n,same_art[i][j]);
			add(n,s,0);
			add(n,A,0x3f3f3f3f);
			add(A,n,0);
			if(check(i,j-1)){
				int B=(i-1)*M+j-1;
				add(n,B,0x3f3f3f3f);
				add(B,n,0);
			}
			if(check(i,j+1)){
				int B=(i-1)*M+j+1;
				add(n,B,0x3f3f3f3f);
				add(B,n,0);
			}
			if(check(i-1,j)){
				int B=(i-2)*M+j;
				add(n,B,0x3f3f3f3f);
				add(B,n,0);
			}
			if(check(i+1,j)){
				int B=(i)*M+j-1;
				add(n,B,0x3f3f3f3f);
				add(B,n,0);
			}
		} 
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			same_science[i][j]=read();
			sum+=same_science[i][j];
			add(++n,t,same_science[i][j]);
			add(t,n,0);
			int A=(i-1)*M+j;
			add(A,n,0x3f3f3f3f);
			add(n,A,0);
			if(check(i,j-1)){
				int B=(i-1)*M+j-1;
				add(B,n,0x3f3f3f3f);
				add(n,B,0);
			}
			if(check(i,j+1)){
				int B=(i-1)*M+j+1;
				add(B,n,0x3f3f3f3f);
				add(n,B,0);
			}
			if(check(i+1,j)){
				int B=(i)*M+j;
				add(B,n,0x3f3f3f3f);
				add(n,B,0);
			}
			if(check(i-1,j)){
				int B=(i-2)*M+j;
				add(B,n,0x3f3f3f3f);
				add(n,B,0);
			}
		} 
	}
	dinic();
	cout<<sum-ans<<endl;
	return 0;
}
2024/8/18 12:31
加载中...