【算法】我,网络流,再生产!(二)

考虑到上篇文章已经加载速度慢的要死,还是开个新的吧qwq。
luogu P2046 [NOI2010]海拔
这个题目首先我们考虑,海拔只有0/1,因为如果有更大/更小的数出现,会白白增加花费吧……
那么在再感性一下,也就说0在一起1在一起……那么实际上我们就需要寻找01的分界线,实际就是最小割,而这个图是一个平面图,根据平面图惯有操作,平面图最小割就是其对偶图的最短路,也就说建出对偶图就好,左下起点,右上终点。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, t, lx, tot = -1, head[300050], dis[300050];

struct in
{
    int to, ne, co;
}ter[1200050];

struct node
{
    int pos, dis;
    inline bool operator < (const node &a) const
    {
        return dis > a.dis;
    }
};

priority_queue <node> qwq;

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    //ter[++ tot] = (in){f, head[l], c}, head[l] = tot;
}

bool flag[300050];

inline int dijkstra()
{
    memset(dis, 63, sizeof(dis)), dis[0] = 0, qwq.push((node){0, 0});
    while(!qwq.empty())
    {
        node qaq = qwq.top(); qwq.pop();
        if(flag[qaq.pos])
            continue;
        flag[qaq.pos] = 1;
        for(ri i = head[qaq.pos]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(dis[to] > dis[qaq.pos] + ter[i].co)
            {
                dis[to] = dis[qaq.pos] + ter[i].co;
                if(!flag[to])
                    qwq.push((node){to, dis[to]});
            }
        }
    }
    return dis[t];
}

int main()
{
    re(n); t = n * n + 1; memset(head, -1, sizeof(head));
    for(ri i = 0; i <= n; i ++)//从东往西,也就说会影响上下之间的关系 
        for(ri j = 1; j <= n; j ++)//从上往下建的边 
            re(lx), build(max(0, (i - 1) * n + j), min(t, i * n + j), lx);
    for(ri i = 1; i <= n; i ++)//从北往南,也就说会影响左右之间的关系 
        for(ri j = 0; j <= n; j ++)
        {
            re(lx);
            if(!j)//在最左边就和终点连接 
                build((i - 1) * n + 1, t, lx);
            else if(j == n)//最右边和起点 
                build(0, i * n, lx);
            else//两列挨着就从右向左建边 
                build((i - 1) * n + j + 1, (i - 1) * n + j, lx);                
        }
    for(ri i = 0; i <= n; i ++)//从西向东
        for(ri j = 1; j <= n; j ++)//从下往上,反着 
            re(lx), build(min(t, i * n + j), max(0, (i - 1) * n + j), lx);
    for(ri i = 1; i <= n; i ++)
        for(ri j = 0; j <= n; j ++)
        {
            re(lx);
            if(!j)
                build(t, (i - 1) * n + 1, lx);
            else if(j == n)
                build(i * n, 0, lx);
            else
                build((i - 1) * n + j, (i - 1) * n + j + 1, lx);
        }
    printf("%d", dijkstra());
}

【luogu CF720A】Closing ceremony

这个题目显然网络流过不了,所以需要考虑贪心,考虑对于从(0,0)出发的点,每一个都尽可能的去选择自己能到达,并且距离(0, m+1)尽可能远的格子。然后就完了……

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e4 + 10;

int n, m, k, l, lx, a[ms], tot;

struct node
{
    int x, y, z, dis;
    inline bool operator < (const node &a) const
    {
        return z < a.z;
    }
}tmp[ms];

priority_queue <node> qwq;

inline bool cmp(node a, node b)
{
    return a.dis < b.dis;
}

int main()
{
    re(n), re(m), re(k);
    for(ri i = 1; i <= k; i ++)
        re(a[i]);
    sort(a + 1, a + 1 + k);
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            tmp[++ tot] = (node){i, j, m + 1 - j + i, i + j};
    sort(tmp + 1, tmp + 1 + tot, cmp);
    int ta = 1; bool fl = 0;
    for(ri i = 1; i <= k; i ++)
    {
        while(a[i] >= tmp[ta].dis && ta <= tot)
            qwq.push(tmp[ta]), ta ++;
        if(qwq.empty())
        {
            fl = 1; break;
        }
        //cout << qwq.top().z << '\n'; 
        qwq.pop();
    }
    while(ta <= tot)
        qwq.push(tmp[ta]), ta ++;
    re(k);
    for(ri i = 1; i <= k; i ++)
        re(a[i]);
    sort(a + 1, a + 1 + k);
    for(ri i = k; i > 0; i --)
    {
        if(a[i] < qwq.top().z)
        {
            fl = 1; break;
        }
        //cout << qwq.top().z << '\n'; 
        qwq.pop();
    }
    printf("%s", fl ? "NO" : "YES");
    system("pause");
}

【BZOJ2253】[BJWC2010]纸箱堆叠

这个题目显然是一个严格化的三维偏序,即
a_i < a_j,b_i < b_j,c_i < c_j
那么问题显然就变成cdq优化转移了,注意这里是严格的,因此我们划分区间的时候,要保证所有第一维相同的数字在同一个区间,而不会被mid给分开……但是这样真的不会破坏复杂度吗我也不知道……

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 2e5 + 10;

lo a, p, n, lsh[ms], ta, tre[ms], ans;//lsh == 离散化 

struct node
{
    lo x, y, z, ans;

    inline bool operator < (const node &a) const
    {
        if(y != a.y)
            return y < a.y;
        return z < a.z;
    }
}ter[ms], tmp[ms];

inline bool cmp(node a, node b)
{
    if(a.x != b.x)
        return a.x < b.x;
    if(a.y != b.y)
        return a.y < b.y;
    return a.z < b.z;
}

inline int lowbit(int x)
{
    return x & (-x);
}

inline void change(int x, lo v)
{
    while(x <= ta)
        tre[x] = max(tre[x], v), x += lowbit(x);    
}

inline lo ask(int x)
{
    lo rt = 0;
    while(x)
        rt = max(rt, tre[x]), x -= lowbit(x);
    return rt;
}

inline void clear(int x)
{
    while(x <= ta)
    {
        if(tre[x])
            tre[x] = 0;
        else
            break;
        x += lowbit(x);
    }
}

void merge(int l, int r)
{
    if(l >= r)
        return;
    int mid = (l + r) >> 1, t1 = mid, t2 = mid + 1; mid = ms;
    while(t1 >= l || t2 <= r)//为了保证三维偏序的严格,我们把第一维所有相同的数字划在一起而不是分到左右两边 
    {
        if(t1 >= l && ter[t1].x != ter[t1 + 1].x)
        {
            mid = t1; break;
        }
        if(t2 <= r && ter[t2].x != ter[t2 - 1].x)
        {
            mid = t2 - 1; break;
        }
        t1 --, t2 ++;
    }
    if(mid == ms)//如果第一维直接都是一样的,那不用算了 
        return;
    merge(l, mid);//先去计算左边 
    t1 = l, t2 = mid + 1;
    sort(ter + l, ter + mid + 1), sort(ter + mid + 1, ter + r + 1);
    for(ri i = l; i <= r; i ++)
    {
        if(t2 > r || (t1 <= mid && ter[t1].y < ter[t2].y))//如果右边的区间算完了,或者左边要比右边小 
            change(ter[t1].z, ter[t1].ans), t1 ++;
        else//否则更新答案 
            ter[t2].ans = max(ter[t2].ans, ask(ter[t2].z - 1) + 1), t2 ++;
    }
    for(ri i = l; i <= mid; i ++)//清空左边的影响 
        clear(ter[i].z);
    sort(ter + mid + 1, ter + r + 1, cmp), merge(mid + 1, r);//再去算右边 
}

int main()
{
    re(a), re(p), re(n);
    lo tmp = a % p;
    for(ri i = 1; i <= n; i ++, tmp = tmp * a % p)
    {
        ter[i].x = tmp, tmp = tmp * a % p, ter[i].y = tmp, tmp = tmp * a % p, ter[i].z = tmp;
        if(ter[i].x > ter[i].y)//提前排好序 
            swap(ter[i].x, ter[i].y);
        if(ter[i].x > ter[i].z)
            swap(ter[i].x, ter[i].z);
        if(ter[i].y > ter[i].z)
            swap(ter[i].y, ter[i].z);
        ter[i].ans = 1;
        lsh[++ ta] = ter[i].x, lsh[++ ta] = ter[i].y, lsh[++ ta] = ter[i].z;
    }
    sort(lsh + 1, lsh + 1 + ta);
    ta = unique(lsh + 1, lsh + 1 + ta) - lsh - 1;
    for(ri i = 1; i <= n; i ++)//离散化 
    {
        ter[i].x = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].x) - lsh;
        ter[i].y = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].y) - lsh;
        ter[i].z = lower_bound(lsh + 1, lsh + 1 + ta, ter[i].z) - lsh;
    }
    sort(ter + 1, ter + 1 + n, cmp);
    merge(1, n);//cdq 
    for(ri i = 1; i <= n; i ++)//比较答案 
        ans = max(ans, ter[i].ans);
    printf("%lld", ans);
}

【算法】我,网络流,再生产!(一)

(玩了个少剧的梗2333333333333333)被zhhx大爷的课件锤到自闭,瞬间觉得自己学了个假的网络流,好好再整理下课件的题目qwq。
首先是个贪心模拟网络流的题目
BZOJ 3716 [PA2014]Muzeum
这个题首先很显然,是个最大权闭合子图,因为手办对警卫有依赖关系,但是你考虑直接建一个最大权闭合子图显然是不太现实的,因为nm都是2e5这种级别的,网络流就算是再玄学也不可能跑得过去,那么这个时候我们就只能贪心/dp了。
首先我们可以通过向量的伸缩使得这个图变成直角,那么变成直角之后我们是不是就可以扫描线之类的处理了。
提前将伸缩好的手办和警卫按照x从小到大排序,之后用set维护y。
考虑网络流我们需要流动,这个地方我们用类似于流的思想,每次从较高处去拿一个手办(因为显然较低的更普遍适用),用这个手办的值去抵消守卫所收贿赂,直到被抵消完或者没法抵消,那么就完成了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const lo ms = 2e5 + 10;

lo n, m, w, h, lx, ly, lz, ans;

struct node
{
    lo x, y, v;
}a[ms], b[ms];

inline bool cmp(node a, node b)
{
    return a.x < b.x;
}

multiset <pair <lo, lo> > mmp;

multiset <pair <lo, lo> >::iterator it;

int main()
{
    re(n), re(m), re(w), re(h);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), re(lz), lx *= h, ly *= w, a[i] = (node){lx + ly, lx - ly, lz}, ans += lz;
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), re(lz), lx *= h, ly *= w, b[i] = (node){lx + ly, lx - ly, lz};
    sort(a + 1, a + 1 + n, cmp), sort(b + 1, b + 1 + m, cmp);
    int ta = 1;
    for(ri i = 1; i <= m; i ++)
    {
        while(ta <= n && a[ta].x <= b[i].x)
            mmp.insert(make_pair(a[ta].y, a[ta].v)), ta ++;
        it = mmp.lower_bound(make_pair(b[i].y, 0));
        lo rt = b[i].v;
        while(rt && it != mmp.end())
        {
            pair <lo, lo> qaq = *it; mmp.erase(it);
            int x = min(rt, qaq.second);
            rt -= x, ans -= x, qaq.second -= x;
            if(qaq.second)
                mmp.insert(qaq);
            else
                it = mmp.lower_bound(make_pair(b[i].y, 0));
        }
    }
    printf("%lld", ans);
}

luogu P3731 [HAOI2017]新型城市化
这个题目学过了可能会挺套路的。
首先考虑问题转化,题目里面实际上给了我们一张补图,而城市群实际上是个团,最大城市群实际上也就是原图的最大团,那么因为团是两两有边的,所以到了补图上面就是两两不能有边,也就是最大独立集。
而这个补图根据题意可知,是一个二分图,而二分图的最大独立集=所有点-二分图最小覆盖,也挺好理解的,你选择最少的点就可以覆盖整个图,那么最小覆盖剩下的点也一定是坠多的。
我们还需要进行第三次转化,最小覆盖==最大匹配,考虑感性的证明,现在存在一个最大匹配,那么不会存在还能够匹配的两个点,也就说对于每一个边都是存在至少一个点被匹配的,那么一定被覆盖过了;考虑存在一个不是最大匹配但是已经完成覆盖的情况,那么也就说至少还存在两个点可以通过增广路进行匹配,那么也就说还存在没有被完全覆盖的边,不符合初始条件,即不存在。
那么经过这三次转化之后我们就将问题从求最大团到最大匹配了。我们的目的是通过删去这个补图的某些边使得最大团变大,也就说补图的最大独立集变大->最小覆盖减小->最大匹配减小。
那么只要考虑那些边一定在最大匹配就好了,割掉他们就一定会减少最大匹配了。
这个时候就是上套路了,对残量网络求scc,一个边一定在最大匹配当且仅当这个边是满流边且两端不在同一个连通分量里面。感性理解下的话就是如果在一个连通分量,至少存在两种方案可以选择,而不在同一个连通分量里的就没得选择了。

// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 2e5 + 10;

int lx, ly, t, lz, n, m, tot = -1, head[ms], ff[ms], ll[ms], he[ms], col[ms];

int de[ms], dfn[ms], scc[ms], low[ms], sta[ms], ta, cnt, ColNum, pos[ms];

struct in
{
    int to, ne, co;
}ter[ms << 2], e[ms << 2];

inline void build(int f, int l, int c)
{
    e[++ tot] = (in){l, he[f], c}, he[f] = tot;
    e[++ tot] = (in){f, he[l], 0}, he[l] = tot;
}

inline void rebuild(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

queue <int> q;

inline void bfs(int s)
{
    q.push(s), col[s] = 0;
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = he[qaq]; i >= 0; i = e[i].ne)
        {
            int to = e[i].to;
            if(col[to] < 0)
                col[to] = col[qaq] ^ 1, q.push(to);
        }
    }
}

inline bool dinic_bfs()
{
    for(ri i = 1; i <= t; i ++)
        de[i] = 0;
    de[0] = 1, q.push(0);
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(!de[to] && ter[i].co)
                q.push(to), de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            int tmp = dfs(to, min(fl, ter[i].co));
            if(tmp > 0)
            {
                ter[i].co -= tmp, ter[i ^ 1].co += tmp, fl -= tmp, rt += tmp;
                if(!fl)
                    return rt;
            }
        }
    }
    return rt;
}

inline void dinic()
{
    while(dinic_bfs())
        dfs(0, 1e9 + 7);
}

bool flag[ms];

void tarjan(int no, int f)
{
    dfn[no] = low[no] = ++ cnt, sta[++ ta] = no, flag[no] = 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if((!ter[i].co) || to == f)
            continue;
        if(!dfn[to])
            tarjan(to, no), low[no] = min(low[no], low[to]);
        else if(flag[to])
            low[no] = min(low[no], dfn[to]);
    }
    if(low[no] == dfn[no])
    {
        ColNum ++;
        while(ta > 0)
        {
            int qaq = sta[ta]; ta --; scc[qaq] = ColNum, flag[qaq] = 0;
            if(qaq == no)
                break;
        }
    }
}

pair <int, int> ans[ms];

inline void solve()
{
    ta = 0;
    for(ri i = 1; i <= m; i ++)
        if((!ter[pos[i]].co) && scc[ff[i]] != scc[ll[i]])
            ans[++ ta] = ff[i] < ll[i] ? make_pair(ff[i], ll[i]) : make_pair(ll[i], ff[i]);
    sort(ans + 1, ans + 1 + ta);
    printf("%d\n", ta);
    for(ri i = 1; i <= ta; i ++)
        printf("%d %d\n", ans[i].first, ans[i].second);
}

int main()
{
    re(n), re(m), t = n + 5;
    memset(head, -1, sizeof(head)), memset(he, -1, sizeof(he)), memset(col, -1, sizeof(col));
    for(ri i = 1; i <= m; i ++)
        re(ff[i]), re(ll[i]), build(ff[i], ll[i], 0);
    for(ri i = 1; i <= n; i ++)
        if(col[i] < 0)
            bfs(i);
    for(ri i = 1; i <= m; pos[i] = tot - 1, i ++)
        if(col[ff[i]])
            rebuild(ll[i], ff[i], 1);
        else
            rebuild(ff[i], ll[i], 1);
    for(ri i = 1; i <= n; i ++)//源点连颜色为0的,汇点;连颜色为1的
        if(col[i])
            rebuild(i, t, 1);
        else
            rebuild(0, i, 1);
    dinic();
    for(ri i = 0; i <= t; i ++)
        if(!dfn[i])
            tarjan(i, 0);
    solve();
}

luogu P3329 [ZJOI2011]最小割
这个题如果学过最小割树那么他就是个模板。原理非常简单,建立一个最小割树,然后枚举每一对,看看它是不是超过限制的大小就好。
关键是怎么建,其实这里不用直接建出来…………
类似于归并的思想,开始先生成一个12345……n这样一个序列,然后类似于归并,处理一整个区间,每次把区间的开头作为源点,结尾作为汇点,跑一下dinic,然后按照与s/t的连通性把这个区间拆分成两半,枚举点对,如果这两个点对不在同一个小区间,就计算答案。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 155;

lo T, n, m, qq, x, tot, lx, ly, lz, ans[ms][ms], pri[ms * ms];

int q[ms], de[ms], a[ms], tmp[ms], head[ms], he[ms];

bool flag[ms];

struct in
{
    int to, ne; lo co;
}ter[10010];

struct node
{
    int pos; lo num, ans;
}Ask[40];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], c}, head[l] = tot;
}

inline bool bfs(int s, int t)
{
    int hh = 0, tt = 0; memset(de, 0, sizeof(de));
    de[s] = 1, q[hh] = s;
    while(hh <= tt)
    {
        int qaq = q[hh ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, q[++ tt] = to;
        }
    }
    return de[t] > 0;
}

lo dfs(int no, lo fl, int t)
{
    if(no == t)
        return fl;
    lo rt = 0, ret;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co)
        {
            ret = dfs(to, min(fl, ter[i].co), t);
            if(ret > 0)
            {
                fl -= ret, rt += ret, ter[i].co -= ret, ter[i ^ 1].co += ret;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline lo dinic(int s, int t)
{
    lo lin, rt = 0;
    while(bfs(s, t))
    {
        memcpy(he, head, sizeof(he));
        while((lin = dfs(s, 1e9 + 7, t)) > 0)
            rt += lin;
    }
    return rt;
}

inline void rebuild()
{
    for(ri i = 0; i <= tot; i += 2)
        ter[i].co = ter[i ^ 1].co = ((ter[i].co + ter[i ^ 1].co) >> 1);
}

void col(int x)
{
    flag[x] = 1;
    for(ri i = head[x]; i >= 0; i = ter[i].ne)
        if(ter[i].co && (!flag[ter[i].to]))
            col(ter[i].to);
}

void merge(int l, int r)
{
    if(l >= r)
        return;
    rebuild(); lo maxflow = dinic(a[l], a[r]);
    memset(flag, 0, sizeof(flag)), col(a[l]);
    for(ri i = 1; i <= n; i ++)
    {
        if(!flag[i])
            continue;
        for(ri j = 1; j <= n; j ++)
        {
            if(flag[j])
                continue;
            ans[i][j] = ans[j][i] = min(ans[i][j], maxflow);
        }
    }
    int ta = l - 1;
    for(ri i = l; i <= r; i ++)//按照点与s/t的连通性划分 
        if(flag[a[i]])
            tmp[++ ta] = a[i];
    int poi = ta;
    for(ri i = l; i <= r; i ++)
        if(!flag[a[i]])
            tmp[++ ta] = a[i];
    for(ri i = l; i <= r; i ++)
        a[i] = tmp[i];
    merge(l, poi), merge(poi + 1, r);
}

inline bool cmpa(node a, node b)
{
    return a.num < b.num;
}

inline bool cmpb(node a, node b)
{
    return a.pos < b.pos;
}

inline void solve()
{
    memset(head, -1, sizeof(head)), memset(ans, 63, sizeof(ans)), tot = -1;
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        a[i] = i;
    while(m --)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    merge(1, n); re(qq);
    for(ri i = 1; i <= qq; i ++)
        re(lx), Ask[i] = (node){i, lx, 0};
    sort(Ask + 1, Ask + 1 + qq, cmpa); int ta = 0;
    for(ri i = 1; i <= n; i ++)
        for(ri j = i + 1; j <= n; j ++)
            pri[++ ta] = ans[i][j];
    sort(pri + 1, pri + 1 + ta);
    int tail = 1;
    for(ri i = 1; i <= ta; i ++)
    {
        while(Ask[tail].num < pri[i] && tail <= qq)
            Ask[tail].ans = i - 1, tail ++;
    }
    while(tail <= qq)
        Ask[tail].ans = ta, tail ++;
    sort(Ask + 1, Ask + 1 + qq, cmpb);
    for(ri i = 1; i <= qq; i ++)
        cout << Ask[i].ans << '\n';
    cout << '\n';
}

int main()
{
    re(T);
    while(T --)
        solve();
}

BZOJ 4625 [BJOI2016]水晶
这个题简直是玄学……我也不知道一开始我建图错在哪里了……明明看起来没什么区别。
这个题其实也挺套路,但是我傻QAQ,你可以按照(x+y+z)mod3的结果来将点划分成三种,显然这就可以构建三分图了,然后你发现有关系的都是相邻并且mod之后可以得到012这样的……然后你就可以建个三分图跑最小割就过了。
为了方便这里可以把z这一维度给压掉。变成x-z,y-z,但是这样你算z轴的变化的时候,就必须要xy一起+/-了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 5e4 + 10;

const int bs = 3e4;

int tot = -1, t, ans, n, m, lz, lc, head[ms << 1], he[ms << 1], de[ms << 1], cnt, x[ms], y[ms], c[ms];

int l[ms], r[ms];

bool flag[ms];

struct in
{
    int to, ne, co;
}ter[ms << 5];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

map <pair<int, int>, int> vis, val;

queue <int> qwq;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), qwq.push(0), de[0] = 1;
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, qwq.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, ret;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            ret = dfs(to, min(fl, ter[i].co));
            if(ret)
            {
                fl -= ret, rt += ret, ter[i].co -= ret, ter[i ^ 1].co += ret;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

int px[10] = {0, 0, 1, -1, 1, -1}, py[10] = {1, -1, 0, 0, 1, -1};

int main()
{
    //freopen("4625.in", "r", stdin);
    //freopen("4625.out", "w", stdout);
    re(n); memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
    {
        re(x[i]), re(y[i]), re(lz), re(c[i]), x[i] -= lz, y[i] -= lz;
        c[i] *= ((x[i] + y[i]) % 3 == 0) ? 11 : 10, ans += c[i];
        pair <int, int> tmp = make_pair(x[i], y[i]);
        if(!vis.count(tmp))
            vis[tmp] = i, val[tmp] = c[i];
        else
            flag[i] = 1, val[tmp] += c[i];
        l[i] = ++ cnt, r[i] = ++ cnt;
    }
    t = ++ cnt;
    for(ri i = 1; i <= n; i ++)
    {
        if(flag[i])
            continue;
        if((x[i] + y[i] + bs) % 3 == 1)
            build(0, r[i], val[make_pair(x[i], y[i])]);
        else if((x[i] + y[i] + bs) % 3 == 0)
            build(l[i], r[i], val[make_pair(x[i], y[i])]);
        else
            build(l[i], t, val[make_pair(x[i], y[i])]);
    }
    for(ri i = 1; i <= n; i ++)
    {
        if(flag[i])
            continue;
        for(ri j = 0; j < 6; j ++)
        {
            int tx = x[i] + px[j], ty = y[i] + py[j], pos;
            if(!vis.count(make_pair(tx, ty)))
                continue;
            pos = vis[make_pair(tx, ty)];
            if((x[i] + y[i] + bs) % 3 == 1 && (tx + ty + bs) % 3 == 0)
                build(r[i], l[pos], 1e9 + 7);
            if((x[i] + y[i] + bs) % 3 == 0 && (tx + ty + bs) % 3 == 2)
                build(r[i], l[pos], 1e9 + 7);
        }
    }
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        ans -= dfs(0, 1e9 + 7);
    }
    printf("%d.%d", ans / 10, ans % 10);
}

luogu P3227 [HNOI2013]切糕
这个题可以说是非常经典了,由它引申出来的许多题目被称为切糕模型。
每次模型转化都是转的我一脸懵逼啊……根本想不到。这个题首先你要先把点转化成边,那么对于每一个纵轴,这样划分成R+1层,这些点分别是,0-1的边,1-2的边………………那么边权显然就是val[i][j][k]。
之后你要考虑|f(i,j)-f(x,y)| \leq D,换句话说只要让这个条件不成立的时候还存在一条流就行,因此向周围的单位降低D+1个高度建一条无限边。

// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 3e5 + 10;

int P, Q, R, D, s, t, tot = -1, head[ms], he[ms], de[ms], val[45][45][45];

queue <int> q;

int px[6] = {-1, 1, 0, 0}, py[6] = {0, 0, -1, 1};

struct in
{
    int to, ne, co;
}ter[ms << 1];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de)), q.push(0), de[0] = 1;
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, q.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, ret;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            ret = dfs(to, min(fl, ter[i].co));
            if(ret)
            {
                fl -= ret, rt += ret, ter[i].co -= ret, ter[i ^ 1].co += ret;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0;
    while(bfs())
        memcpy(he, head, sizeof(he)), rt += dfs(0, 1e9 + 7);
    return rt;
}

int main()
{
    re(P), re(Q), re(R), re(D), t = P * Q * (R + 1) + 5;
    memset(head, -1, sizeof(head));
    for(ri k = 1; k <= R; k ++)
        for(ri i = 1; i <= P; i ++)
            for(ri j = 1; j <= Q; j ++)
                re(val[i][j][k]);
    for(ri i = 1; i <= P; i ++)
        for(ri j = 1; j <= Q; j ++)
        {
            int pos = (i - 1) * Q + j + 1;
            build(0, pos, 1e9 + 7), build(P * Q * R + pos, t, 1e9 + 7);
            for(ri k = 1; k <= R; k ++)
                build(P * Q * (k - 1) + pos, P * Q * k + pos, val[i][j][k]);
        }
    for(ri i = 1; i <= P; i ++)
        for(ri j = 1; j <= Q; j ++)
            for(ri l = 0; l < 4; l ++)
            {
                int tx = i + px[l], ty = j + py[l];
                if(tx < 1 || tx > P || ty < 1 || ty > Q)
                    continue;
                for(ri k = D + 1; k <= R + 1; k ++)
                    build(P * Q * (k - 1) + (i - 1) * Q + j + 1,
                        P * Q * (k - D - 1) + (tx - 1) * Q + ty + 1, 1e9 + 7);
            }
    printf("%d\n", dinic());
    system("pause");
}

luogu P3749 [SHOI2017]寿司餐厅
这个题目又双叒验证了我是个sb……
首先很直接的,会想到d_{i,j}只需要和d_{i,j-1},d_{i+1,j}连边,但是具体怎么连我完全没想到啊…………………………
建图是这样的,因为是最大权闭合子图,所以要求所有的正权点和源点相连,边权则是正的点权,所有的负权点和汇点相连,这首先是没有任何问题的,然后所有的寿司向汇点连边,边权为ma_i^2,然后d_{i,j}只需要和d_{i,j-1},d_{i+1,j}各连条无限边,防止隔断,d_{i,i}要和他所对应的寿司编号连无限边,向汇点连接一条边权为a_i的边,这样就能使得你选择这个点的时候同时产生相应的费用了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int tot = -1, ans, t, he[30030], head[30030], n, m, a[110], d[110][110], de[30030];

int cnt, posa[1010], posd[110][110];

struct in
{
    int to, ne, co;
}ter[300030];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

queue <int> q;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, q.push(0);
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                q.push(to), de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0, tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he)); 
        while((tmp = dfs(0, 1e9 + 7)) > 0)
            rt += tmp;
    }
    return rt;
}

inline void init()
{
    re(n), re(m), t = ++ cnt; memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
    {
        re(a[i]);
        if(!posa[a[i]])
            posa[a[i]] = ++ cnt, build(cnt, t, m * a[i] * a[i]);
    }
    for(ri i = 1; i <= n; i ++)
        for(ri j = i; j <= n; j ++)
        {
            re(d[i][j]), posd[i][j] = ++ cnt;
            if(d[i][j] > 0)
                build(0, cnt, d[i][j]), ans += d[i][j];
            else
                build(cnt, t, - d[i][j]);
        }
    for(ri i = 1; i <= n; i ++)
        build(posd[i][i], posa[a[i]], 1e9 + 7), build(posd[i][i], t, a[i]);
    for(ri i = 1; i <= n; i ++)
        for(ri j = i + 1; j <= n; j ++)
            build(posd[i][j], posd[i][j - 1], 1e9 + 7), build(posd[i][j], posd[i + 1][j], 1e9 + 7);
}

int main()
{
    init(), printf("%d", ans - dinic());
}

luogu SP839 OPTM – Optimal Marks
这个题目又是一个经典的2选1问题啊……首先二进制,每一位都是独立的,意味着我可以按位考虑。那么显然我要拆分二进制,那么现在这个问题就变成了每一位上是0/1,如果两个数在这一位上不一样并且之间有边,就会产生1的代价。那么现在我们可以这么建图,先考虑所有点都没选择的情况,这个时候显然你都选0就好了……也就说是那些被钦定的点给我们产生了影响,因此你把和源点相连代表选1,和汇点相连代表选0,开始对于那些钦定的点按照这一位上是0还是1连接源点/汇点(流量都是无穷)。然后还是按照原图的关系建边,流量为1,这样在图上跑最小割,这个割就是不得不选的那些代价。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int T, n, m, K, head[550], he[550], t, ff[3030], tt[3030], tot, Mark[550], ans[550], pos[550];

int de[550];

bool flag[550];

struct in
{
    int to, ne, co;
}ter[100010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
}

queue <int> q;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, q.push(0);
    while(!q.empty())
    {
        int qaq = q.front(); q.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                q.push(to), de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline void dinic()
{
    int tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while((tmp = dfs(0, 1e9 + 7)) > 0);
    }
}

inline void init()
{
    tot = -1, memset(head, -1, sizeof(head)), memset(flag, 0, sizeof(flag));
}

void change(int no, int x)
{
    flag[no] = 1, ans[no] |= x;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
        if(ter[i].co && (!flag[ter[i].to]))
            change(ter[i].to, x);
} 

inline void solve()
{
    re(n), re(m);
    for(ri i = 1; i <= m; i ++)
        re(ff[i]), re(tt[i]);
    memset(ans, 0, sizeof(ans)); re(K);
    for(ri i = 1; i <= K; i ++)
        re(pos[i]), re(Mark[i]);
    t = n + 1;
    for(ri i = 30; i >= 0; i --)
    {
        init();
        for(ri j = 1; j <= m; j ++)
            build(ff[j], tt[j], 1), build(tt[j], ff[j], 1);
        for(ri j = 1; j <= K; j ++)//强制选1是连源点,选0连接汇点 
        {
            if(Mark[j] & (1 << i)) 
                build(0, pos[j], 1e9 + 7), build(pos[j], 0, 0);
            else
                build(pos[j], t, 1e9 + 7), build(t, pos[j], 0);
        }
        dinic(), change(0, 1 << i);
    }
    for(ri i = 1; i <= n; i ++)
        printf("%d\n", ans[i]);
}

int main()
{
    re(T);
    while(T --)
        solve();
}

luogu P4003 无限之环
这个题好tm牛逼……我不会自闭了。
这个题目首先看到闭合我头都炸了……妈耶这是啥情况,我不会用网络流构造闭合的回路啊,但是考虑这个题目,一个水管口只可能会和周围的另一个水管口配对……这也就意味着我们可以往二分图去考虑,首先对整个地图黑白染色,对每一个格子拆成上下左右四个点,之后按照水管口的方向建边不带费用流量都1。这样我们就做完不带修改的情况了。
那么待修改的呢?待修改意味着我们可以改变原有的水管方向去连向其他方向的点,也就说内部连边。看下代码+画图应该是能理解的……考虑5种图就好。每次费用就是我们需要修改到那个状态所花费的旋转次数。
有史以来写过最长的费用流。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, m, tot = -1, sum, head[10010], dis[10010], fl[10010], pre[10010], t, cnt, ans, Cost;

queue <int> qwq;

bool flag[10010];

struct in
{
    int to, ne, fl, co;
}ter[200020];

inline void build(int f, int l, int fl, int co)
{
    ter[++ tot] = (in){l, head[f], fl, co}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0, -co}, head[l] = tot;
}

int lx, id[2020][2020][4];

int px[4] = {-1, 0, 1, 0}, py[4] = {0, 1, 0, -1};

inline int lowbit(int x)
{
    return x & (-x);
}

inline int askbit(int x)
{
    int rt = 0;
    while(x)
        rt ++, x -= lowbit(x);
    return rt;
}

inline void link(int x, int y, int fl, int co, int col)
{
    if(col == 1)
        build(x, y, fl, co);
    else if(x == 0)
        build(y, t, fl, co);
    else
        build(y, x, fl, co);
}

inline void work(int x, int y, int ty, int dir, int col)
{
    int *A = id[x][y];
    if(ty == 1)//射线的时候 
    {
        link(0, A[dir], 1, 0, col), link(A[dir], A[(dir + 1) % 4], 1, 1, col);
        link(A[dir], A[(dir + 2) % 4], 1, 2, col), link(A[dir], A[(dir + 3) % 4], 1, 1, col);
    }
    else if(ty == 2)//两个接口挨着 
    {
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 1) % 4], 1, 0, col);
        link(A[dir], A[(dir + 2) % 4], 1, 1, col), link(A[(dir + 1) % 4], A[(dir + 3) % 4], 1, 1, col);
    }
    else if(ty == 3)//直线型的,不能转 
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 2) % 4], 1, 0, col);
    else if(ty == 4)//那种3个接口的 
    {
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 1) % 4], 1, 0, col), link(0, A[(dir + 2) % 4], 1, 0, col);
        link(A[dir], A[(dir + 3) % 4], 1, 1, col), link(A[(dir + 1) % 4], A[(dir + 3) % 4], 1, 2, col), link(A[(dir + 2) % 4], A[(dir + 3) % 4], 1, 1, col);
    }
    else//四个方向都有…… 
    {
        link(0, A[dir], 1, 0, col), link(0, A[(dir + 1) % 4], 1, 0, col);
        link(0, A[(dir + 2) % 4], 1, 0, col), link(0, A[(dir + 3) % 4], 1, 0, col);
    }
}

inline bool spfa()
{
    memset(flag, 0, sizeof(flag)), memset(fl, 0, sizeof(fl)), memset(dis, 63, sizeof(dis));
    dis[0] = 0, fl[0] = 1e9 + 7, qwq.push(0), flag[0] = 1;
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].fl && dis[to] > dis[qaq] + ter[i].co)
            {
                dis[to] = dis[qaq] + ter[i].co, fl[to] = min(fl[qaq], ter[i].fl), pre[to] = i;
                if(!flag[to])
                    qwq.push(to), flag[to] = 1;
            }
        }
        flag[qaq] = 0;
    }
    return fl[t] > 0;
}

inline void change()
{
    ans += fl[t], Cost += fl[t] * dis[t];
    for(ri i = t; i; i = ter[pre[i] ^ 1].to)
        ter[pre[i]].fl -= fl[t], ter[pre[i] ^ 1].fl += fl[t];
}

int main()
{
    re(n), re(m); memset(head, -1, sizeof(head)), t = ++ cnt;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            re(lx);
            for(ri k = 0; k < 4; k ++)
                id[i][j][k] = ++ cnt;
            if(lx == 1)
                work(i, j, 1, 0, (i + j) & 1);
            else if(lx == 2)
                work(i, j, 1, 1, (i + j) & 1);
            else if(lx == 3)
                work(i, j, 2, 0, (i + j) & 1);
            else if(lx == 4)
                work(i, j, 1, 2, (i + j) & 1);
            else if(lx == 5)
                work(i, j, 3, 0, (i + j) & 1);
            else if(lx == 6)
                work(i, j, 2, 1, (i + j) & 1);
            else if(lx == 7)
                work(i, j, 4, 0, (i + j) & 1);
            else if(lx == 8)
                work(i, j, 1, 3, (i + j) & 1);
            else if(lx == 9)
                work(i, j, 2, 3, (i + j) & 1);
            else if(lx == 10)
                work(i, j, 3, 1, (i + j) & 1);
            else if(lx == 11)
                work(i, j, 4, 3, (i + j) & 1);
            else if(lx == 12)
                work(i, j, 2, 2, (i + j) & 1);
            else if(lx == 13)
                work(i, j, 4, 2, (i + j) & 1);
            else if(lx == 14)
                work(i, j, 4, 1, (i + j) & 1);
            else if(lx == 15)
                work(i, j, 5, 0, (i + j) & 1);
            sum += askbit(lx);
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            if((i + j) & 1)
                for(ri k = 0; k < 4; k ++)
                {
                    int tx = i + px[k], ty = j + py[k];
                    if(tx < 1 || tx > n || ty < 1 || ty > m)
                        continue;
                    build(id[i][j][k], id[tx][ty][(k + 2) % 4], 1, 0);
                }
    while(spfa())
        change();
    printf("%d", (ans == (sum >> 1)) ? Cost : -1);
}

ZOJ 2314 Reactor Cooling
这算是一个上下界网络流的裸题,怎么证明我也不会……
先记下最低流量,同时记录每个点的流入-流出,然后每条边按照最大流量-最小流量建边。
同时设置一个源点一个汇点,设第i个点的流入-流出为a_i,那么如果a_i > 0,就建一条从源点到i的边,流量为a_i,否则就建一个流量为-a_i的,从i流到t的边。记录所有a_i大于0的和。
对这个图跑一边最大流,然后每条边的答案就是最低流量+反向边流量

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e5 + 10;

int T, n, m, t, la, lb, lc, ld, tot = -1, ans, Flow, head[ms], he[ms], de[ms], a[ms], in[ms], inv[ms];

struct edge
{
    int to, ne, co;
}ter[ms];

inline void build(int f, int l, int c)
{
    //cout << f << ' ' << l << ' ' << c << '\n';
    ter[++ tot] = (edge){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (edge){f, head[l], 0}, head[l] = tot;
}

queue <int> qwq;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, qwq.push(0);
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, qwq.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0, tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while((tmp = dfs(0, 1e9 + 7)) > 0)
            rt += tmp;
    }
    return rt;
}

int main()
{
    re(T);
    while(T --)
    {
        re(n), re(m), tot = -1, t = n + 1, Flow = 0; 
        memset(a, 0, sizeof(a)), memset(head, -1, sizeof(head));
        for(ri i = 1; i <= m; i ++)
        {
            re(la), re(lb), re(lc), re(ld);
            in[i] = lc, a[lb] += lc, a[la] -= lc;
            build(la, lb, ld - lc), inv[i] = tot;
        }
        for(ri i = 1; i <= n; i ++)
        {
            if(a[i] > 0)
                build(0, i, a[i]), Flow += a[i];
            else if(a[i] < 0)
                build(i, t, -a[i]);
        }
        ans = dinic(); 
        if(ans == Flow)
        {
            printf("YES\n");
            for(ri i = 1; i <= m; i ++)
                printf("%d\n", in[i] + ter[inv[i]].co);
        }
        else
            printf("NO\n");
    }
}

luogu P4311 士兵占领
听说这个题目可以上下界费用流什么的……反正打死我也不会。
说个简单点的办法,对于每行建个点,从源点流向他,边权是它最多不要的人数,对于每列也是类似,只不过你往汇点建边就是了。
把每个格子加在中间,然后向行和列建一条流量为1的边就是了。
无解就是某行某列都放上棋子也不满足条件。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

bool flag[110][110];

int n, m, t, k, cnt, lx, ly, ans, e[12000], a[110], b[110], he[12000], tot = -1, head[12000];

int rh[110], rl[110];

int de[12000];

struct in
{
    int to, ne, co;
}ter[100010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

queue <int> qwq;

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[0] = 1, qwq.push(0);
    while(!qwq.empty())
    {
        int qaq = qwq.front(); qwq.pop();
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && (!de[to]))
                de[to] = de[qaq] + 1, qwq.push(to);
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t || (!fl))
        return fl;
    int rt = 0, c;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(fl, ter[i].co));
            if(c)
            {
                fl -= c, rt += c, ter[i].co -= c, ter[i ^ 1].co += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int dinic()
{
    int rt = 0, tmp;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while((tmp = dfs(0, 1e9 + 7)) > 0)
            rt += tmp;
    }
    return rt;
}

int main()
{
    re(n), re(m), re(k), t = n + m + n * m + 1, cnt = n + m, ans = n * m - k;
    memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
        re(a[i]), rh[i] = m - a[i];
    for(ri i = 1; i <= m; i ++)
        re(b[i]), rl[i] = n - b[i];
    for(ri i = 1; i <= k; i ++)
        re(lx), re(ly), flag[lx][ly] = 1, rh[lx] --, rl[ly] --;
    for(ri i = 1; i <= n; i ++)
    {
        if(rh[i] < 0)
        {
            printf("JIONG!"); return 0;
        }
        build(0, i, rh[i]);
    }
    for(ri i = 1; i <= m; i ++)
    {
        if(rl[i] < 0)
        {
            printf("JIONG!"); return 0;
        }
        build(i + n, t, rl[i]);
    }
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            if(!flag[i][j])
                cnt ++, build(i, cnt, 1), build(cnt, j + n, 1);
    ans -= dinic(); printf("%d", ans);
}

【算法】根号系列

带修莫队

这个东西其实说起来挺简单的,除了带一个修改原理和莫队没啥区别,复杂度……应该是n^{\frac{5}{3}}级别的……搞得和kdtree差不多。实现的时候,我们往查询操作里记录目前这个查询操作时已经算到哪个修改操作了,然后剩下的地方就是普通莫队了。原理挺简单的……只要你会莫队,记得把块开成n^\frac{2}{3},开到根号可能你会被卡到生不如死。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 2e6 + 10; 

struct ask
{
    int l, r, pre, pos;
}q[ms];

struct cha
{
    int pos, v;
}c[ms];

int col[ms], su[ms], n, m, lx, ly, taq, tac, bas[ms], sz, ans, pri[ms];

char opt[10];

inline bool cmp(ask a, ask b)//左侧块是第一关键字,右侧块是第二关键字,上一次修改是第三关键字 
{ 
    return bas[a.l] == bas[b.l] ? (bas[a.r] == bas[b.r] ? a.pre < b.pre : a.r < b.r) : a.l < b.l;
}

inline void add(int x)
{
    su[x] ++;
    if(su[x] == 1)
        ans ++;
}

inline void del(int x)
{
    su[x] --;
    if(su[x] == 0)
        ans --;
}

inline void work(int no, int p)
{
    if(c[no].pos >= q[p].l && c[no].pos <= q[p].r)
    {
        su[col[c[no].pos]] --;
        if(su[col[c[no].pos]] == 0)
            ans --;
        su[c[no].v] ++;
        if(su[c[no].v] == 1)
            ans ++;
    }
    swap(col[c[no].pos], c[no].v);//这里将目前序列中的颜色和修改操作做交换的原因是,我们可能需要撤销操作,这个时候我们默认将序列的值改成修改操作存的颜色,减少代码量 
}

inline void solve()
{
    int l = 1, r = 0, no = 0;
    for(ri i = 1; i <= taq; i ++)
    {
        while(l < q[i].l) 
            del(col[l]), l ++;
        while(l > q[i].l) 
            l --, add(col[l]);
        while(r < q[i].r) 
            r ++, add(col[r]);
        while(r > q[i].r) 
            del(col[r]), r --;
        while(no < q[i].pre) 
            no ++, work(no, i);
        while(no > q[i].pre) 
            work(no, i), no --;
        pri[q[i].pos] = ans;
    }
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= n; i ++)
        re(col[i]);
    for(ri i = 1; i <= m; i ++)
    {
        scanf("%s", opt);
        if(opt[0] == 'Q')
            re(lx), re(ly), taq ++, q[taq] = (ask){lx, ly, tac, taq};
        else
            re(lx), re(ly), tac ++, c[tac] = (cha){lx, ly};
    }
    sz = pow(n, 0.666666666);
    for(ri i = 1; i <= n; i ++)
        bas[i] = i / sz + 1;
    sort(q + 1, q + 1 + taq, cmp);
    solve();
    for(ri i = 1; i <= taq; i ++)
        printf("%d\n", pri[i]);
} 

【算法】长链剖分/树剖复杂度正确性

luoguP3565 [POI2014]HOT-Hotels
首先先考虑比较暴力的做法,设f_{i,j}表示目前考虑到i号节点的子树,并且距离为j的点有多少。g_{i, j}表示目前在i子树内,有多少对(x,y)满足x,y,以及他们的lca距离为d,并且i到他们lca距离为d-j
最开始的时候,设目前处理到点x,先插入一个儿子y,这个时候显然x这个树里面得有俩点,那么对于这个点来说,它所产生的贡献就是g_{x,0}
接下来考虑这个dp的转移,对于f,g的转移,首先第一个显然的式子
f_{x,i} = f_{x,i}+f_{y,i-1}
这个式子确实非常显然,因为往上爬了一步距离也增大了。
第二个式子
g_{x,i} = g_{x,i}+g_{y,i+1}
这个式子就要稍微动点脑筋了,随着我们往上爬,我们距离lca越来越远了,d-j这个式子也在不断增大,d是定值,那么j不断缩小。
第三个式子
g_{x,i} = g_{x,i} + f_{x,i}f_{y,i-1}
这个式子也挺直观的,考虑目前我们把x作为lca,枚举子树内部的距离就是了。
那我们考虑这个新加入的蛾子对答案的贡献
ans = ans + f_{x,i-1}g_{y,i} + g_{x,i+1}f_{y,i}
这个式子的意思是什么,f_{x,i-1}g_{y,i}表示的是目前有两个点在子树y里面,那么从已经插了不少点的x里面取出距离xi-1的,因为还要从x走到yg_{x,i+1}f_{y,i}就和刚才情况相反,然后就是要从y走到x罢了
那么这个dp式子我们发现,对于前两个式子你只不过就是移动了一格,因此可以用指针的移动优化这个地方。用长链剖分的思想把这个地方剖开,所谓长链剖分,只不过是将树剖里面用来比较的关键字——子树大小,换成了子树最长深度而已,局限性更大了qwq。
这里简单口胡下树剖的复杂度正确性,众所周知树剖的复杂度是O(nlogn),但是这个东西为什么复杂度是有保证的呢,这要从树剖的性质说起,对于一个根节点为x子树内部,对于x的每一个轻儿子,其大小size_y \leq \frac{size_x}{2},这很简单,考虑反证法,如果存在这么一个y不满足这个不等式,那么它和重儿子大小之和一定大于size_{x},这显然是和初始条件不符合的。也就说,我们每次跨越轻重链,树的大小至少乘2,最多log_{2}n次我们就跳到树的最顶端了。
扯远了,这里我们分析长剖的复杂度为什么是正确的,因为你考虑,对于每个重链,我们只在它被跨越的地方进行了查询,换个说法的话就是我们每次枚举轻儿子的时候,才会访问以它开头的重链,那么对于每一个点,访问次数也不过就是常数级别了,那么复杂度自然而然是O(n)了。
长剖的代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e5 + 10;

lo n, cnt, ans, head[ms], lx, ly, fa[ms], son[ms], de[ms], mxde[ms], Pool[ms *20], tot = -1;

struct in
{
    lo to, ne;
}ter[ms << 1];

inline void build(lo f, lo l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

lo *f[ms], *g[ms], *No = Pool + 1;

void dfs1(lo no)
{
    de[no] = mxde[no] = 0;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no])
            continue;
        fa[to] = no, dfs1(to), mxde[no] = max(mxde[no], mxde[to] + 1);
        if(!son[no] || mxde[to] > mxde[son[no]])
            son[no] = to;
    }
}

void dfs2(int no)
{
    if(son[no])
    {
        f[son[no]] = f[no] + 1, g[son[no]] = g[no] - 1;
        dfs2(son[no]);
    }
    f[no][0] = 1, ans += g[no][0];//自己也算一个点
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == son[no] || to == fa[no])
            continue;
        f[to] = No, No += (mxde[to] + 1) << 1, g[to] = No, No += (mxde[to] + 1) << 1;
        dfs2(to);
        for(ri j = mxde[to]; j >= 0; j --)
        {
            if(j)
                ans += f[no][j - 1] * g[to][j];
            ans += g[no][j + 1] * f[to][j];
            g[no][j + 1] += f[no][j + 1] * f[to][j];//最后还是真香了……统一+1 
        }
        for(ri j = 0; j <= mxde[to]; j ++)
        {
            if(j)
                g[no][j - 1] += g[to][j]; 
            f[no][j + 1] += f[to][j]; 
        }
    } 
}

int main()
{
    re(n), memset(head, -1, sizeof(head));
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), build(lx, ly);
    dfs1(1), f[1] = No, No += (mxde[1] + 1) << 1, g[1] = No, No +=  (mxde[1] + 1) << 1, dfs2(1);
    printf("%lld", ans);
} 

但事实上,树剖也可以做这个题目,但是因为重链的长度不一定最长,所以每次你开空间还得按照最长链的长度开。比如有一个深度为3的重链,最长链是5,这个时候如果你不开大点空间你就gg了,而且好像菊花图可以卡死我树剖……具体复杂度不好算,但是起码常数要比长剖大。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e5 + 10;

lo n, cnt, ans, head[ms], lx, ly, fa[ms], son[ms], de[ms], mxde[ms], Pool[ms *20], tot = -1, sz[ms];

struct in
{
    lo to, ne;
}ter[ms << 1];

inline void build(lo f, lo l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

lo *f[ms], *g[ms], *No = Pool + 1;

void dfs1(lo no)
{
    de[no] = mxde[no] = 0, sz[no] = 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no])
            continue;
        fa[to] = no, dfs1(to), sz[no] += sz[to], mxde[no] = max(mxde[no], mxde[to] + 1);
        if(!son[no] || sz[to] > sz[son[no]])
            son[no] = to;
    }
}

void dfs2(int no)
{
    if(son[no])
    {
        f[son[no]] = f[no] + 1, g[son[no]] = g[no] - 1;
        dfs2(son[no]);
    }
    f[no][0] = 1, ans += g[no][0];//自己也算一个点
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == son[no] || to == fa[no])
            continue;
        f[to] = No, No += (mxde[to] + 1) << 1, g[to] = No, No += (mxde[to] + 1) << 1;
        dfs2(to);
        for(ri j = mxde[to]; j >= 0; j --)
        {
            if(j)
                ans += f[no][j - 1] * g[to][j];
            ans += g[no][j + 1] * f[to][j];
            g[no][j + 1] += f[no][j + 1] * f[to][j];//最后还是真香了……统一+1 
        }
        for(ri j = 0; j <= mxde[to]; j ++)
        {
            if(j)
                g[no][j - 1] += g[to][j]; 
            f[no][j + 1] += f[to][j]; 
        }
    } 
}

int main()
{
    freopen("4543.in", "r", stdin);
    freopen("4543.out", "w", stdout); 
    re(n), memset(head, -1, sizeof(head));
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), build(lx, ly);
    dfs1(1), f[1] = No, No += (mxde[1] + 1) << 1, g[1] = No, No +=  (mxde[1] + 1) << 1, dfs2(1);
    printf("%lld", ans);
} 

【luoguP4113】文理分科

首先一个比较直接的想法是,把源点看做文科,汇点看做理科,边权是文科/理科收益,问题转化为总边权-最小割。但是我们还需要考虑四周所有人选文/理的收益,因此我们再分别对于这四周的人建点,从起点到这个点,边权为收益,这个点再向周围那几个点建无限大的边,让他割不掉,这样必须割掉起点到这个新点的边或者把原来几个点到汇点的边割掉

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

const lo mo = 1e9 + 7;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 110;

struct in
{
    int to, ne, co;
}ter[1000010];

int n, m, las, ans, s, t, lx, tot = -1, q[100020], head[100020], de[100020], he[100020];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de)); int hh = 1, tt = 1;
    q[1] = s, de[s] = 1;
    while(hh <= tt)
    {
        int qaq = q[hh ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co && de[to] == 0)
                de[to] = de[qaq] + 1, q[++ tt] = to;
        }
    }
    return de[t] != 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int rt = 0;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to, c;
        if(ter[i].co && de[to] == de[no] + 1)
        {
            c = dfs(to, min(ter[i].co, fl));
            if(c > 0)
            {
                ter[i].co -= c, ter[i ^ 1].co += c, fl -= c, rt += c;
                if(fl <= 0)
                    return rt;
            }
        }
    }
    return rt;
}

inline int ask(int x, int y)
{
    return (x - 1) * m + y;
}

int px[4] = {-1, 0, 1, 0}, py[4] = {0, 1, 0, -1};

int main()
{
    re(n), re(m), t = las = n * m + 1; memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            int p = ask(i, j);
            re(lx), build(0, p, lx), ans += lx;
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            int p = ask(i, j);
            re(lx), build(p, t, lx), ans += lx;
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            int p = ask(i, j); las ++;
            re(lx), build(0, las, lx), build(las, p, 1e9 + 7), ans += lx;
            for(ri k = 0; k < 4; k ++)
                if(i + px[k] >= 1 && i + px[k] <= n && j + py[k] >= 1 && j + py[k] <= m)
                    build(las, ask(i + px[k], j + py[k]), 1e9 + 7);
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            int p = ask(i, j); las ++;
            re(lx), build(las, t, lx), build(p, las, 1e9 + 7), ans += lx;
            for(ri k = 0; k < 4; k ++)
                if(i + px[k] >= 1 && i + px[k] <= n && j + py[k] >= 1 && j + py[k] <= m)
                    build(ask(i + px[k], j + py[k]), las, 1e9 + 7);
        }
    int rt;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while((rt = dfs(0, 1e9 + 7)) > 0)
            ans -= rt;
    }
    printf("%d", ans);
}

【luoguP4560】[IOI2014]Wall 砖墙

这个题虽然实现挺好写的,但是我死活没想出来……
我们设置两个标记,一个add一个remove,当我们插入一个新的add标记的时候,如果比原来的add大就更新add,比原来的remove大就更新remove,插入一个新的remove标记就比他们小就更新。仔细一想就是三种情况,落在值域左侧/右侧/中间,根据add和remove性质就好

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

const lo mo = 1e9 + 7;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 8e6 + 5e4;

int add[ms], del[ms], n, m, opt, lx, ly, lz;

inline void down(int w)
{
    if(add[w])
    {
        add[w << 1] = (add[w << 1] < add[w]) ? add[w] : add[w << 1];
        del[w << 1] = (del[w << 1] < add[w]) ? add[w] : del[w << 1];
        add[w << 1 | 1] = (add[w << 1 | 1] < add[w]) ? add[w] : add[w << 1 | 1];
        del[w << 1 | 1] = (del[w << 1 | 1] < add[w]) ? add[w] : del[w << 1 | 1];
        add[w] = 0;
    }
    if(del[w] < 1e5 + 5)
    {
        add[w << 1] = (add[w << 1] > del[w]) ? del[w] : add[w << 1];
        del[w << 1] = (del[w << 1] > del[w]) ? del[w] : del[w << 1];
        add[w << 1 | 1] = (add[w << 1 | 1] > del[w]) ? del[w] : add[w << 1 | 1];
        del[w << 1 | 1] = (del[w << 1 | 1] > del[w]) ? del[w] : del[w << 1 | 1];
        del[w] = 1e5 + 5;
    }
}

void change(int w, int l, int r, int ll, int rr, int v, int p)
{
    if(l == ll && r == rr)
    {
        if(p == 1)
        {
            add[w] = (add[w] < v) ? v : add[w];
            del[w] = (del[w] < v) ? v : del[w];
        }
        else
        {
            add[w] = (add[w] > v) ? v : add[w];
            del[w] = (del[w] > v) ? v : del[w];
        }
        return;
    }
    int mid = (l + r) >> 1; down(w);
    if(rr <= mid)
        change(w << 1, l, mid, ll, rr, v, p);
    else if(ll > mid)
        change(w << 1 | 1, mid + 1, r, ll, rr, v, p);
    else
        change(w << 1, l, mid, ll, mid, v, p), change(w << 1 | 1, mid + 1, r, mid + 1, rr, v, p);
}

void ask(int w, int l, int r)
{
    if(l == r)
    {
        printf("%d\n", add[w]); return;
    }
    int mid = (l + r) >> 1; down(w);
    ask(w << 1, l, mid), ask(w << 1 | 1, mid + 1, r);
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= (n << 2); i ++)
        del[i] = 1e5 + 5;
    while(m --)
        re(opt), re(lx), re(ly), re(lz), lx ++, ly ++, change(1, 1, n, lx, ly, lz, opt);
    ask(1, 1, n);
}

【luoguP1445】[Violet]樱花

这个题目挺巧妙的,简单写下
n! = \frac{xy}{x+y} \\ xy – n!(x+y) = 0 \\ (n!)^2 + xy – n!(x + y) = (n!)^2 \\ (x-n!)(y – n!) = (n!)^2 \\ 设a= x-n!,b = y – n! \\ ab = (n!)^2
之后对n!分解质因数就好

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned long long ulo;

typedef long double ld;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e6 + 10;

const lo mo = 1e9 + 7;

bool flag[ms];

lo n, prime[ms], ans = 1, tot, ci[ms], las[ms];

int main()
{
    re(n), flag[1] = 1; int d;
    for(ri i = 2; i <= n; i ++)
    {
        if(flag[i] == 0)
            prime[++ tot] = i, las[i] = i;
        for(ri j = 1; j <= tot && (d = i * prime[j]) <= n; j ++)
        {
            flag[d] = 1, las[d] = prime[j];
            if(i % prime[j] == 0)
                break;
        }
    }
    for(ri i = 2; i <= n; i ++)
    {
        d = i;
        while(d != 1)
            ci[las[d]] ++, d /= las[d];
    }
    for(ri i = 2; i <= n; i ++)
        ans = ans * ((ci[i] * 2 + 1) % mo) % mo;
    printf("%lld", ans);
    system("pause");
}

【luoguP1110】[ZJOI2007]报表统计

这个题其实是个splay板子……不过我感觉我写麻烦了qwq。这个题给你三个操作,往原来的序列插入数,那就记录好所有元素对应原序列的哪个位置,插入的时候只要到的点位置和他一样或者比它小就向右走,否则向左。查询序列上挨着的最小值,那么我们建一个以序列位置前后作为关键字的splay就好了,查询整个序列最接近的两个元素差值,那再建一棵以权值为关键字的splay/线段树就好了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<utility>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned long long ulo;

typedef long double ld;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e6 + 10;

int root, sz[ms], sta[ms], lx, ta, ch[ms][2], pos[ms], val[ms], mi[ms], fa[ms], ls[ms], rs[ms];

int n, m, tot = 0, cnt = 0, ly;

inline bool dir(int x)
{
    return ch[fa[x]][1] == x;
}

inline void up(int x)
{
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
    ls[x] = (ch[x][0]) ? ls[ch[x][0]] : x;
    rs[x] = (ch[x][1]) ? rs[ch[x][1]] : x;
    mi[x] = min(min(mi[ch[x][0]], mi[ch[x][1]]), min(abs(val[x] - val[ls[ch[x][1]]]), abs(val[x] - val[rs[ch[x][0]]])));
}

inline void rotate(int x)
{
    int d = dir(x), f = fa[x], g = fa[f];
    fa[x] = g;
    if(g != 0)
        ch[g][dir(f)] = x;
    fa[f] = x, ch[f][d] = ch[x][d ^ 1];
    if(ch[x][d ^ 1])
        fa[ch[x][d ^ 1]] = f;
    ch[x][d ^ 1] = f; up(f), up(x);
}

inline void splay(int x)
{
    for(ri i; i = fa[x]; rotate(x))
        if(fa[i])
            rotate((dir(x) == dir(i)) ? i : x);
    root = x;
}

struct node
{
    int opt, p, v;
}poi[ms];

string s;

struct in
{
    int l, r, mi, mx, ans, num;
}ter[ms << 2];

inline void upseg(int w)
{
    ter[w].mx = max(ter[w << 1].mx, ter[w << 1 | 1].mx);
    ter[w].mi = min(ter[w << 1].mi, ter[w << 1 | 1].mi);
    ter[w].ans = min(min(min(ter[w << 1].ans, ter[w].ans), ter[w << 1 | 1].ans), abs(ter[w << 1].mx - ter[w << 1 | 1].mi));
    //cout << abs(ter[w << 1].mx - ter[w << 1 | 1].mi) << '\n';
}

inline void build(int w, int l, int r)
{
    ter[w].l = l, ter[w].num = 0, ter[w].ans = 1e9 + 7; ter[w].r = r;
    if(l == r)
    {
        ter[w].mi = 1e9 + 7, ter[w].mx = - 1e9 - 7; return;
    }
    int mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r); upseg(w);
}

inline void newnode(int c, int v, int f, int d)
{
    val[++ tot] = v, fa[tot] = f, pos[tot] = c, sz[tot] = 1, mi[tot] = 1e9 + 7;
    if(f != 0)
        ch[f][d] = tot;
    splay(tot);
}

inline void insert(int c, int v)
{
    int las = 0, d, rt = root;
    while(rt != 0)
        las = rt, d = (pos[rt] <= c) ? 1 : 0, rt = (pos[rt] <= c) ? ch[rt][1] : ch[rt][0];
    newnode(c, v, las, d);
}

void seginsert(int w, int l, int v)
{
    if(ter[w].l == ter[w].r)
    {
        ter[w].num ++, ter[w].mi = ter[w].mx = v, ter[w].ans = (ter[w].num > 1) ? 0 : 1e9 + 7; return;
    }
    int mid = (ter[w].l + ter[w].r) >> 1;
    if(v <= ter[w].mi)
        ter[w].ans = min(ter[w].ans, abs(ter[w].mi - v));
    if(v >= ter[w].mx)
        ter[w].ans = min(ter[w].ans, abs(ter[w].mx - v));
    if(l <= mid)
        seginsert(w << 1, l, v);
    else
        seginsert(w << 1 | 1, l, v);
    upseg(w);
}

int main()
{
    re(n), re(m); val[0] = mi[0] = 1e9 + 7;
    for(ri i = 1; i <= n; i ++)
        re(lx), sta[++ ta] = lx, poi[++ cnt] = (node){1, i, lx};
    for(ri i = 1; i <= m; i ++)
    {
        cin >> s;
        if(s == "INSERT")
            re(lx), re(ly), poi[++ cnt] = (node){1, lx, ly}, sta[++ ta] = ly;
        else if(s == "MIN_GAP")
            poi[++ cnt] = (node){2, 0, 0};
        else
            poi[++ cnt] = (node){3, 0, 0};
    }
    sort(sta + 1, sta + 1 + ta);
    ta = unique(sta + 1, sta + 1 + ta) - sta - 1;
    build(1, 1, ta);
    for(ri i = 1; i <= n + m; i ++)
    {
        if(poi[i].opt == 1)
        {
            int p = lower_bound(sta + 1, sta + 1 + ta, poi[i].v) - sta;
            insert(poi[i].p, poi[i].v), seginsert(1, p, poi[i].v);
            //cout << mi[root] << '\n';
        }
        else if(poi[i].opt == 2)
            printf("%d\n", mi[root]);
        else
            printf("%d\n", ter[1].ans);
    }
}