BZOJ 1150[CTSC 2007]データバックアップBackup——アナログ費用フロー+ヒープ+チェーンテーブル

3807 ワード

タイトルの説明

IT会社では、大規模なオフィスビルやオフィスビルのコンピュータデータをバックアップしています.しかし、データバックアップの作業は退屈です.
そのため、異なるオフィスビルを互いにバックアップするシステムを設計したいと思っていますが、家に座ってコンピュータゲームを楽しむことができます.既知のオフィス
ビルはみな同じ通りにある.あなたはこれらのオフィスビルにペアを組むことにしました(2つのグループ).各オフィスビルはこの2つの建物の間に網を敷くことができます.
ケーブルは互いにバックアップできるようにします.しかし、ネットワークケーブルの費用は高い.ローカルテレコムはK本のネットワークケーブルしか提供できません.これは
K対オフィスビル(または合計2 Kのオフィスビル)のバックアップのみを手配できます.いずれのオフィスビルも唯一のペアグループに属しています(言い換えれば、この2 K
このオフィスビルはきっと違うに違いない).また、電信会社はネットワークケーブルの長さ(キロ数)で料金を徴収する必要があります.だから、このK対オフィスを選ぶ必要があります.
ケーブルの全長をできるだけ短くします.言い換えれば、このK対のオフィスビルを選択して、各対のオフィスビル間の距離の和(総距離)を選択する必要があります.
できるだけ小さくする.次の例では、5人のお客様がオフィスビルが1つの街にあると仮定します.下図に示します.この5つのオフィスビルは
大通りの起点から1 km、3 km、4 km、6 km、12 kmに位置しない.電信会社はK=2本のケーブルしか提供していません.
上記の例では、1番目と2番目のオフィスビルを接続し、3番目と4番目のオフィスビルを接続するのがベストです.必要に応じて使用できます
K=2本のケーブル.1本目のケーブルの長さは3 km-1 km=2 km、2本目のケーブルの長さは6 km-4 km=2 kmです.このペアリングスキームには総長が必要だ
4 kmのネットワークケーブルは、距離の和の最小の要件を満たしています.

入力

最初の行は整数nとkを含む
ここで、n(2≦n≦100000)はオフィスビルの数を表し、k(1≦k≦n/2)は利用可能なネットワークケーブルの数を表す.
次のn行は、各オフィスビルから通りの起点までの距離を示す整数(0≦s≦10000000)のみを含む.
これらの整数は、小さい順に表示されます.

しゅつりょく

出力は、2 K個の異なるオフィスビルをk対に接続するために必要なネットワークケーブルの最小総長を与える正の整数で構成されるべきである.

サンプル入力

5 2 1 3 4 6 12

サンプル出力

4

まず選択した各対の点は必ず隣接する点であり、隣接座標を減算すると$n-1$のオプションスキームが得られ、これらのスキームの中で$k$個を選択する必要がある.各ポイントは最大1つのシナリオしかないため、隣接するシナリオを同時に選択することはできません.この問題は明らかに費用フローで解決できる:$n$個の点の中で各点を2つの点に分ける$a_{i},b_{i}$,ソースポイント連向$a_{i}$,$b_{i}$連向為替ポイント,$a_{i}$連向$b_{i-1}$と$b_{i+1}$.このように費用フローを1回走ると、答えの2倍の大きさの最小費用(モデリングでは$i$マッチング$i+1$と$i+1$マッチング$i$が2回計算されるため)を得ることができ、この図の特殊な性質を考慮すると、各点はその両側の2つの点にのみ接続されている(すなわち、ソース点と送金点が接続されているエッジを考慮せず、残りのエッジは2つの交差するチェーンである).シナリオ$i$が拡張され、逆エッジが構築されると、その後$i$に隣接するシナリオ($i-1$と仮定)に拡張されると、費用フローが最短を選択するたびに$i$シナリオの逆エッジが拡張され、$i+1$シナリオがさらに進むに違いない.これにより、このプロセスをシミュレートし、現在のコストが最も小さいシナリオをスタックで維持し、最適シナリオを取り出すたびに(最適シナリオを$b$と仮定し、隣接シナリオを$a,c$)、最適シナリオを隣接シナリオと取り出し、元の位置に$a+c-b$という代価の新しいシナリオを入れることができ、新しいシナリオを選択すると、実際に$a$と$c$を選択して$b$を放棄したことを示し、費用フローの後悔プロセスを実現することができる.これにより、スタックトップを取り出すたびに1つの案が複数選択されることが保証される(ただし、ここでは両端の処理に注意する).隣接関係は双方向チェーンテーブルで維持すればよい.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define pr pair
using namespace std;
int n,k;
priority_queue< pr,vector,greater >q;
int cnt;
int pre[600010];
int suf[600010];
int a[600010];
int vis[300010];
ll s[300010];
int t[300010];
int v[600010];
ll ans;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i!=1)
        {
            v[i]=a[i]-a[i-1];
        }
    }
    for(int i=2;i<=n;i++)
    {
        cnt++;
        s[cnt]=1ll*v[i];
        t[cnt]=cnt;
        pre[cnt]=cnt-1;
        suf[cnt]=cnt+1;
        q.push(make_pair(s[cnt],t[cnt]));
    }
    pre[1]=0;
    suf[n-1]=0;
    s[0]=1<<30;
    while(k)
    {
        int now=q.top().second;
        ll res=q.top().first;
        q.pop();
        if(!vis[now])
        {
            ans+=res;
            vis[now]=1;
            vis[pre[now]]=1;
            vis[suf[now]]=1;
            cnt++;
            t[cnt]=cnt;
            s[cnt]=s[pre[now]]+s[suf[now]]-res;
            pre[cnt]=pre[pre[now]];
            suf[cnt]=suf[suf[now]];
            suf[pre[pre[now]]]=cnt;
            pre[suf[suf[now]]]=cnt;
            q.push(make_pair(s[cnt],t[cnt]));
            k--;
        }
    }
    printf("%lld",ans);
}

転載先:https://www.cnblogs.com/Khada-Jhin/p/10421588.html

JavaをJava 17(Collection Framework(2)、LinkedList、Stack、Queue)に変換

TIL#41 JS)JavaScriptの非同期化