【洛谷P5331】 [SNOI2019]通信

题意：

\(n\)个哨站排成一列，第\(i\)个哨站的频段为\(a_i\)。

现在每个哨站可以选择:

直接连接到中心，代价为\(w\)；
连接到前面某个哨站\(j(j<i)\)，代价为\(|a_i-a_j|\)。
规定每个哨站只能被后面的至多一个哨站连接。

问最终最小代价和为多少。

思路：

直接费用流比较好想：每个点有两个选择，我们将点拆为两个点\(x_i,y_i\)，然后
- \(S->x_i\)容量为\(1\)，费用为\(w\)；
- \(S->y_i\)容量为\(1\)，费用为\(0\)；
- \(y_i->x_j,j>i\)容量为\(1\),费用为\(|a_i-a_j|\)。
但直接来搞的话边的数量是\(O(n^2)\)的，时间复杂度不能承受。
我们考虑拆绝对值，然后考虑每个位置的贡献。
具体来说，采用分治的思想（太妙了QAQ），对于当前区间\([l,r]\)，我们只考虑现在\(x_i\) ~ \(x_{mid}\)到\(y_{mid+1}\) ~ \(y_r\)之间的连边。
因为我们是拆绝对值，这里要分两种情况考虑，我们接下来考虑\(a_i>a_j\)的情况。
我们将左边的部分提取出来，离散化后从大到小串在一起，那么每个点都有一个贡献，之后视在哪部分连线即可；
另外一种情况类似。
因为采用分治，每一层我们会多出\(O(n)\)级别的边，所以最后边的总数为\(O(nlogn)\)级别了。

核心思想感觉还是拆分绝对值后单独考虑每个值的贡献，相同的一起计算。但这种串在一起的方式感觉也太巧妙了。。

代码如下：

#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

// #define Local

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 2e5 + 5;

int n, w, tot;

int a[N];

class Flow

{

    bool vis[N],inq[N];ll dis[N];queue<int>q;

    struct edge{int to,w,c,nex;}e[N*10];int cur[N],hr[N],en;

    bool spfa()

    {

        for(int i=S;i<=T;++i) cur[i]=hr[i],inq[i]=0,dis[i]=1e18;

        for(dis[S]=0,inq[S]=1,q.push(S);!q.empty();)

        {

            int u=q.front();q.pop(),inq[u]=0;

            for(int i=hr[u];i;i=e[i].nex)

            if(dis[e[i].to]>dis[u]+e[i].c&&e[i].w)

            {

                dis[e[i].to]=dis[u]+e[i].c;

                if(!inq[e[i].to]) inq[e[i].to]=1,q.push(e[i].to);

            }

        }

        return dis[T]<INF;

    }

    int dfs(int x,int f)

    {

        if(x==T||!f) return f;

        vis[x]=1;

        int w,used=0;

        for(int &i=cur[x];i;i=e[i].nex)

        if(dis[e[i].to]==dis[x]+e[i].c&&e[i].w&&!vis[e[i].to])

        {

            w=dfs(e[i].to,min(f-used,e[i].w));

            e[i].w-=w;e[i^1].w+=w;used+=w;

            if(used==f) break;

        }

        vis[x]=0;return used;

    }

    public:

        int S,T;

        Flow(){S=0;en=1;}

        void ins(int x,int y,int w,int c)

        {

            e[++en]=(edge){y,w,c,hr[x]},hr[x]=en;

            e[++en]=(edge){x,0,-c,hr[y]},hr[y]=en;

        }

        ll Ans(){ll r=0;while(spfa())r+=dfs(S,INF)*dis[T];return r;}

}F;

int b[N], D;

void solve(int l, int r) {

	if(l == r) return;

	int mid = (l + r) >> 1;

	#define lb(x) lower_bound(b + 1, b + D + 1, x) - b

	#define p(x) tot + x

	D = 0;

	for(int i = l; i <= mid; i++) b[++D] = a[i];

	sort(b + 1, b + D + 1); D = unique(b + 1, b + D + 1) - b - 1;

	for(int i = 2; i <= D; i++) F.ins(p(i), p(i - 1), INF, 0);

	for(int i = l; i <= mid; i++) {

		F.ins(i + n, p(lb(a[i])), 1, a[i]);

	}

	for(int i = mid + 1; i <= r; i++) {

		int j = lb(a[i]);

		if(j <= D) F.ins(p(j), i, 1, -a[i]);

	}

	tot += D;

	D = 0;

	for(int i = mid + 1; i <= r; i++) b[++D] = a[i];

	sort(b + 1, b + D + 1); D = unique(b + 1, b + D + 1) - b - 1;

	for(int i = 2; i <= D; i++) F.ins(p(i - 1), p(i), INF, 0);

	for(int i = mid + 1; i <= r; i++) {

		F.ins(p(lb(a[i])), i, 1, a[i]);

	}

	for(int i = l; i <= mid; i++) {

		int j = lb(a[i]);

		if(j <= D) F.ins(i + n, p(j), 1, -a[i]);

	}

	tot += D;

	solve(l, mid); solve(mid + 1, r);

}

void run() {

	for(int i = 1; i <= n; i++) cin >> a[i];

	tot = 2 * n;

	solve(1, n);

	F.T = tot + 1;

	for(int i = 1; i <= n; i++) F.ins(F.S, i, 1, w);

	for(int i = 1; i <= n; i++) F.ins(i, F.T, 1, 0);

	for(int i = 1; i <= n; i++) F.ins(F.S, i + n, 1, 0);

	cout << F.Ans() << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    while(cin >> n >> w) run();

    return 0;

}

巴特西

【洛谷P5331】 [SNOI2019]通信

最新文章

热门文章