【交互 / 差分约束】

题目

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 10510;
const int M = 200 * 500 + 10;
int h[N], ne[M], e[M], w[M], idx;
ll d[N];
int n, m;
bool st[N];
int cnt[N];void add(int a, int b, int c)
{w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
ll spfa()
{memset(d, 0x3f, sizeof d);queue<int> q;for(int i = 1; i <= n+m; i++)q.push(i);while(q.size()){int u = q.front(); q.pop();st[u] = 0;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(d[j] > d[u] + w[i]){d[j] = d[u] + w[i];cnt[j] += 1;if(cnt[j] >= m) return -1;if(!st[j]){q.push(j);st[j] = 1;}}}}ll maxx = d[1], minn = d[1];for(int i = 2; i <= m; i++)maxx = max(maxx, d[i]), minn = min(minn, d[i]);return maxx - minn;
}	
int main()
{	cin >> n >> m;memset(h, -1, sizeof h);for(int t = 1; t <= n; t++){int l, r, p, q, ans;cin >> l >> r >> p >> q >> ans;for(int i = l; i <= r; i++)add(i, m+t, 0);for(int j = p; j <= q; j++)add(m+t, j, -ans);}ll ans = spfa();if(ans == -1) puts("No Solution");else cout << ans;
}