求助!70分!
查看原帖
求助!70分!
375249
xianman楼主2021/9/5 20:28
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
typedef long long ll;
//typedef pair<int,int> P;
using namespace std;
const int N = 50000+9;
const ll inf = 1e15;
struct edge{
	ll to,cap,cost,rev;
};
ll V;
vector<edge> G[N];
ll dist[N];
ll h[N];
ll prevv[N],preve[N];
void add_edge(ll from,ll to,ll cap,ll cost){
	edge ed;
	ed.to = to;ed.cap = cap;ed.cost = cost;ed.rev = G[to].size();
	G[from].push_back(ed);
	ed.to = from;ed.cap = 0;ed.cost = -cost;ed.rev = G[from].size() - 1;
	G[to].push_back(ed);
	return ;
}
ll min_cost_flow(ll s,ll t,ll f){
	ll res = 0;
	fill(h,h + V,0);
	while(f > 0){
		priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > que;
		fill(dist,dist + V,inf);
		dist[s] = 0;
		que.push(pair<ll,ll>(0,s));
		while(!que.empty()){
			pair<ll,ll> p = que.top();que.pop();
			ll v = p.second;
			if(dist[v] < p.first) continue;
			for(int i = 0;i < G[v].size();i++){
				edge &e = G[v][i];
				if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(pair<ll,ll>(dist[e.to],e.to));
				}
			}
		}
		if(dist[t] == inf){
			return -1;
		}
		for(int v = 0;v < V;v++) h[v] += dist[v];
		ll d = f;
		for(int v = t;v != s;v = prevv[v]){
			d = min(d,G[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for(int v = t;v != s;v = prevv[v]){
			edge &e = G[prevv[v]][preve[v]];
			e.cap -= d;
			G[v][e.rev].cap += d;
		}
	}
	return res;
}

int cnt = 0;
int n,m;
inline int findin(int x,int y){
	return (x-1)*m+y;
}
inline int findout(int x,int y){
	return n*m+((x-1)*m+y);
}
int d[60][60] = {0};
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			scanf("%d",&d[i][j]);
		}
	}
	int s,t;
	s = 0;
	t = 2 * n * m + 1;
	add_edge(s,1,2,0);
	add_edge(findout(n,m),t,2,0);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			int in = findin(i,j);
			int out = findout(i,j);
			add_edge(in,out,2,-d[i][j]);
			if(i + 1 <= n){
				add_edge(out,findin(i+1,j),1,0);
			}
			if(j + 1 <= m){
				add_edge(out,findin(i,j+1),1,0);
			}
		}
	}
	ll ans = 0;
	V = 2 * n * m + 2;
	ans = -min_cost_flow(s,t,2);
	printf("%lld",ans);
	return 0;
}

2021/9/5 20:28
加载中...