差分约束

【差分约束/tarjan缩点】BZOJ2330 银河

传送门

题目的五个条件转化为差分约束的不等式
再加：

设d[0] = 0; d[i] – d[0] = 1 每个星球最低为1亮度
再从0一个点往所有点连1的有向边

题目可能出现无解的情况，差分约束的图出现正环即无解。

但是题目数据量很大，直接在跑最长路的时候用spfa判正环会超时

先tarjan缩点。同一个强连通分量里面如果边权之和为正那么肯定存在正环直接无解。复杂度 $O(N)$

最后把缩点后的图重新建图，是一个有向无环图，可以直接跑最长路。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 233;
int n, m;
int h[maxn], e[maxn], val[maxn], pre[maxn], cnt;
int hc[maxn], ec[maxn], valc[maxn], prec[maxn], cntc;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt;
}
void addc(int u, int v, int w)
{
    ec[++cntc] = v;

… Read the rest

【差分约束/数据结构优化贪心】poj1201 区间

传送门

这个题目有两种做法

设s [ i ]表示前i个里面取数的个数
* s[b] – s[a – 1] = ci
* s[k] – s[k – 1] = 0 (任何k要比k-1取得多)
* s[k] – s[k – 1] <= 1 (任何数只能取一次)

然后建图跑，从第一个点开始跑最长路。
注意最后只能用spfa来跑，因为djistra无法处理反边权的情况。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 233;
int h[maxn], e[maxn], pre[maxn], val[maxn], cnt;
void add(int u, int v, int w)
{
    e[++cnt] = v; val[cnt] = w; pre[cnt] = h[u]; h[u] = cnt; 
}
int dis[maxn], vis[maxn];
void dji()
{
    memset(dis,

… Read the rest