C++14(g++5.4) 解法, 执行用时: 9601ms, 内存消耗: 24384K, 提交时间: 2020-03-09 11:27:54

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define sz(a) ((int)a.size())
const int maxn = 2e3 + 5;
const ll inf = 1ll << 60;

template<class ll>
struct Dinic{

    struct Edge{ int v, rev; ll cap, cot; };
    vector<Edge> G[maxn];
    ll dis[maxn];
    int cur[maxn], vis[maxn], n, sp, tp;
    void init(int nn){

        n = nn;
        for(int i = 1; i <= n; ++i) G[i].clear();
    }
    void add(int u, int v, ll cap, ll cot){

        G[u].pb({v, sz(G[v]), cap, cot});
        G[v].pb({u, sz(G[u]) - 1, 0, -cot});
    }
    int bfs(){

        queue<int> q;
        for(int i = 1; i <= n; ++i) dis[i] = inf, vis[i] = 0;
        dis[sp] = 0, q.push(sp), vis[sp] = 1;
        while(!q.empty()){

            int u = q.front(); q.pop(); vis[u] = 0;
            for(Edge &e : G[u]){

                if(e.cap && dis[e.v] > dis[u] + e.cot){

                    dis[e.v] = dis[u] + e.cot;
                    if(!vis[e.v]) q.push(e.v), vis[e.v] = 1;
                }
            }
        }
        return dis[tp] != inf;
    }
    ll dfs(int u, ll flow){

        if(u == tp || !flow) return flow;
        ll ret = 0, tmp; vis[u] = 1;
        for(int &i = cur[u]; i < sz(G[u]); ++i){

            Edge &e = G[u][i];
            if(!vis[e.v] && dis[e.v] == dis[u] + e.cot && (tmp = dfs(e.v, min(e.cap, flow - ret)))){

                ret += tmp, e.cap -= tmp, G[e.v][e.rev].cap += tmp;
                if(ret == flow) { vis[u] = 0; return ret; }
            }
        }
        if(!ret) vis[u] = 1;
        return ret;
    }
    pair<ll, ll> solve(int s, int t, ll ans[]){

        sp = s, tp = t;
        ll mf = 0, mc = 0;
        while(bfs()){

            for(int i = 1; i <= n; ++i) cur[i] = 0;
            ll tmp = dfs(sp, inf);
            for(int i = 1; i <= tmp; ++i) ans[i + mf] = ans[i + mf - 1] + dis[tp];
            mf += tmp, mc += tmp * dis[tp];
        }
        return {mf, mc};
    }
};

Dinic<ll> dn;
ll ans[maxn];
int a[maxn], b[maxn];
int n, m;

int main(){
 
    ios::sync_with_stdio(0); cin.tie(0);
    int t, cas = 0; cin >> t;
    while(t--){

        cin >> n >> m;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = 1; i <= m; ++i) cin >> b[i];
        cout << "Case #" << ++cas << ":\n";
        ll base = 0;
        for(int i = 1; i < n; ++i) base += abs(a[i] - a[i + 1]);
        int S = m + n + 2, T = S + 1;
        dn.init(T);
        for(int i = 1; i <= m; ++i) dn.add(S, i, 1, 0);
        for(int i = 1; i <= n + 1; ++i) dn.add(m + i, T, 1, 0);
        for(int i = 1; i <= m; ++i){

            dn.add(i, m + 1, 1, -abs(b[i] - a[1]));
            dn.add(i, m + n + 1, 1, -abs(b[i] - a[n]));
            for(int j = 2; j <= n; ++j){

                int dt = abs(b[i] - a[j - 1]) + abs(b[i] - a[j]) -abs(a[j] - a[j - 1]);
                dn.add(i, m + j, 1, -dt);
            }
        }
        dn.solve(S, T, ans);
        for(int i = 1; i <= m; ++i) cout << base - ans[i] << " ";
        cout << "\n";
        for(int i = 1; i <= n + 1; ++i){

            int p = 0;
            for(auto &e : dn.G[m + i]){

                if(e.v == T || !e.cap) continue;
                p = e.v; break;
            }
            if(p) cout << b[p] << " ";
            if(i <= n) cout << a[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 5199ms, 内存消耗: 17668K, 提交时间: 2022-11-25 09:34:16

#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
#define fi first
#define se second
#define min amin
#define max amax
#define pb push_back
using namespace std;
using ll=long long;
using pii=array<int,2>;
constexpr int N=610;
constexpr int inf=1E9;
constexpr int p=998244353;
int qpow(int x,int n=p-2){int y=1;for(;n;n>>=1,x=1LL*x*x%p)if(n&1)y=1LL*y*x%p;return y;}
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>U min(U x,V y){return x<y?x:y;}
template<typename U,typename V>U max(U x,V y){return x>y?x:y;}
template<typename U,typename...V>U min(U x,V...y){return min(x,min(y...));}
template<typename U,typename...V>U max(U x,V...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,V y){return x>y?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,V y){return x<y?x=y,true:false;}

int n,m,y,z;
int a[N],b[N],c[N],dis[N<<1],pre[N<<1];
vector<array<int,4>>to[N<<1];
queue<int>q;
bool tag[N<<1];
void add(int u,int v,int w)
{
    int l=to[u].size(),r=to[v].size();
    to[u].pb({v,r,w,1});
    to[v].pb({u,l,-w,0});
}
void push(int x,int d,int y)
{
    if(cmax(dis[x],d))
    {
        pre[x]=y;
        if(!tag[x])q.push(x),tag[x]=1;
    }
}
void calc(int x)
{
    for(auto &[t,i,d,w]:to[x])if(w)
    {
        if(t^z)cout<<b[t]<<' ';
        break;
    }
}
void solve()
{
    n=read(),m=read(),y=n+m+2,z=y+1;
    for(int i=1;i<=z;++i)to[i].clear();
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        ans+=c[i]=abs(a[i]-a[i-1]);
        add(m+i,z,0);
    }
    ans-=c[1];
    add(y-1,z,0);
    for(int i=1;i<=m;++i)
    {
        cin>>b[i];
        add(y,i,0);
        add(i,m+1,abs(b[i]-a[1]));
        add(i,y-1,abs(b[i]-a[n]));
        for(int j=2;j<=n;++j)add(i,m+j,abs(b[i]-a[j-1])+abs(b[i]-a[j])-c[j]);
    }
    for(int o=m;o--;)
    {
        for(int i=1;i<=z;++i)dis[i]=INT_MIN;
        push(y,0,0);
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            tag[x]=0;
            for(auto &[t,i,d,k]:to[x])if(k)push(t,dis[x]+d,i);
        }
        ans+=dis[z];
        for(int i=z;i^y;)
        {
            auto &[j,k,d,w]=to[i][pre[i]];
            ++w;
            --to[j][k][3];
            i=j;
        }
        cout<<ans<<' ';
    }
    cout<<'\n';
    for(int i=1;i<=n;++i)
    {
        calc(m+i);
        cout<<a[i]<<' ';
    }
    calc(y-1);
    cout<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(6);
    int T=read();
    for(int i=1;i<=T;++i)
    {
        cout<<"Case #"<<i<<":\n";
        solve();
    }
}