P1646 T飞了求助
  • 板块题目总版
  • 楼主Ptilopsis_
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/2/5 14:18
  • 上次更新2025/2/5 17:15:47
查看原帖
P1646 T飞了求助
524994
Ptilopsis_楼主2025/2/5 14:18
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
const int inf=1e9;
struct edge
{
	int v,w,flow,rev;
};
int n,m,s,t,cnt,sum,dep[N],cur[N];
vector<edge> a[N];
int id(int x,int y)
{
	return (x-1)*n+y;
}
void add_edge(int u,int v,int w)
{
	a[u].push_back({v,w,0,a[v].size()});
	a[v].push_back({u,0,0,a[u].size()-1});
}
bool bfs(int s,int t)
{
	queue<int> q;
	memset(dep,-1,sizeof(dep));
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<a[u].size();i++)
		{
			int v=a[u][i].v,w=a[u][i].w,flow=a[u][i].flow;
			if(dep[v]==-1&&w>flow)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]!=-1;
}
int dfs(int u,int t,int mxflow)
{
	if(u==t)
		return mxflow;
	int ret=0;
	for(int &i=cur[u];i<a[u].size();i++)
	{
		int v=a[u][i].v,w=a[u][i].w,flow=a[u][i].flow,rev=a[u][i].rev;
		if(dep[v]!=dep[u]+1)
			continue;
		int f=dfs(v,t,min(mxflow-ret,w-flow));
		ret+=f;
		a[u][i].flow+=f;
		a[v][rev].flow-=f;
		if(ret==mxflow) 
			return ret;
	}
	return ret;
}
int dinic()
{
	int ret=0;
	while(bfs(s,t))
	{
		memset(cur,0,sizeof(cur));
		ret+=dfs(s,t,inf);
	}
	return ret;
}
int main()
{
	cin>>n>>m;
	s=0,t=N-1;
	int u;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>u;
			sum+=u;
			add_edge(s,id(i,j),u);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>u;
			sum+=u;
			add_edge(id(i,j),t,u);
		}
	}
	for(int i=1;i<=n-1;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>u;
			sum+=u;
			add_edge(s,++cnt,u);
			add_edge(cnt,id(i,j),inf);
			add_edge(cnt,id(i+1,j),inf);
		}
	}
	for(int i=1;i<=n-1;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>u;
			sum+=u;
			add_edge(++cnt,t,u);
			add_edge(id(i,j),cnt,inf);
			add_edge(id(i+1,j),cnt,inf);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m-1;j++)
		{
			cin>>u;
			sum+=u;
			add_edge(s,++cnt,u);
			add_edge(cnt,id(i,j),inf);
			add_edge(cnt,id(i,j+1),inf);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m-1;j++)
		{
			cin>>u;
			sum+=u;
			add_edge(++cnt,t,u);
			add_edge(id(i,j),cnt,inf);
			add_edge(id(i,j+1),cnt,inf);
		}
	}
	cout<<sum-dinic()<<endl;
}
2025/2/5 14:18
加载中...