基本图论

[TOC]

建图

邻接矩阵

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 105;
int G[maxn][maxn];
int vis[maxn];
int n, m;
void add_edge(int u, int v)
{
    G[u][v] = 1;
}

void dfs(int u)
{
    cout << u << " ";
    vector<int> vec;
    for (int i = 1; i <= n; i++)
    {
        if (G[u][i] && !vis[i])
        {
            vec.push_back(i);
        }
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++)
    {
        vis[vec[i]] = 1;
        dfs(vec[i]);
    }
}
void bfs(int u)
{
    queue<int> q;
    q.push(u);

    while (!q.empty())
    {
        int cur = q.front();
        cout<<cur<<" ";
        q.pop();
        vector<int> vec;
        for (int i = 1; i <= n; i++)
        {
            if (G[cur][i] && !vis[i])
            {
                vec.push_back(i);
            }
        }
        sort(vec.begin(), vec.end());
        for (int i = 0; i < vec.size(); i++)
        {
            vis[vec[i]] = 1;
            q.push(vec[i]);
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }
    dfs(1);
    cout<<endl;
    memset(vis,0,sizeof(vis));
    bfs(1);
    return 0;
}

邻接链表（用vector）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
struct Edge
{
    int from, to;
};
vector<int> G[maxn];
vector<Edge> edges;
int vis[maxn];
void add_edge(int u, int v)
{
    edges.push_back({u, v});
    G[u].push_back(edges.size() - 1);
}
void input()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        add_edge(a, b);
    }
}
void dfs(int u)
{
    vis[u] = 1;
    // 我们G[u]存的是所有起点为u的边的编号，遍历拿到每一个编号edge_no
    for (auto edge_no : G[u])
    {
        // 通过边的编号我们拿到这条边的终点，即u的相邻点
        int to = edges[edge_no].to;
        if (!vis[to])
        {
            dfs(to);
        }
    }
}
int main()
{
    return 0;
}

拓扑排序

我们可以对DAG（有向无环图）进行拓扑排序。

用bfs来获得拓扑排序，首先将所有入度为0的节点加入队列。删除这些入度为0的节点（不需要真正删除，只要将相邻节点入度-1就行了），如果因为该节点删除后相邻节点入度为0，将相邻节点也加入队列。

如果我们拓扑排序后线性化的数组中元素个数小于节点数，说明拓扑排序失败（图中有环）

bool topo()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!deg[i])
            q.push(i);

    int cnt = 0;
    while (!q.empty())
    {
        auto u = q.front();
        q.pop();
        cnt++;
        for (auto v : G[u])
        {
            deg[v]--;
            if (!deg[v])
                q.push(v);
        }
    }
    return cnt == node_cnt;
}

排序

题目大意

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 A,B,C,D 表在这道题中\(A<B<C<D\)，我们将给你一系列形如 \(A<B\) 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

解题思路

我们将每个字母当作一个节点，一个小于关系就是一条边。然后建图跑拓扑排序，如果图中存在环就说明无解。有的时候图中的拓扑排序是不唯一的，该题还要询问拓扑排序是否唯一（即方案唯一），我们可以记录bfs最长的深度，如果该深度等于节点数，说明有一条有n个节点的链刚好连接所有节点。

AC代码

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e5;
struct Edge
{
    int from;
    int to;
};
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int deg[maxn];
int Deg[maxn];
int vis[maxn];

void add_edge(int u, int v)
{
    edges.push_back({u, v});
    Deg[v]++;
    G[u].push_back(edges.size() - 1);
}

vector<int> ans;
int topo_sort()
{
    memcpy(deg,Deg,sizeof(Deg));
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
            q.push({i, 1});
    int res = 1;
    while (!q.empty())
    {
        int cur = q.front().first;
        int depth = q.front().second;
        q.pop();
        ans.push_back(cur);

        for (auto edge_no : G[cur])
        {
            Edge e = edges[edge_no];
            deg[e.to]--;
            if (deg[e.to] == 0)
            {
                q.push({e.to, depth + 1});
                res = max(res, depth + 1);
            }
        }
    }
    if (ans.size() < n)
        return -1;
    if (res < n)
        return 0;
    return 1;
}
char getch()
{
    char ch = getchar();
    while (isspace(ch))
        ch = getchar();
    return ch;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        char u = getch();
        getchar();
        char v = getch();
        add_edge(u - 'A' + 1, v - 'A' + 1);
        ans.clear();
        int res = topo_sort();
        if (res == 1)
        {
            cout << "Sorted sequence determined after"
                 << " " << i << " relations: ";
            for (auto a : ans)
            {
                cout << (char)(a + 'A' - 1);
            }
            cout << ".";
            cout << endl;
            return 0;
        }
        else if (res == -1)
        {
            cout << "Inconsistency found after " << i << " relations.\n";
            return 0;
        }
    }
    cout << "Sorted sequence cannot be determined.\n";
    return 0;
}

车站分级

题目大意

题面看上去挺复杂的，大概就是给你很多车站，以及很多车次，每个车站有一个优先级，如果某一车次在优先级为\(a_i\)的车站停靠了，那么起点和终点之间，所有优先级大于等于\(a_i\)的车站，该车次都必须停靠。一开始这些车站的优先级都不确定，你只知道每个车次会在哪里停靠，请尝试为这些车站分级，输出所需要的最小的级数。

题目分析

这里有一个显然的顺序就是一辆车次起点站和终点站之间的所有站，停靠的优先级一定大于不停靠的优先级。

我们根据这个建图，然后进行拓扑排序，最后记录一下图中最长深度就行了。其实这一题并没有让你输出拓扑排序，而且保证了有解（也就是无环）你也可以求DAG上最长路直接求出最长深度。

AC代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e3 + 5;
struct Edge
{
    int from, to;
};
vector<int> G[maxn];
vector<Edge> edges;
int n, m;
int vis[maxn];
int G2[maxn][maxn];
vector<int> Trans[maxn];
int deg[maxn];
void add_edge(int u, int v)
{
    if (G2[u][v])
        return;
    G2[u][v] = 1;
    deg[v]++;
    edges.push_back({u, v});
    G[u].push_back(edges.size() - 1);
}
int topo()
{
    memset(vis, 0, sizeof(vis));
    // 记录层数
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++)
        if (!deg[i])
            q.push({i, 1});
    int res = 1;
    while (!q.empty())
    {
        int cur = q.front().first;
        int dep = q.front().second;
        q.pop();
        for (auto e_no : G[cur])
        {
            int v = edges[e_no].to;
            deg[v]--;
            if (!deg[v])
            {
                q.push({v, dep + 1});
                res = max(res, dep + 1);
            }
        }
    }
    return res;
}

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int cnt;
        cin >> cnt;
        memset(vis, 0, sizeof(vis));
        for (int j = 1; j <= cnt; j++)
        {
            int cur;
            cin >> cur;
            Trans[i].push_back(cur);
            vis[cur] = 1;
        }
        for (int j = Trans[i].front(); j <= Trans[i].back(); j++)
        {
            if (vis[j])
                continue;
            // 没有走到的车站，优先级肯定比走到的车站优先级低，我们依次连接已经走到的车站。
            for (auto v : Trans[i])
                add_edge(j, v);
        }
    }
}
int main()
{
    input();
    cout << topo() << endl;
    return 0;
}

最小生成树

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
const int maxn = 1e5 + 5;
using namespace std;
#define int long long
namespace Kruskal
{
    int n, m;
    struct Edge
    {
        int from, to, w;
        bool operator<(const Edge &e) const
        {
            return w < e.w;
        }
    };

    vector<Edge> edges;

    int par[maxn];

    void add_edge(int u, int v, int d)
    {
        edges.push_back({u, v, d});
    }
    void init()
    {
        for (int i = 1; i <= n; i++)
            par[i] = i;
    }
    int find(int x)
    {
        return x == par[x] ? x : par[x] = find(par[x]);
    }

    int kruskal()
    {
        int res = 0;
        sort(edges.begin(), edges.end());
        for (auto e : edges)
        {
            int a = find(e.from), b = find(e.to);
            if (a == b)
                continue;
            par[a] = b;
            res += e.w;
        }
        return res;
    }
}

signed main()
{
    cin >> Kruskal::n >> Kruskal::m;
    Kruskal::init();
    for (int i = 1; i <= Kruskal::m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Kruskal::add_edge(a, b, c);
    }
    cout << Kruskal::kruskal();
    return 0;
}

CF1408E

题目大意

给你\(m\)个集合，\(A_1\)到\(A_m\)，他们元素的范围都为\([1,n]\)的整数，以及数组\(\{a_i\},\{b_i\}\)，在第\(i\)集合删掉元素\(j\)第代价是\(a_i+b_j\)，你可以删除任意一个集合元素。

现在有一个\(n\)个节点的无向图，如果删除操作结束以后元素\(x,y\)在同一个集合\(i\)同时存在，则\(x,y\)之间连一条颜色为\(i\)的边。

问最小代价，使得删除完元素后形成的图不存在一个每条边颜色都不同的环(环长可以为2)

输入

第一行\(m,n\)

第二行\(m\)个数\(\{a_i\}\)

第三行\(n\)个数\(\{b_i\}\)

下面\(m\)行，第一个数字表示\(A_i\)元素的个数，接下来个是\(A_i\)序列

样例

CASE 1
3 2
1 2 3
4 5
2 1 2
2 1 2
2 1 2
ANS:
11
  
CASE 2:
7 8
3 6 7 9 10 7 239
8 1 9 7 10 2 6 239
3 2 1 3
2 4 1
3 1 3 7
2 4 3
5 3 4 5 6 7
2 5 7
1 8
ANS:
66

题解

分别连接每个\(j\)到\(A_i\) 边权为\(a[i]+b[j]\)，然后跑最大生成树。最后拿所有边权和减去这个最大生成树，这个最大生成树就是不存在环的最优解。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define int long long
const int maxn = 2e5 + 5;
using namespace std;
int n, m;
int a[maxn];
int b[maxn];
vector<int> A[maxn];

namespace Kruskal
{
    int n, m;
    struct Edge
    {
        int from, to, w;
        bool operator<(const Edge &e) const
        {
            return w > e.w;
        }
    };

    vector<Edge> edges;

    int par[maxn];

    void add_edge(int u, int v, int d)
    {
        edges.push_back({u, v, d});
    }
    void init()
    {
        for (int i = 1; i <= n; i++)
            par[i] = i;
    }
    int find(int x)
    {
        return x == par[x] ? x : par[x] = find(par[x]);
    }

    int kruskal()
    {
        int res = 0;
        sort(edges.begin(), edges.end());
        for (auto e : edges)
        {
            int a = find(e.from), b = find(e.to);
            if (a == b)
                continue;
            par[a] = b;
            res += e.w;
        }
        return res;
    }
}
void input()
{
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    for (int i = 1; i <= m; i++)
    {
        int cnt;
        cin >> cnt;
        for (int j = 1; j <= cnt; j++)
        {
            int tmp;
            cin >> tmp;
            A[i].push_back(tmp);
        }
    }
}
signed main()
{
    input();
    Kruskal::n = n + m + 1;
    Kruskal::init();
    int ans = 0;
    for (int i = 1; i <= m; i++)
        for (auto j : A[i])
        {
            ans += a[i] + b[j];
            Kruskal::add_edge(j, i + n, a[i] + b[j]);
        }

    cout << ans - Kruskal::kruskal() << endl;
    return 0;
}

最短路

SPFA

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
struct Edge{
    int from,to;
    int dist;
};
const int maxn=1e4+5;
vector<Edge> edges;
vector<int> G[maxn];
void add_edge(int u,int v,int dist)
{
    edges.push_back({u,v,dist});
    G[u].push_back(edges.size()-1);
}
int n,m,s;
int vis[maxn];
int dist[maxn];
void input(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,d;
        cin>>u>>v>>d;
        add_edge(u,v,d);
    }
}
void spfa(int s)
{
    memset(dist,0x3f,sizeof(dist));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    dist[s]=0;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;

        for(size_t i=0;i<G[u].size();i++)
        {
            Edge e=edges[G[u][i]];
            int v= e.to,d=e.dist;
            if(dist[v] > dist[u]+d)
            {
                dist[v]=dist[u]+d;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main(){
    input();
    spfa(s);
    for(int i=1;i<=n;i++)
        cout<<dist[i]<<" \n"[i==n];
    return 0;
}

Dijkstra

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;    
struct Edge
{
    int from, to, d;
};
struct NodeCmp
{
    long long d;
    int x;
    bool operator<(const NodeCmp & nc)const 
    {
        return d>nc.d;
    }
};
int N,M;
const int maxn = 100005;
struct Dj
{
    vector<int> G[maxn];
    vector<Edge> edges;
    int vis[maxn];
    long long d[maxn];
    void add_edge(int x, int y, int v)
    {
        edges.push_back(Edge{x, y, v});
        G[x].push_back(edges.size()-1);
    }

    void solve(int s){
        memset(d,0x3f,sizeof(d));
        memset(vis,0,sizeof(vis));
        d[s]=0;
        priority_queue<NodeCmp> q;
        q.push({0LL,s});

        while(!q.empty())
        {
            int cur_d=q.top().d;
            int u=q.top().x;
            q.pop();
            if(vis[u])
                continue;
            vis[u]=1;
            for(int i=0;i<G[u].size();i++)
            {
                int v=edges[G[u][i]].to;
                if(d[v]>d[u]+edges[G[u][i]].d)
                {
                    d[v]=d[u]+edges[G[u][i]].d;
                    q.push({d[v],v});
                }
            }
        }
    }
}dj;

int main(){
    int s;
    cin>>N>>M>>s;
    for(int i=0;i<M;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        dj.add_edge(a,b,c);
        //rev_dj.add_edge(b,a,c);
    }
    dj.solve(s);
    //rev_dj.solve(0);
    int sum=0;
    for(int i=1;i<=N;i++)
        std::cout<<dj.d[i]<<" ";
    //std::cout<<sum;
    return 0;
}

缩点

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=20005;
struct Edge
{
    int from,to;
};
int value[maxn],N,M;
int ng[maxn],ans[maxn];
int rd[maxn];
int dfn[maxn],low[maxn],vis[maxn],tim=1;
vector<Edge> edges;
vector<Edge> new_edges;
vector<int> stac;
vector<int> new_G[maxn];
vector<int> G[maxn];
void add_edge(int from,int to)
{
    edges.push_back({from,to});
    G[from].push_back(edges.size()-1);
}
void tarjan(int u)
{
    low[u]=dfn[u]=++tim;
    vis[u]=1;
    stac.push_back(u);
    for(int i=0;i<G[u].size();i++)
    {
        int v=edges[G[u][i]].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    //printf("TIME TIK:(%d,%d)\n",dfn[u],low[u]);
    if(dfn[u]==low[u])
    {
        int v;
        while(v=stac.back())
        {
            // printf("%d ",v);
            stac.pop_back();
            ng[v]=u;
            vis[v]=0;
            if(u==v)
                break;
            value[u]+=value[v];
        }
    }
}

void rebuild(){
    for(int i=0;i<M;i++)
    {
        int u=ng[edges[i].from],v=ng[edges[i].to];
        if(u!=v)
        {
            new_edges.push_back({u,v});
            // printf("LINK %d,%d %d\n",u,v,rd[v]+1);
            new_G[u].push_back(new_edges.size()-1);
            rd[v]++;
        }
    }
}
void topo()
{
    queue<int> q;
    for(int i=1;i<=N;i++)
    {
        if(ng[i]==i&&!rd[i] ) 
        {
            q.push(i);
            ans[i]=value[i];
            // printf("VALUE %d %d\n",i,value[i]);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<new_G[u].size();i++)
        {
            Edge e=new_edges[new_G[u][i]];
            int v=e.to;
            ans[v]=max(ans[v],ans[u]+value[v]);
            rd[v]--;
            if(rd[v]==0)
            {
                // printf("ADD %d\n",v);
                q.push(v);
            }
        }
    }
}
int main(){
    cin>>N>>M;
    memset(rd,0,sizeof(rd));
    memset(vis,0,sizeof(vis));
    memset(ng,0,sizeof(ng));
    memset(ans,0,sizeof(ans));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(value,0,sizeof(value));
    for(int i=1;i<=N;i++)
        cin>>value[i];
    for(int i=1;i<=M;i++)
    {
        int a,b;
        cin>>a>>b;
        add_edge(a,b);
    }
    // printf("\n================\n");
    int res=0;
    for(int i=1;i<=N;i++)
        if(!dfn[i]) tarjan(i);
    rebuild();
    topo();
    for(int i=1;i<=N;i++)
        res=max(res,ans[i]);
    cout<<res;
    return 0;
}

割点

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=2e4+5;
struct Edge{
    int from,to;
};
vector<Edge> edges;
vector<int> G[maxn];
int dfn[maxn],low[maxn],tim=0,cut[maxn];
int N,M;
void add_edge(int u,int v)
{
    edges.push_back({u,v});
    G[u].push_back(edges.size()-1);
}

void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tim;
    int child=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=edges[G[u][i]].to;
        if(!dfn[v])
        {
            tarjan(v,fa);
            low[u]=min(low[v],low[u]);
            if(low[v] >= dfn[u] && u!=fa)
                cut[u]=1;
            if(u==fa)
                child++;
        }
        low[u]=min(low[u],dfn[v]);
    }
    if(child>=2)
        cut[u]=1;
}

int main(){
    cin>>N>>M;
    for(int i=0;i<M;i++)
    {
        int a,b;
        cin>>a>>b;
        add_edge(a,b);
        add_edge(b,a);
    }
    for(int i=1;i<=N;i++)
        if(!dfn[i])
            tarjan(i,i);
    vector<int> res;
    for(int i=1;i<=N;i++)
        if(cut[i])
            res.push_back(i);
    cout<<res.size()<<endl;
    for(int i=0;i<res.size();i++)
        cout<<res[i]<<" \n"[i==res.size()-1];
    return 0;
}

差分约束

差分约束系统是下面形式的多元一次不等式组（\(y_1,y_2...y_n\)是已知量）

\[ \begin{align} & x_{c1}-x_{c1'}\le y_1 \\ & x_{c2}-x_{c2'}\le y_2 \\ & ... \\ & x_{c_n}-x_{c_n'}\le y_n \\ \end{align} \]

我们转换为\(x_{c_i} \le x_{c_i'} + y_i\) 我们将\(c_i'\)到\(c_i\)连上一条权值为\(y_i\)的边，然后引入一个超级源点，将其他所有点连一条权值为0点边。

\({x_i}\)的一组解就是从超级源点出发的最短路。如果没有最短路，就无解。我们得到的一组解可以同时加上或减去一个数（设置dist[0]的值），也是一组解。

这里其实求的是满足 \(x_i\le dist[0]\)的最大解，如果我们要求\(x_i\ge dist[0]\)最小解我们就可以修改程序的的三角形不等式的比较符号以及差分约束的比较符号变为\(\ge\)并将dist初始化为-INF 即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
struct Edge
{
    int from, to;
    int d;
};
vector<int> G[maxn];
vector<Edge> edges;
int cnt[maxn];
int dist[maxn];
int vis[maxn];
void add_edge(int u, int v, int d)
{
    edges.push_back({u, v, d});
    G[u].push_back(edges.size() - 1);
}
void input()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add_edge(b,a, c);
    }
    for (int i = 1; i <= n; i++)
    {
        add_edge(n + 1, i, 0);
    }
}
bool spfa()
{
    queue<int> q;
    memset(dist, 0x3f, sizeof(dist));
    q.push(n + 1);
    vis[n + 1] = 1;
    dist[n+1]=0;
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        vis[cur] = 0;
        for (auto eno : G[cur])
        {
            Edge e = edges[eno];
            if (dist[e.to] > dist[cur] + e.d)
            {
                if (++cnt[e.to] > 2 * n)
                    return false;
                dist[e.to] = dist[cur] + e.d;
                if (!vis[e.to])
                {
                    q.push(e.to);
                    vis[e.to] = 1;
                }
            }
        }
    }
    return true;
}
int main()
{
    input();
    if(!spfa())
        cout<<"NO";
    else {
        for(int i=1;i<=n;i++)
            cout<<dist[i]<<" ";
    }
    return 0;
}

实际问题中可能不仅仅是小于的关系，我们可以进行转化

1. \(x_1 - x_2 \ge y\) 转化为 \(x_2-x_1 \le -y\)

2. \(x_1-x_2 = y\) 转化为 \(x_1-x_2 \le y\) 且 \(x_2 - x_1 \le y\)

3. \(x_1 - x_2 \lt y\) 转化为 \(x_1 - x_2 \le y - 1\)

4. $x_1 - x_2 > y $转化为 \(x_2 - x_1 \le -y -1\)

P1250 种树

题目描述 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。 写一个程序完成以下工作： 输入格式 第一行包含数据N，区域的个数(0<N≤30000)； 第二行包含H，房子的数目(0<H≤5000)； 下面的H行描述居民们的需要：B E T，0<B≤E≤30000，T≤E-B+1。 输出格式 输出文件只有一行写有树的数目

我们可以用前缀和来处理，就是要满足

$ S_E-S_{B-1}T$且\(0 \le S_i-S_{i-1} \le 1\)

然后跑一个差分约束即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
const int maxn = 1e5 + 5;
int n, m;
struct Edge
{
    int from, to, dist;
};
vector<int> G[maxn];
vector<Edge> edges;
int dist[maxn];
int vis[maxn];
void add_edge(int u, int v, int c)
{
    edges.push_back({u, v, c});
    G[u].push_back(edges.size() - 1);
}
void spfa()
{
    memset(dist, -0x3f, sizeof(dist));
    queue<int> q;
    q.push(0);
    vis[0] = 1;
    dist[0] = 0;
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        vis[cur] = 0;
        for (auto edge_no : G[cur])
        {
            auto e = edges[edge_no];
            if (dist[e.to] < dist[cur] + e.dist)
            {
                dist[e.to] = dist[cur] + e.dist;
                if (!vis[e.to])
                {
                    q.push(e.to);
                    vis[e.to] = 1;
                }
            }
        }
    }
}
void input()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> b >> a >> c;
        add_edge(b - 1, a, c);
    }
    for (int i = 1; i <= n; i++)
    {
        add_edge(i - 1, i, 0);
        add_edge(i, i - 1, -1);
    }
}
int main()
{
    input();
    spfa();
    cout << dist[n];
    return 0;
}

网络流

模板

Ford-Fulkson

Ford-Fulkson算法，对于一个有向图，要求图中的最大流我们可以建图的时候连上反向边并初始化为0，不断求增广路。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, start, dest;
struct Edge
{
    int from, to;
    int d;
};
vector<int> G[maxn];
vector<Edge> edges;
int vis[maxn];

void add_edge(int u, int v, int d)
{
    edges.push_back({u, v, d});
    G[u].push_back(edges.size() - 1);
}
void input()
{
    cin >> n >> m >> start >> dest;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add_edge(a, b, c);
        add_edge(b, a, 0);
    }
}
int dfs(int u, int t, int flow)
{
    if (u == t)
        return flow;
    vis[u] = true;
    int res = 0;
    for (auto e_no : G[u])
    {
        auto &e = edges[e_no];
        if (vis[e.to] || e.d <= 0)
            continue;
        if ((res = dfs(e.to, t, min(flow, e.d))) > 0)
        {
            edges[e_no].d -= res;
            edges[e_no ^ 1].d += res;
            return res;
        }
    }
    return 0;
}

int max_flow(int s, int t)
{
    int res = 0;
    while (true)
    {
        memset(vis,0,sizeof(vis));
        int tmp = dfs(s, t, 0x3f3f3f3f);
        if (tmp)
            res += tmp;
        else
            break;
    }
    return res;
}
int main()
{
    input();
    cout << max_flow(start, dest);
    return 0;
}

EK

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n, m, start, dest;
struct Edge
{
    int from, to;
    int flow;
};
vector<int> G[maxn];
vector<Edge> edges;
int vis[maxn];
int A[maxn];
int last[maxn];

void add_edge(int u, int v, int d)
{
    edges.push_back({u, v, d});
    G[u].push_back(edges.size() - 1);
}
void input()
{
    cin >> n >> m >> start >> dest;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add_edge(a, b, c);
        add_edge(b, a, 0);
    }
}

int max_flow(int s, int t)
{
    int res = 0;
    while (true)
    {
        queue<int> q;
        q.push(s);
        memset(A, 0, sizeof(A));
        memset(last, -1, sizeof(last));
        A[s] = 0x3f3f3f3f;

        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            for (auto e_no : G[cur])
            {
                auto e = edges[e_no];
                if (last[e.to] == -1 && e.flow)
                {
                    last[e.to] = e_no;
                    A[e.to] = min(e.flow, A[e.from]);
                    q.push(e.to);
                }
            }
        }
        // 到汇点无流量，即可退出
        if (!A[t])
            return res;
        res += A[t];
        // 找到的路径榨流量
        for (int cur = t; cur != s; cur = edges[last[cur]].from)
        {
            edges[last[cur]].flow -= A[t];
            edges[last[cur] ^ 1].flow += A[t];
        }
    }
}
signed main()
{
    input();
    cout << max_flow(start, dest);
    return 0;
}

Dinic 模版

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
namespace Dinic
{
    int s, t;
    const int maxn = 20005;
    const int maxm = 1000100;
    int head[maxn], cur[maxn], depth[maxn];
    int cnt = 1, n = 0;

    struct Edge
    {
        int to, next, cap;
    };
    Edge edges[maxm];

    void _add_edge(int u, int v, int c)
    {
        edges[++cnt].to = v;
        edges[cnt].cap = c;
        edges[cnt].next = head[u];
        head[u] = cnt;
    }
    void add(int u, int v, int c)
    {
        // printf("{%d,%d,%d}\n",u,v,c);
        _add_edge(u, v, c);
        _add_edge(v, u, 0);
    }
    bool bfs()
    {
        memset(depth, -1, sizeof(depth));
        depth[s] = 0;

        for (int i = 0; i <= n; i++)
            cur[i] = head[i];
        cur[t]= head[t];
        cur[s]= head[s];
        queue<int> q;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = head[u]; i; i = edges[i].next)
            {
                int to = edges[i].to;
                if (depth[to] == -1 && edges[i].cap > 0)
                    depth[to] = depth[u] + 1, q.push(to);
            }
        }
        return depth[t] != -1;
    }
    int dfs(int from, int flow)
    {
        if (from == t)
            return flow;

        int res = flow;

        for (int i = cur[from]; i && res; i = edges[i].next)
        {
            cur[from] = i;

            int to = edges[i].to;
            int cap = edges[i].cap;
            if (cap > 0 && depth[to] == depth[from] + 1)
            {
                int c = dfs(to, min(cap, res));
                res -= c;
                edges[i].cap -= c;
                edges[i ^ 1].cap += c;
            }
        }
        return flow - res;
    }
    long long dinic(int _s,int _t,int _n)
    {
        s=_s;
        t=_t;
        n=_n;
        long long ret = 0;
        while (bfs())
        {
            ret += dfs(s, 0x3f3f3f3f);
        }
        return ret;
    }
} // namespace Dinic
int main(){
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        Dinic::add(a,b,c);
    }
    cout<<Dinic::dinic(s,t,n);
    return 0;
}

MCMF模版

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
namespace MCMF
{
    const int maxn=100005;
    int s, t;
    
    struct Edge
    {
        int from, to, w, c;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int dist[maxn];
    int pre[maxn];
    int vis[maxn];
    int flow[maxn];
    void add_edge(int u, int v, int w, int c)
    {
        edges.push_back({u, v, w, c});
        G[u].push_back(edges.size() - 1);
    }
    void add(int u,int v,int w,int c)
    {
        add_edge(u,v,w,c);
        add_edge(v,u,0,-c);
    }
    bool spfa()
    {
        // init
        memset(vis, 0, sizeof(vis));
        memset(flow, -1, sizeof(flow));
        memset(dist, 0x3f, sizeof(dist));
        memset(pre, -1, sizeof(pre));
        dist[s] = 0;
        flow[s] = 0x3f3f3f3f;
        // spfa
        queue<int> q;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for (auto idx : G[u])
            {
                Edge e = edges[idx];
                int v = e.to;
                if (e.w && dist[v] > dist[u] + e.c)
                {
                    dist[v] = dist[u] + e.c;
                    flow[v] = min(flow[u], e.w);
                    pre[v] = idx;
                    if (!vis[v])
                    {
                        q.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
        return flow[t] != -1;
    }
    // first max_flow, second min_cost
    std::pair<long long,long long> MCMF(int _s,int _t)
    {
        s=_s,t=_t;
        long long max_flow = 0, min_cost = 0;
        while (spfa())
        {
            max_flow += flow[t];
            min_cost += dist[t] * flow[t];
            for (int i = t; pre[i] != -1; i = edges[pre[i]].from)
            {
                edges[pre[i]].w -= flow[t];
                edges[pre[i] ^ 1].w += flow[t];
            }
        }
        return {max_flow,min_cost};
    }
} // namespace MCMF

P1251 餐饮计划问题

题目大意

一个餐厅\(n\)天，每天需要\(r_i\)个餐巾，每天可以花\(p\)分购买新餐巾，也可以送到快洗店，洗一块需要\(m\)天其费用是\(f\)分，或者送到慢洗部，洗一块需要\(n\)天其费用为\(s\)，每天结束会产生脏餐巾。问满足每天需求量最小的花费。

输入

第一行\(N\)

第二行\(p,m,f,n,s\)

输入:
3
1 7 5 
11 2 2 3 1
输出:
134

分析

可以考虑拆点，将一天拆成白天和黑夜白天用的餐巾到了晚上就会变脏衣服。

1. 从源点引入费用为\(p\)，容量为inf的边连接第\(i\)天早上，代表可以买餐具
2. 从第\(i\)天早上引入费用为0，容量为inf的边连接汇点，这样跑最大流的时候会帮自动保证第\(i\)天餐巾是够的。
3. 从源点引入费用为0，容量为\(r_i\)的边连接到第\(i\)天晚上，说明早上的衣服脏了留到了晚上。
4. 连接第\(i\)天晚上到第\(i+m\)天早上，费用为快洗费用，流量为inf, 使用快洗
5. 连接第\(i\)天晚上到第\(i+n\) 天早上，费用为慢洗费用，流量为inf, 使用慢洗
6. 连接第\(i\)天早上到第\(i+1\)天早上，费用为0，流量为inf, 干净的衣服留到第二天。(留脏衣服好像也行，都AC了。。。。)

AC代码

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <fstream>
const int maxn = 20005;
using namespace std;
namespace MCMF
{
    int s, t;
    struct Edge
    {
        int from, to, w, c;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int dist[maxn];
    int pre[maxn];
    int vis[maxn];
    int flow[maxn];
    void add_edge(int u, int v, int w, int c)
    {
        edges.push_back({u, v, w, c});
        G[u].push_back(edges.size() - 1);
    }
    void add(int u,int v,int w,int c)
    {
        add_edge(u,v,w,c);
        add_edge(v,u,0,-c);
    }
    bool spfa()
    {
        // init
        memset(vis, 0, sizeof(vis));
        memset(flow, -1, sizeof(flow));
        memset(dist, 0x3f, sizeof(dist));
        memset(pre, -1, sizeof(pre));
        dist[s] = 0;
        flow[s] = 0x3f3f3f3f;
        // spfa
        queue<int> q;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for (auto idx : G[u])
            {
                Edge e = edges[idx];
                int v = e.to;
                if (e.w && dist[v] > dist[u] + e.c)
                {
                    dist[v] = dist[u] + e.c;
                    flow[v] = min(flow[u], e.w);
                    pre[v] = idx;
                    if (!vis[v])
                    {
                        q.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
        return flow[t] != -1;
    }
    // first max_flow, second min_cost
    std::pair<long long,long long> MFMC()
    {
        long long max_flow = 0, min_cost = 0;
        while (spfa())
        {
            max_flow += flow[t];
            min_cost += dist[t] * flow[t];
            for (int i = t; pre[i] != -1; i = edges[pre[i]].from)
            {
                edges[pre[i]].w -= flow[t];
                edges[pre[i] ^ 1].w += flow[t];
            }
        }
        return {max_flow,min_cost};
    }
} // namespace MCMF
int req[maxn];
int N;
int p,m,f,n,s;
int main()
{
    const int inf=0x3f3f3f3f;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>req[i];
    }
    cin>>p>>m>>f>>n>>s;
    MCMF::s=0;
    MCMF::t=maxn-1;

    for(int i=1;i<=N;i++)
    {
        int base=(i-1)*2;
        MCMF::add(0,base+1,req[i],p);
        MCMF::add(base+1,MCMF::t,req[i],0);
        MCMF::add(base+1,base+1+2,inf,0);
        MCMF::add(0,base+2,req[i],0);
        // Link to Washing room
        MCMF::add(base+2,base+1+(2*m),inf,f);
        MCMF::add(base+2,base+1+(2*n),inf,s);
    }
    cout<<MCMF::MFMC().second<<std::endl;
    return 0;
}