[网络流24题]数字梯形问题

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 512K, 提交时间: 2023-08-04 15:48:44

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

struct {
	int v,w,c,nxt;
}e[200010];
int head[200010],cnt=1;
int n,m,s,t;
int a[2100][2100],sum[2100][2010];
void add(int u,int v,int w,int c)
{
	e[++cnt]={v,w,c,head[u]};
	head[u]=cnt;
}

int pre[2100],dis[2100],inq[2100];
bool spfa()
{
	for(int i=s;i<=t;i++)
	{
		pre[i]=-1;
		dis[i]=-1e9;
		inq[i]=0;
	}

	queue<int>q;
	q.push(s);
	inq[s]=1;
	dis[s]=0;
	while(q.size())
	{
		//cout<<"sp\n";
		int u=q.front();
		q.pop();
		inq[u]=0;

		for(int i=head[u];i>0;i=e[i].nxt){
			int v=e[i].v,c=e[i].c;
			if(e[i].w>0&&dis[v]<dis[u]+c){
				dis[v]=dis[u]+c;
				pre[v]=i;
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dis[t]!=-1e9;
}

int mincost()
{
	int flow=0,cost=0;
	while(spfa())
	{

		int f=1e9,u=t;

		while(pre[u]!=-1){
			f=min(f,e[pre[u]].w);
			u=e[pre[u]^1].v;
		}

		u=t;
		while(pre[u]!=-1){
			e[pre[u]].w-=f;
			e[pre[u]^1].w+=f;
			u=e[pre[u]^1].v;
		}
		
		cost+=f*dis[t];
		flow+=f;

	}

	return cost;
}

void clear()
{
	for(int i=0;i<=t;i++)
		head[i]=0;
	for(int i=1;i<=cnt;i++)
		e[i].v=e[i].c=e[i].w=e[i].nxt=0;
} 

int main()
{
	cin>>m>>n;
	int tt=n*m+n*(n-1)/2;//注意s、t的实际范围；
	s=0,t=tt*2+1;
	
	int qq=0;
	for(int i=1,k=0;i<=n;i++,k++)
		for(int j=1;j<=m+k;j++)
		{
			cin>>a[i][j];
			sum[i][j]=++qq;
		}

	for(int i=1;i<=m;i++){
		add(s,sum[1][i],1,0);
		add(sum[1][i],s,0,0);
	}
	//建图要考虑清楚，不能在建图环节出现错误！！！；
	qq=0;int k=0;
	for(int i=1;i<n;i++,k++)
		for(int j=1;j<=k+m;j++){
			add(sum[i][j],sum[i][j]+tt,1,a[i][j]);
			add(sum[i][j]+tt,sum[i][j],0,-a[i][j]);

			add(sum[i][j]+tt,sum[i+1][j],1,0);
			add(sum[i+1][j],sum[i][j]+tt,0,0);

			add(sum[i][j]+tt,sum[i+1][j+1],1,0);
			add(sum[i+1][j+1],sum[i][j]+tt,0,0);
			++qq;
		}

	for(int i=1;i<=m+k;i++){
		add(sum[n][i],sum[n][i]+tt,1,a[n][i]);
		add(sum[n][i]+tt,sum[n][i],0,-a[n][i]);

		add(sum[n][i]+tt,t,1,0);
		add(t,sum[n][i]+tt,0,0);
	}

	cout<<mincost()<<'\n';

	clear();

	s=0,t=tt+1;
	for(int i=1;i<=m;i++){
		add(s,sum[1][i],1,a[1][i]);
		add(sum[1][i],s,0,-a[1][i]);
	}
	//建图要考虑清楚，不能在建图环节出现错误！！！；
	 k=0;
	for(int i=1;i<n;i++,k++)
		for(int j=1;j<=k+m;j++){

			add(sum[i][j],sum[i+1][j],1,a[i+1][j]);
			add(sum[i+1][j],sum[i][j],0,-a[i+1][j]);

			add(sum[i][j],sum[i+1][j+1],1,a[i+1][j+1]);
			add(sum[i+1][j+1],sum[i][j],0,-a[i+1][j+1]);
		}

	for(int i=1;i<=m+k;i++){
		add(sum[n][i],t,1e9,0);
		add(t,sum[n][i],0,0);
	}
	cout<<mincost()<<"\n";


	clear();

	s=0,t=tt+1;
	for(int i=1;i<=m;i++){
		add(s,sum[1][i],1,a[1][i]);
		add(sum[1][i],s,0,-a[1][i]);
	}
	//建图要考虑清楚，不能在建图环节出现错误！！！；
	 k=0;
	for(int i=1;i<n;i++,k++)
		for(int j=1;j<=k+m;j++){

			add(sum[i][j],sum[i+1][j],1e9,a[i+1][j]);
			add(sum[i+1][j],sum[i][j],0,-a[i+1][j]);

			add(sum[i][j],sum[i+1][j+1],1e9,a[i+1][j+1]);
			add(sum[i+1][j+1],sum[i][j],0,-a[i+1][j+1]);
		}

	for(int i=1;i<=m+k;i++){
		add(sum[n][i],t,1e9,0);
		add(t,sum[n][i],0,0);
	}
	cout<<mincost()<<"\n";

	return 0;

}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 400K, 提交时间: 2022-11-09 17:15:10

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1200, M = 4000, INF = 1e8;

int e[M], ne[M], f[M], w[M], h[N], idx;
int d[N], q[N], pre[N], incf[N];
int n, m, S, T, cnt;
bool vis[N];
int id[50][50], s[50][50];

void insert(int u, int v, int c, int d) {
    e[idx] = v, ne[idx] = h[u], f[idx] = c, w[idx] = d, h[u] = idx++;
    e[idx] = u, ne[idx] = h[v], f[idx] = 0, w[idx] = -d, h[v] = idx++;
}

bool spfa() {
    int tt = 0, hh = 0;
    memset(incf, 0, sizeof incf);
    memset(d, 0xcf, sizeof d);
    q[tt++] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        vis[t] = false;
        if (hh == N) hh = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (f[i] && d[j] < d[t] + w[i]) {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(f[i], incf[t]);
                if (!vis[j]) {
                    vis[j] = true;
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return incf[T] > 0;
}

int EK() {
    int cost = 0;
    while (spfa()) {
        int t = incf[T];
        cost += d[T] * t;
        for (int i = T; i != S; i = e[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t; 
    }
    return cost;
}

void solve(int rule) {
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m + i - 1; j++) {
            insert(id[i][j] * 2, id[i][j] * 2 + 1, rule <= 1 ? 1 : INF, s[i][j]);
            if (i == 1) insert(S, id[i][j] * 2, 1, 0);
            if (i == n) insert(id[i][j] * 2 + 1, T, rule <= 1 ? 1 : INF, 0);
            if (i < n) {
                insert(id[i][j] * 2 + 1, id[i + 1][j] * 2, rule <= 2 ? 1 : INF, 0);
                insert(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, rule <= 2 ? 1 : INF, 0);
            }
        }
    }
    printf("%d\n", EK());
}

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m + i - 1; j++) {
            scanf("%d", &s[i][j]);
            id[i][j] = ++cnt;
        }
    }
    S = 0, T = cnt * 2 + 2;
    
    for (int rule = 1; rule <= 3; rule++) solve(rule);
    return 0;
}

详情