【算法】欧拉路&欧拉回路

欧拉路和欧拉回路是数学家欧拉在研究七桥问题的时候提出的,其具体历史这里就不多说了。
简单区分下欧拉回路和欧拉路
欧拉路就是说所有的边走且只走一次,欧拉回路就是在欧拉路的基础上更进一层,不仅所有的边都走一次,最后还回到了起点
其实就是我们熟知的一笔画呗
这个算法其实比较结论。对于有向图和无向图我们只需要找准条件随便写一下就行了,混合图……反正我是没看懂23333333
有向图存在欧拉路:所有顶点出度等于入度(且存在欧拉回路);或者是出两点外,所有点出度等于入度,这两个点中,出度大的为起点,入度大的为终点。
无向图存在欧拉路:所有点度数均为偶数(且存在欧拉回路);或有两个奇数点,他们一定是终点和起点
代码实现的话直接dfs就好啦。反正是一笔画,所以只要能走就一直走就行,记住dfs的时候要修改边权
luogu P1341 无序字母对

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

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 ++;
}

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;
}

int n, dis[1010][1010], d[1010];

char s[1010], ans[1010], ss[1010];

void dfs(int no)
{
    for(ri i = 0; i < 52; i ++)
        if(dis[no][i])
            dis[no][i] = dis[i][no] = 0, dfs(i);
    ans[n --] = ss[no];
}

int main()
{
    re(n);
    for(ri i = 0; i < 26; i ++)
        ss[i] = 'A' + i;
    for(ri i = 26; i < 52; i ++)
        ss[i] = 'a' + i - 26;
    for(ri i = 1; i <= n; i ++)
    {
        scanf("%s", s + 1);
        int lx, ly;
        if(s[1] >= 'A' && s[1] <= 'Z')
            lx = s[1] - 'A';
        else
            lx = s[1] - 'a' + 26;
        if(s[2] >= 'A' && s[2] <= 'Z')
            ly = s[2] - 'A';
        else
            ly = s[2] - 'a' + 26;
        dis[lx][ly] = dis[ly][lx] = 1, d[lx] ++, d[ly] ++;
    }
    int num = 0, sta = -1;
    for(ri i = 0; i < 52; i ++)
        if(d[i] & 1)
        {
            num ++;
            sta = (sta == -1) ? i : sta;
        }   
    bool f = 0;
    if((num != 0 && num != 2) || f != 0)
    {
        printf("No Solution"); return 0;
    }
    if(sta == -1)
    {
        for(ri i = 0; i < 52; i ++)
            if(d[i] != 0)
            {
                sta = i; break;
            }
    }
    dfs(sta);
    if(n > 0)
    {
        printf("No Solution"); return 0;
    }
    printf("%s", ans);
}

【算法】最大权闭合子图

日常安利两篇文章[网络流]最大权闭合图(转载)
hiho 第119周 最大权闭合子图
闭合图是啥,就是说所有的点连出去的边都指向我们所选的点集,这就是闭合图
那么我们现在要求一个最大权的闭合图,可以通过网络流来解决
我们首先转化模型,我们将所有的正权点与源点s相连,所有的负权点与汇点t相连,原来的图流量我们都换成无穷大
首先我们来证明这么一张图上最小割是简单割
简单割的定义就是割上每条边都与起点或者汇点相连
那么首先我们可以将与起点相连的边都割掉,这些边里面没有无穷大的边,当然这种割法并不一定是最小割
那么对于最小割,它付出的代价一定小于等于刚才那种方案的代价,这就要求最小割不存在无穷大的边。因此,最小割所有的边都会与起点或者终点相连
第二步,我们要证明简单割即为闭合图,闭合图即为简单割。
如果闭合图不是简单割,必然存在一条无穷大的边,那么这个图还保持联通,与割断不相合
如果简单割不是闭合图,那么一定有无穷大的边连向另一个集合,那么这个图也是不连通的,不符合前提
那么到了最关键的一步,最大权闭合子图的权值w = 所有正权点权值之和w0 – 最小割c
证明
设最小割将点集分为两半,有源点的为点集s,有汇点的为点集t,那么最小割容量c = t内原图正权点点权之和 + s中负权点点权绝对值之和,w = s内所有正权点点权之和 – s内所有负权点绝对值之和
所以c + w = 所有正权点点权和
所以w = 所有正权点点权和
例题
luogu P2762 太空飞行计划问题
这个题就是一个比较典型的最大权闭合子图问题,我们可以将实验和仪器划分到两个集合,分别以点权的绝对值向起点/汇点建边,我们割掉与起点相连的边,说明这个实验不够优,不足以让我们去购买相应的仪器,我们割掉与终点相连的边,就说明仪器的代价要小于收益

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int
using namespace std;

const int mo = 1000000007;

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 ++;
}

char a;

bool flag;

inline void re(int &x)
{
    x = 0;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
    if(a == '\r' || a == '\n')
        flag = 1;
}

int n, m, t, he, ta, lx, ans, tot = -1;

int q[500], v1[110], v2[110], de[110], head[110], hea[110];

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

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[he = ta = 0] = 0, de[0] = 1;
    while(he <= ta)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[to] = de[qaq] + 1, q[++ ta] = to;
        }
    }
    return de[t] > 0;
}

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

int main()
{
    memset(head, -1, sizeof(head));
    re(m), re(n), t = n + m + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(v1[i]), ans += v1[i], flag = 0, build(0, i, v1[i]);
        while(!flag)
            re(lx), build(i, lx + m, mo);
    }
    for(ri i = 1; i <= n; i ++)
        re(v2[i]), build(i + m, t, v2[i]);
    while(bfs())
    {
        for(ri i = 0; i <= t; i ++)
            hea[i] = head[i];
        while(int ret = dfs(0, mo))
             ans -= ret;
    }
    for(ri i = 1; i <= m; i ++)
        if(de[i] > 0)
            printf("%d ", i);
    printf("\n");
    for(ri i = 1; i <= n; i ++)
        if(de[i + m] > 0)
            printf("%d ", i);
    printf("\n%d", ans);
}

luogu P2805 [NOI2009]植物大战僵尸

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

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 ++;
}

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

int h, t, ta, n, m, lx, ly, lz, tot = -1, ans, pri;

int q[1010], de[1010], num[1010], v[1010], he[1010], head[1010];

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

bool flag[1010];

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

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

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

inline void init()
{
    h = 1;
    for(ri i = 1; i <= n * m; i ++)
        if(num[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 1;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to; num[to] --;
            if(num[to] == 0)
                q[++ t] = to;
        }
    }
    t = 0;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 0;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to;
            if(flag[to] == 1)
                q[++ t] = to;
        }
    } 
    tot = -1, t = n * m + 1;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 1)
        {
            if(v[i] > 0)
                ans += v[i], rebuild(i, t, v[i]);
            else
                rebuild(0, i, - v[i]);
            for(ri j = he[i]; j >= 0; j = edge[j].ne)
            {
                int to = edge[j].to;
                if(flag[to] == 1)
                    rebuild(i, to, 1e9 + 7);
            }
        }
}

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

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int lin = 0;
    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 > 0)
        {
            int rt = dfs(to, min(fl - lin, ter[i].co));
            ter[i].co -= rt, ter[i ^ 1].co += rt, lin += rt;
            if(lin == fl)
                return lin;
        }
    }
    return lin;
}

/*
这个题其实是一个比较板子的最大权闭合子图,但是之前没有认真了解过
闭合子图:图内所有点的出边,都指向图内所有点构成的集合中的一个点
这个东西我们可以转化成原图正权点点权之和减去新图最小割
新图怎么建
我们现在考虑植物之间的关系,它是由一堆保护和被保护这样的东西组成的
那么对于一对这样的关系,我们从保护植物向被保护的植物建边
然后跑拓扑排序,将图中的环和受环庇护的植物去掉
那么现在就剩下了一堆一定可以被删除掉的植物
那么我们就需要考虑删除哪些植物划算哪些植物不划算了
现在还是按照保护和被保护的关系建图,流量无限 
但是我们加入一个汇点和一个源点,所有正权点向汇点连边,流量为点权
负权点向源点建边,流量为点权的绝对值
然后跑最小割,答案就是所有正点点权之和减去最小割
至于为什么这么干 我们现在最小割只会割两种边 ,与起点相连和与终点相连的边
那么对于割掉与起点有关系的点,就表示我们现在决定割掉某个植物获取更大的利益
割掉与终点有关系的点,就表示我们现在决定不要某种植物的点权来减少损失 
*/ 

int main()
{
    //freopen("qwq.out", "w", stdout);
    re(n), re(m), memset(he, -1, sizeof(he)), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            re(lx), v[ask(i, j)] = lx, re(lz);
            while(lz --)
                re(lx), re(ly), lx ++, ly ++, build(ask(i, j), ask(lx, ly), 1);
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = m; j > 1; j --)
            build(ask(i, j), ask(i, j - 1), 1);
    init(); 
    while(bfs())
        memcpy(he, head, sizeof(he)), ans -= dfs(0, 1e9 + 7);
    printf("%d", ans);
    return 0;
} 

【洛谷P4382】劈配

……no zuo no die,考场就想到正解了,但是不敢打,结果一轮就gg了,也算是报应qwq,也许以后我应该大胆一点了……
这个题目第一问我们可以动态建边,贪心的做一遍就好,并在匹配的同时记录剩余网络,便于处理第二问
第二问如果本来就满足期望值就不管,否则二分第几名才能满足这个人要求,然后每次用(二分答案-1)的剩余网络+重新建边,跑一下就可以了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

typedef long long lo;

typedef long double ld;

const lo mo = 1000000007;

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 ++;
}

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')    
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, m, e, t, c, tot = -1, te, he, lx;

int pos[220][220][220], ta[220], lin[220], head[880], ta1[220], ta2[220];

int q[1010], de[1010], fir[220][880], a2[220], num[220], hop[220];

struct in
{
    int to, ne, co;
}ter[80080], wb[220][80080];

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[te = he = 0] = 0, de[0] = 1;
    while(he <= te)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[to] = de[qaq] + 1, q[++ te] = to;
        }
    }
    return de[e] > 0;
}

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

int main()
{
    re(t), re(c);
    for(ri ci = 1; ci <= t; ci ++)
    {
        memset(pos, 0, sizeof(pos)), memset(fir, -1, sizeof(fir));
        memset(head, -1, sizeof(head)), memset(ta, 0, sizeof(ta));
        memset(ta2, 63, sizeof(ta1)), memset(lin, 63, sizeof(lin));
        re(n), re(m), e = n + m + 5, tot = -1;
        for(ri i = 1; i <= m; i ++)
            re(num[i]), build(i + n, e, num[i]);
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= m; j ++)//pos[i][j][0]表示第i个人第j志愿一共选了多少导师 
                re(lx), pos[i][lx][++ pos[i][lx][0]] = j, lx = (lx == 0) ? 1000000007 : lx, ta2[i] = min(ta2[i], lx);
        for(ri i = 1; i <= n; i ++)//第m + 1志愿设为m + 1位导师(没匹配成功) 
            re(hop[i]), pos[i][m + 1][++ pos[i][m + 1][0]] = m + 1;
        for(ri i = 0; i <= e; i ++)//fir[i][j]表示当前匹配到i号学员的head[j] 
            fir[0][i] = head[i];
        for(ri i = 0; i <= tot; i ++)//wb[i][j]表示当前匹配到i号学员,第j条边的情况,记录残余网络 
            wb[0][i] = ter[i];
        ta1[0] = tot;
        for(ri i = 1; i <= n; i ++)
        {
            build(0, i, 1);
            int ll = tot;
            while(++ ta[i] <= m + 1)//动态加边 
            {
                head[i] = ll;//每回合将之前这个点连的边基本踢掉,只留从它到起点的 
                if(pos[i][ta[i]][0] == 0)
                    continue;
                for(ri j = 1; j <= pos[i][ta[i]][0]; j ++)//建边 
                    build(i, pos[i][ta[i]][j] + n, 1);
                if(bfs())//如果可以增广,说明可以匹配了 
                {
                    while(int ret = dfs(0, 1000000007));
                    break;
                }
            }
            for(ri j = 0; j <= e; j ++)//记录每次的残余网络 
                fir[i][j] = head[j];
            for(ri j = 0; j <= tot; j ++)
                wb[i][j] = ter[j];
            ta1[i] = tot;//记录到此时用的边 
        }
        for(ri i = 1; i <= n; i ++)
            ta[i] = (ta[i] > m + 1) ? m + 1 : ta[i], printf("%d ", ta[i]);
        printf("\n");
        for(ri i = 1; i <= n; i ++)//然后接下来二分答案,第几名才能满足第i个人的要求 
        {
            int lia = 0;
            if(ta[i] <= hop[i])
                a2[i] = 0;
            else
            {
                int l = 1, r = i - 1, mid;
                while(l <= r)
                {
                    mid = (l + r) >> 1;
                    for(ri j = 0; j <= e; j ++)//替换成原来的剩余网络 
                        head[j] = fir[mid - 1][j];
                    for(ri j = 0; j <= ta1[mid - 1]; j ++)
                        ter[j] = wb[mid - 1][j];
                    int rr = tot;
                    build(0, i, 1);
                    for(ri j = 1; j <= hop[i]; j ++)//然后把期望值之前的志愿连边就行,任意一个能匹配就可以 
                        for(ri k = 1; k <= pos[i][j][0]; k ++)
                            build(i, pos[i][j][k] + n, 1);
                    bool fl = bfs() && dfs(0, 1000000007);
                    if(fl == 1)
                        l = mid + 1, lia = mid;
                    else
                        r = mid - 1;
                    tot = rr;
                }
                a2[i] = i - lia;
            }
        }
        for(ri i = 1; i <= n; i ++)
            printf("%d ", a2[i]);
        printf("\n");
    }
    return 0;
}

【洛谷P4126】最小割

……时间有点紧,就不写了qwq,要写的都在代码里了qwq

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

typedef long long lo;

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 ++;
}

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

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

int n, m, s, t, he, ta, lx, ly, tt, lz, ret, ans, cnt, ci, tot = -1;
int lin[20020], low[20020], sta[20020], dfn[20020], scc[20020], q[20020], de[20020], head[4020];

bool flag[20020];

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

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

int dfs(int no, int fl) 
{
    if(no == t)
        return fl;
    int used = 0;
    for(ri i = lin[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to, ret;
        if(de[to] == de[no] + 1)
        {
            ret = dfs(to, min(ter[i].co, fl - used));
            ter[i].co -= ret, ter[i ^ 1].co += ret;
            if(ter[i].co)//优化,边权为0的边就不需要跑了 
                lin[no] = i;
            used += ret;
            if(used == fl)//能跑到这里的最大流量,一起返回,减少递归次数 
                return fl;
        }
    }
    if(used == 0)   
        de[no] = 0;
    return used;
}

void tarjan(int no)//把剩余网络缩点 
{
    dfn[no] = low[no] = ++ ci, sta[++ tt] = no, flag[no] = 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co)
        {
            if(dfn[to] == 0)
                tarjan(to), low[no] = (low[no] > low[to]) ? low[to] : low[no];
            else if(flag[to])
                low[no] = (low[no] > dfn[to]) ? dfn[to] : low[no];
        }
    }
    if(low[no] == dfn[no])
    {
        cnt ++;
        while(233)
        {
            int qaq = sta[tt --]; scc[qaq] = cnt, flag[qaq] = 0;
            if(qaq == no)
                break;
        }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    re(n), re(m), re(s), re(t);
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    while(bfs())//先dinic,跑出最小割 
    {
        for(ri i = 1; i <= n; i ++)//应该是优化qwq,用lin存储每次还有价值值得去跑的边开头qwq

            lin[i] = head[i];
        ans += dfs(s, 1000000007);
    }
    for(ri i = 1; i <= n; i ++)
        if(!dfn[i])
            tarjan(i);
    for(ri i = 0; i <= tot; i += 2)
    {
        if(ter[i].co > 0)
        {
            puts("0 0"); continue;
        }
        int f = ter[i].fr, to = ter[i].to;
        if(scc[f] != scc[to])//如果说这个边之前是满流边而且连接着两个不同的集合,那么说明一定出现在最小割的某个方案里
            printf("1 ");//可以这么想,我们有很多种方案可以把这些缩过的点分成两半,那么这些跨集合的点是一定需要这些边来切开的(但不是必须每次使用) 
        else
            printf("0 ");
        if(scc[f] == scc[s] && scc[to] == scc[t])//如果这个边连接起点和终点,那么必须切断否则还联通 
            puts("1");
        else
            puts("0");
    }
}

【HDU4677】Graph

这个题调的我真绝望(这个题解的公式也写的我很绝望),写了三遍调了一天才过qwq,蓝瘦香菇
这个题利用了根号分治的思想,我们把按照入度把边分类,所有出入度之和大于\(\sqrt[2]{m}\)的点作为重点,剩下的点作为轻点
那么设重点个数为\(x\),所以\(\frac{x*\sqrt{m}}{2} \lt m\) ,所以\(x \lt 2 * \sqrt{m}\)
那么我们将单次修改和查询的时间复杂度都变为了\(n\sqrt{n}\),就可以接受了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int
#define F(i,a,b) for(ri i=a;i<=b;i++)  

using namespace std;

typedef long long lo;

const int s = 100010;

char lin, qwq[20];

lo n, m, du[s], tp[s], col[s], ans[5], su[s][2], head[s][2], q, lx, ly, ci, tot, cnt, sz;

struct in
{
    lo to, ne, co;
}ter[s << 2];

struct es
{
    lo f, l, c;
    inline bool operator < (const es &a) const
    {
        if(f == a.f)
            return l < a.l;
        return f < a.f;
    }
}ing[s];

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 ++;
}

inline void re(lo &x)
{
    x = 0;
    char a = getchar(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = getchar();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

inline void rechar(char &x)
{
    x = getchar();
    while(x < 'A' || x > 'Z')
        x = getchar();
}

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

int main()
{
    while(~ scanf("%lld%lld", &n, &m))
    {
        tot = cnt = 0;
        for(ri i = 1; i <= n; i ++)
            re(col[i]);
        for(ri i = 0; i < m; i ++)
        {
            re(ing[i].f), re(ing[i].l), re(ing[i].c);
            if(ing[i].f > ing[i].l)
                swap(ing[i].f, ing[i].l);
        }
        sort(ing, ing + m);
        for(ri i = 0, j; i < m; i = j)//合并重边 
        {
            for(j = i + 1; ing[j].f == ing[i].f && ing[j].l == ing[i].l && j < m; j ++)
                ing[i].c += ing[j].c;
            ing[cnt ++] = ing[i];
        }
        sz = sqrt(cnt << 1);//按照根号分治 
        memset(du, 0, sizeof(du)), memset(head, -1, sizeof(head));
        for(ri i = 0; i < cnt; i ++)
            du[ing[i].f] ++, du[ing[i].l] ++;
        for(ri i = 1; i <= n; i ++)//判断所有出入大于m^(1/2)的点,因为设点的个数为X,那么x * m ^ (1 / 2) / 2 < m,所以x < 2 * sqrt(m),这样时间复杂度就降下来了 
            tp[i] = (du[i] >= sz);
        for(ri i = 0; i < cnt; i ++)//重新建没有重边的图 
        {
            lo x = ing[i].f, y = ing[i].l, c = ing[i].c;
            if(tp[x])//重点(度数大于sqrt(m))是被连的,轻点是连出去的 
                build(1, y, x, c);
            else
                build(0, x, y, c);
            if(tp[y])
                build(1, x, y, c);
            else
                build(0, y, x, c);
        }
        memset(ans, 0, sizeof(ans)), memset(su, 0, sizeof(su));
        for(ri i = 0; i < cnt; i ++)
        {
            lo f = ing[i].f, l = ing[i].l, c = ing[i].c;
            if(tp[f])//维护每个点与它相连的两种点所形成的边的边权 
                su[f][col[l]] += c;
            if(tp[l])
                su[l][col[f]] += c;
            ans[col[f] + col[l]] += c;
        }
        printf("Case %d:\n", ++ ci);
        re(q);
        while(q --)
        {
            scanf("%s", qwq), re(lx);
            if(qwq[0] == 'A')
                re(ly), printf("%lld\n", ans[lx + ly]);
            else
            {
                col[lx] ^= 1;
                if(tp[lx])//如果这个点是重点,直接修改
                    for(ri i = 0; i <= 1; i ++)
                        ans[(col[lx] ^ 1) + i] -= su[lx][i], ans[col[lx] + i] += su[lx][i];
                else//否则对与自己相连的轻点修改(不超过sqrt(m)) 
                    for(ri i = head[lx][0]; i > 0; i = ter[i].ne)
                    {
                        int to = ter[i].to;
                        ans[(col[lx] ^ 1) + col[to]] -= ter[i].co;
                        ans[col[lx] + col[to]] += ter[i].co;
                    }
                for(ri i = head[lx][1]; i > 0; i = ter[i].ne)//每次都要修改与自己相连的终边 
                {
                    int to = ter[i].to;
                    su[to][col[lx] ^ 1] -= ter[i].co, su[to][col[lx]] += ter[i].co;//减去原来的方案,加上现在的方案 
                }
            }
        } 
    }
}

【codeforces 160D】Edges in MST

这个题……emmmm有个小地方挺难调的
大体思想就是我们按照权值从小到大排序,比较所有权值相同的边,判断他们与最小生成树的关系。我们用并查集维护点所在的联通块,当一个边的两端点均在同一个联通块的时候,说明之前已经有更小的边使这个联通块联通了,那么这个边肯定不在最小生成树上。如果这些新加入的边形成环,则说明他们可以互相替换,可能出现在最小生成树上。如果没有成环,说明不可替代,一定在最小生成树上。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ri register int

using namespace std;

const int s = 100010;

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 ++;
}

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, m, tot, cnt, dfn[s], ans[s], head[s], fa[s];

struct es
{
    int f, l, c, pos;
    inline bool operator < (const es &a) const
    {
        return c < a.c;
    }
}ing[s];

struct in
{
    int to, ne, pos;
}ter[s << 1];

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

int find(int x)
{
    return (fa[x] == x) ? x : fa[x] = find(fa[x]);
}

int dfs(int no, int f)//找环,注意这里记录上次走过的边而不是点 
{
    int lowno = dfn[no] = ++ cnt;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(dfn[to] == 0)
        {
            int lowto = dfs(to, i);
            lowno = (lowno > lowto) ? lowto : lowno;
            if(lowto > dfn[no])
                ans[ter[i].pos] = 0;
        }
        else if(dfn[to] < dfn[no] && i != (f ^ 1))
            lowno = (lowno > dfn[to]) ? dfn[to] : lowno;
    }
    return lowno;
}

inline void up(int x, int y)//并查集合并 
{
    x = find(x), y = find(y);
    if(x == y)
        return;
    fa[x] = y;
}

int main()
{
    re(n), re(m);
    for(ri i = 1; i <= m; i ++)
        re(ing[i].f), re(ing[i].l), re(ing[i].c), ing[i].pos = i;
    for(ri i = 1; i <= n; i ++)
        fa[i] = i;
    sort(ing + 1, ing + 1 + m);
    for(ri i = 1; i <= m; i ++)
    {
        ri j = i;
        while(j + 1 <= m && ing[j + 1].c == ing[j].c)
            j ++;
        tot = -1, cnt = 0;
        for(ri k = i; k <= j; k ++)
        {
            ing[k].f = find(ing[k].f), ing[k].l = find(ing[k].l);//我们用并查集合并联通块 
            head[ing[k].f] = head[ing[k].l] = -1, dfn[ing[k].f] = dfn[ing[k].l] = 0;//每次重新建图,之前的联通块已经被压成一个点 
        }
        for(ri k = i; k <= j; k ++)
        {
            int x = ing[k].f, y = ing[k].l, id = ing[k].pos;
            if(x == y)//如果这两个点之前已经合并,那么说明有更小的边使他们联通,这个边就一定不会出现在最小生成树里 
            {
                ans[id] = 2; continue;
            }
            ans[id] = 1, build(x, y, id);//否则就可能出现在最小生成树 
        }
        for(ri k = i; k <= j; k ++)
            if(!dfn[ing[k].f])//搜索,判断这些边是否能成环,如果能成环,说明这些边都是可能被替代的 
                dfs(ing[k].f, -1);
        for(; i <= j; ++ i)//合并 
            up(ing[i].f, ing[i].l);
        i --;
    }
    for(ri i = 1; i <= m; i ++)
    {
        if(ans[i] == 2)
            puts("none");
        else
            puts(ans[i] ? "at least one" : "any");
    }
}

【bzoj1143】祭祀

这个题很容易就可以想到,先判断各个点之间的联通情况,然后把点拆成作为出发点的情况和作为终点的情况,那么枚举每一个点,把所有能从他出发到达的点与他建边,然后二分图最大匹配,完了
洛谷有人在这个基础上又加了两个要求……然而我太菜了,只能解决第一个新加要求emmmmm

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ri register int

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 ++;
}

inline void re(int &x)
{
    x = 0;
    char a = getchar(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = getchar();
    }
    while(a >= '0' && a <= '9')
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

int n, m, lx, ly, q[200100], he, ta, de[4200], mmp[500][500], f = -1;

int head[4200], tot = -1, s = 0, t, ret, ans, a1[500], a2[500];

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

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

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

inline int dfs(int d, int fl)
{
    if(d == t)
        return fl;
    for(ri i = head[d]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(f > 0 && (to == f || to == f + n))
            continue;
        if(de[to] == de[d] + 1 && ter[i].co > 0)
        {
            int r = dfs(to, min(fl, ter[i].co));
            if(r > 0)
            {
                ter[i ^ 1].co += r, ter[i].co -= r; return r;
            }
        }
    }
    return 0;
}

inline void init()
{
    memset(head, -1, sizeof(head)), tot = -1;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= n; j ++)
            if(mmp[i][j] == 1)
                build(i, j + n);
    for(ri i = 1; i <= n; i ++)
        build(0, i), build(i + n, t);/*然后按照网络流的常规操作,把一个点拆成它作为出发点和作为终点的情况,二分图最大匹配*/ 
}

int main()
{
    re(n), re(m);
    t = (n << 1) + 1;
    for(ri i = 1; i <= m; i ++) 
        re(lx), re(ly), mmp[lx][ly] = 1;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= n; j ++)
            for(ri k = 1; k <= n; k ++)
                if(mmp[i][k] + mmp[k][j] == 2)//处理出所有点之间的到达关系 
                    mmp[i][j] = 1;
    init();
    while(bfs())
        while(ret = dfs(0, 1000000007))
            ans += ret; 
    printf("%d\n", n - ans);
}

【洛谷P2403】所驼门王的宝藏

这个题贼恶心,首先很容易就可以想到缩环跑个dp,但是这个题难点在于,你要怎么建图,才能避免一行全是1这种门或者一列全是2这种情况,防止mle
所以我们将每一行中的1以及每一列当中2按行/列连成一个大环,然后再从这个环上建边即可,至于3,我们开一个二维map然后判断下它四周的点,然后建边即可
不知道为啥,洛谷的评测姬吼像对stl并不友好,我在bzoj上时间空间均无压力,但是到了洛谷各种被卡空间卡时间,最后手写了个栈,开了个真2维map(因为两个维度上都在动态开点),把一堆中间变量全加上register,才算是在洛谷稳定通过

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector> 
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#define ri register int

using namespace std;

const int mx = 1000000007;

typedef long long lo;

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

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 3) + (x << 1) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

bool flag[100010];

int tail, he[100010], head[100010], sta[100010];

int dfn[100010], scc[100010], v[100010], low[100010];

int n, r, c, ta, cnt, ans, tot = -1, x[100010], y[100010], t[100010];

vector <int> h[1000010], l[1000010];

map <int, map <int, int> > mmp;

int dx[8] = {0, 0, -1, -1, -1, 1, 1, 1}, dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};

struct in
{
    int fr, to, ne;
}ter[1000020], es[1000020];

int dp[100010];

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

void DP(ri no)
{
    flag[no] = 1;
    for(ri i = he[no]; i >= 0; i = es[i].ne)
    {
        ri to = es[i].to;
        if(flag[to] == 0)
            DP(to);
        dp[no] = max(dp[no], dp[to]);
    }
    dp[no] += v[no];
    ans = max(ans, dp[no]);
}


void dfs(ri no)
{
    dfn[no] = low[no] = ++ ta;
    sta[++ tail] = no;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        ri to = ter[i].to;
        if(dfn[to] == 0)
            dfs(to), low[no] = low[no] > low[to] ? low[to] : low[no];
        else if(scc[to] == 0)
            low[no] = low[no] > dfn[to] ? dfn[to] : low[no]; 
    }
    if(dfn[no] == low[no])
    {
        cnt ++;
        while(233)
        {
            ri qaq = sta[tail --];
            scc[qaq] = cnt, v[cnt] ++;
            if(qaq == no)
                break;
        }
    }
}

inline void rebuild(ri f, ri l)
{
    if(f == l)
        return;
    es[++ tot] = (in){f, l, he[f]}, he[f] = tot;
}

int main()
{
    memset(head, -1, sizeof(head));
    re(n), re(r), re(c);
    for(ri i = 1; i <= n; i ++)
        re(x[i]), re(y[i]), re(t[i]), mmp[x[i]][y[i]] = i, h[x[i]].push_back(i), l[y[i]].push_back(i);
    for(ri i = 1; i <= r; i ++)
    {
        int no = 0;
        for(ri j = 0; j < h[i].size(); j ++)
            if(t[h[i][j]] == 1)
            {
                no = h[i][j]; break;
            }
        for(ri j = 0; j < h[i].size(); j ++)
        {
            build(no, h[i][j]);
            if(t[h[i][j]] == 1)
                build(h[i][j], no);
        }
    }
    for(ri i = 1; i <= c; i ++)
    {
        int no = 0;
        for(ri j = 0; j < l[i].size(); j ++)
            if(t[l[i][j]] == 2)
            {
                no = l[i][j]; break;
            }
        for(ri j = 0; j < l[i].size(); j ++)
        {
            build(no, l[i][j]);
            if(t[l[i][j]] == 2)
                build(l[i][j], no);
        }
    }
    for(ri i = 1; i <= n; i ++)
        if(t[i] == 3)
            for(ri lx, ly, j = 0; j < 8; j ++)
            {
                lx = x[i] + dx[j], ly = y[i] + dy[j];
                if(mmp[lx][ly])
                    build(i, mmp[lx][ly]);
            }
    for(ri i = 1; i <= n; i ++)
        if(dfn[i] == 0)
            dfs(i);
    tot = -1;
    memset(he, -1, sizeof(he));
    for(ri i = 1; i <= n; i ++)
        for(ri j = head[i]; j >= 0; j = ter[j].ne)
            if(scc[i] != scc[ter[j].to])
                rebuild(scc[i], scc[ter[j].to]);
    for(ri i = 1; i <= cnt; i ++)
        if(flag[i] == 0)
            DP(i);
    printf("%d", ans);
}

【洛谷P1772】物流运输

这个题开始我在想,一个时间点转移到下一个时间点怎么办,比如我在1这个时间有一条长度为1的最短路,然后2这个时间,最短路就变为3了(之前3这整个路径不通),那么说明需要改变线路,但是改变一次的代价是1000000,还有一个为4的路,但是它一直可以通行,那么答案为4
后来看了题解发现担心是不必要的,我们可以求出一整个时间段的最短路,这样然后设dp[i]为从1~n的最小代价,然后枚举切换路径的时间点就吼了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

const int mx = 1000000007;

typedef long long lo;

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

inline void re(int &x)
{
    x = 0;
    char a = getchar(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = getchar();
    }
    while(a >= '0' && a <= '9')
        x = (x << 3) + (x << 1) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

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

int n, m, k, e, d, ta, he, lx, ly, lz, head[30], tot = -1;

int su[22][110], co[110][110], dis[25], q[1000010], dp[110];
/*
设dp[i]表示在1~n这个时间段里的最小花费
然后我们预处理出所有时间段的花费(不改变线路)
所以转移方程为dp[i] = min(dp[i], dp[j] + cost[j + 1][i] + k)
cost不改变线路时一段时间的花费 
*/ 

bool flag[22][110], vis[25];

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 void spfa(int f, int l)
{
    memset(dis, 63, sizeof(dis)), memset(vis, 0, sizeof(vis));
    ta = he = 0;
    q[he] =  1, dis[1] = 0;
    while(he <= ta)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(dis[to] > dis[qaq] + ter[i].co && su[to][l] - su[to][f - 1] == 0)
            {
                dis[to] = dis[qaq] + ter[i].co;
                if(vis[to] == 0)
                    vis[to] = 1, q[++ ta] = to;
            }
        }
        vis[qaq] = 0;
    }
    co[f][l] = dis[m];
    if(co[f][l] < dis[0])
        co[f][l] *= (l - f + 1);
}

int main()
{
    memset(head, -1, sizeof(head));
    re(n), re(m), re(k), re(e);
    for(ri i = 1; i <= e; i ++)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    re(d);
    for(ri i = 1; i <= d; i ++)
    {
        re(lx), re(ly), re(lz);
        for(ri j = ly; j <= lz; j ++)
            flag[lx][j] = 1;
    }
    for(ri i = 1; i <= m; i ++)//通过求前缀和,判断这个点是否能在一段时间内使用 
        for(ri j = 1; j <= n; j ++)
            su[i][j] = su[i][j - 1] + (int)flag[i][j];
    for(ri i = 1; i <= n; i ++)//预处理所有时间段内的最短路 
        for(ri j = i; j <= n; j ++)
            spfa(i, j);
    for(ri i = 1; i <= n; i ++)
        dp[i] = co[1][i];
    for(ri i = 2; i <= n; i ++)
        for(ri j = 1; j < i; j ++)
            dp[i]= min(dp[i], dp[j] + co[j + 1][i] + k);
    printf("%d", dp[n]);
}

【洛谷P1119】灾后重建

这个题开始我想着按照询问次数跑最短路,转念一想,这个题完全可以按照时间逐渐跑最短路,一步步读入查询,因为题目已经给你排好序了,剩下的就是判断是否有新的村庄重建完毕,然后去跑最短路,写个floyd就好了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

const int mx = 1000000007;

typedef long long lo;

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

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 3) + (x << 1) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, m, q, lx, ly, lz, ta, t[220], mmp[220][220];

int main()
{
    memset(mmp, 63, sizeof(mmp));
    memset(t, 63, sizeof(t));
    re(n), re(m);
    for(ri i = 0; i < n; i ++)
        re(t[i]), mmp[i][i] = 0;
    for(ri i = 0; i < m; i ++)
        re(lx), re(ly), re(mmp[lx][ly]), mmp[ly][lx] = mmp[lx][ly];
    re(q);
    while(q --)
    {
        re(lx), re(ly), re(lz);
        while(t[ta] <= lz)//判断是否有新的村庄重建好了 
        {
            for(ri i = 0; i < n; i ++)//有就更新最短路 
                for(ri j = 0; j < n; j ++)
                    mmp[i][j] = min(mmp[i][j], mmp[i][ta] + mmp[ta][j]);
            ta ++;
        }
        if(mmp[lx][ly] == mmp[210][210] || t[lx] > lz || t[ly] > lz)//如果跑不到或是询问的点没有重建好,无解 
            printf("-1\n");
        else
            printf("%d\n", mmp[lx][ly]);
    }
}