题解 | #网络优化#

线段树优化建图+网络流

首先可以看出是求最大流 源点向用户连一条容量为1的边，每个游客向可以登录的线连容量为1的边，最后m条线向汇点连边，第i条线连一条容量为v[i]的边求最大流即可。

但是，连边操作太多了，可以达到O(nm),所以我们用线段树优化建图。

以及，最后的最后，不要忘记多组输入呜呜呜～～～

#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;

typedef long long ll;
const int maxn = 3e4 + 10;
const int maxm = 2e6 + 10;
int tot,tree[maxn << 2],n,m,l,r,v;
#define INF 0x3f3f3f3f

struct Edge {
  int from, to, cap, flow;
  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct Dinic {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  int d[maxn], cur[maxn];
  bool vis[maxn];

  void init() {
    for (int i = 0; i < maxn; i++) G[i].clear();
    edges.clear();
  }

  void add(int from, int to, int cap) {
   // cout<<"=========="<<from<<' '<<to<<' '<<cap<<endl;
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    d[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          d[e.to] = d[x] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }

  ll DFS(int x, int a) {
    if (x == t || a == 0) return a;
    ll flow = 0, f;
    for (int& i = cur[x]; i < G[x].size(); i++) {
      Edge& e = edges[G[x][i]];
      if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
        e.flow += f;
        edges[G[x][i] ^ 1].flow -= f;
        flow += f;
        a -= f;
        if (a == 0) break;
      }
    }
    return flow;
  }

  ll Maxflow(int s, int t) {
    this->s = s;
    this->t = t;
    ll flow = 0;
    while (BFS()) {
      memset(cur, 0, sizeof(cur));
      flow += DFS(s, INF);
    }
    return flow;
  }
}ans;

void build(int o, int l, int r)
{
	tree[o] = ++tot;
	if(l == r){
		ans.add(0, tree[o], 1);
		return ;
	}
	int mid = (l + r) / 2;
	build(ls, l, mid); build(rs, mid + 1, r);
	ans.add(tree[ls], tree[o], mid - l + 1);
	ans.add(tree[rs], tree[o], r - mid);
}

void update(int o, int l, int r, int x, int y, int v)
{
	if(l >= x && y >= r)
	{
		ans.add(tree[o], v, r - l + 1);
		return ;
	}
	int mid = (l + r) / 2;
	if(mid >= x) update(ls, l, mid, x, y, v);
	if(y > mid) update(rs, mid + 1, r, x, y, v);
}

int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		ans.init();
		tot  = 0;
		build(1, 1, n);	
		for(int i = 1; i <= m; i++)
		{
			scanf("%d%d%d", &l, &r, &v);
			update(1, 1, n, l, r, tot + i);
			ans.add(tot + i,tot + m + 1, v);
		}
//2	cout<<"-----"<<endl;
		printf("%d\n", ans.Maxflow(0,tot + m + 1));
	}
	return 0;
}