看上去毫不相干的东西也许是正解

其实本来不想写的…毕竟看了题解很惭愧…但是今天又考了一个类似的…看上去还挺普遍挺套路的?

AHOI2009 Mincut

感谢Gay娘耐心的讲解

在残量网络上可以干很多有趣的事情…比如说求个方案或者跑个tarjan啥的…

我们在残量网络上跑tarjan(只关心flow < cap的边)

  • 如果一条边没有满流, 显然不会出现在任何割中
  • 如果一条边的fromto在一个强连通分量中, 那么这条边不满足条件1: 如那支灰色的流的前两条边, 和下面两条空流的蓝边在一个强连通分量中, 那么我就可以用底下的蓝边来替代这两条灰色的边, 而流量不变

看看这个

  • 如果一条边的froms在一个强连通分量里, tot在一个强连通分量里, 那么这条边满足条件2: froms在一个强连通分量中代表有至少两条路径可以走到from, 而且一条有流量一条没有流量(即确实可以通过这些在强连通分量里的路径到达from);tot在一个强连通分量理由同上; 所以不管割掉哪些满流的边, 都可以通过另外一条路径到达from, to也可以通过另外的路径到达t, 所以这条边是必须割掉的

如果您看不懂, 说明您和我一样理解的有偏差…

[割掉一条边]是要求割掉这条边之后, 别的边不管割掉哪些, 都不会有流通过, 而不是出现在最小割中, 因为最小割是一个割集, 必须要割掉指定的所有边才能保证没有流通过

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#define MAXN (400000 + 5)
#define MAXM (600000 + 5)
#define INF (0x7ffffff)
#define rev(a) ((((a) - 1) ^ 1) + 1)
#define pbb pair<bool, bool>
#define mkp(a, b) make_pair(a, b)
using namespace std;
struct edg
{
    int from, to, next, cap, flow, bh;
    edg(): bh(0) {}
    edg(int fr, int t, int ne, int ca, int fl): from(fr), to(t), next(ne), cap(ca), flow(fl) {}
}b[MAXM << 1];
int s, t, g[MAXN], cntb, n, bl[MAXN], dfn[MAXN], low[MAXN], cntdfn, dis[MAXN];
pbb ans[MAXN];
bool instack[MAXN];
stack<int> ss;
void tarjan(int dq)
{
    bl[dq] = dq;
    dfn[dq] = low[dq] = ++cntdfn;
    ss.push(dq);
    instack[dq] = true;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].cap <= b[i].flow)    continue;
        if (!dfn[b[i].to])
        {
            tarjan(b[i].to);
            low[dq] = min(low[dq], low[b[i].to]);
        }
        else if (instack[b[i].to])
        {
            low[dq] = min(low[dq], dfn[b[i].to]);
        }
    }
    if (low[dq] == dfn[dq])
    {
        while (!ss.empty() && ss.top() != dq)
        {
            bl[ss.top()] = dq;
            instack[ss.top()] = false;
            ss.pop();
        }
        ss.pop();
        instack[dq] = false;
    }
}
bool bfs()
{
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            if (!dis[b[i].to] && b[i].cap > b[i].flow)
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
        }
    }
    return dis[t];
}
int dinic(int dq, int maxf)
{
    if (dq == t || (!maxf))
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
        {
            int zl = dinic(b[i].to, min(b[i].cap - b[i].flow, maxf));
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
            maxf -= zl;
            re += zl;
        }
    }
    return re;
}
void solve()
{
    while (bfs())
        dinic(s, INF);
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= cntb; i++)
    {
        if (b[i].bh && b[i].flow == b[i].cap)
        {
            ans[b[i].bh] = mkp(false, false);
            if (bl[b[i].from] != bl[b[i].to])
            {
                ans[b[i].bh].first = true;
                if (bl[b[i].from] == bl[s] && bl[b[i].to] == bl[t])
                    ans[b[i].bh].second = true;
            }
        }
    }
}
void adn(int from, int to, int cap)
{
    b[++cntb] = edg(from, to, g[from], cap, 0);
    g[from] = cntb;
}
int main()
{
    int m;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++)
    {
        int srx, sry, srz;
        scanf("%d%d%d", &srx, &sry, &srz);
        adn(srx, sry, srz);
        b[cntb].bh = i;
        adn(sry, srx, 0);
    }
    solve();
    for (int i = 1; i <= m; i++)
        printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}

/*
6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3
*/

舞动的夜晚

感谢XP学长耐心的讲解

和上面那个题就非常的像了…

如果一条边没有满流, 而且他的首尾不在一个强连通分量中, 那么加上这条边就会使流量减少

看看这个

如果一条边被删掉了流量不变, 当且仅当他的fromto在一个强连通分量中, 因为如果这条边有流量, 就一定可以通过强连通分量中的另一条路径流过去, 否则删掉也没有任何影响

那么, 可以改变边的流量都是在强连通分量之间改变的, 如果一条边并不在强连通分量中, 而他的流量还是空的, 说明加上这条边就一定会使总流量减少

沙茶的 代码

注意别把反向边给加到ans里了…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0X7FFFFFF)
#define bh(a) ((a) + n)
#define rev(a) ((((a) - 1) ^ 1) + 1)
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from, to, next, cap, flow;
    int bh;
}b[MAXM << 1];
int g[MAXN], cntb, belong[MAXN], dfn[MAXN], low[MAXN], cntdfn;
int dis[MAXN], n, m, tm;
stack<int> st;
bool ins[MAXN], ans[MAXN];
void adn(int from, int to, int cap)
{
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].flow = 0, b[cntb].to = to, b[cntb].cap = cap;
    g[from] = cntb;
}
void tarjan(int dq)
{
    low[dq] = dfn[dq] = ++cntdfn;
    st.push(dq);
    ins[dq] = true;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].cap <= b[i].flow)
            continue;
        if (!dfn[b[i].to])
        {
            tarjan(b[i].to);
            low[dq] = min(low[b[i].to], low[dq]);
        }
        else if (ins[b[i].to])
            low[dq] = min(low[dq], dfn[b[i].to]);
    }
    if (low[dq] == dfn[dq])
    {
        while (!st.empty() && st.top() != dq)
        {
            ins[st.top()] = false;
            belong[st.top()] = dq;
            st.pop();
        }
        ins[dq] = false;
        belong[dq] = dq;
        if (!st.empty())
            st.pop();
    }
}
int dinic(int dq, int maxf)
{
    if (dq == t || !maxf)
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
        {
            int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
            maxf -= zl;
            re += zl;
        }
    }
    return re;
}
int bfs()
{
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
            if (!dis[b[i].to] && b[i].cap > b[i].flow)
                dis[b[i].to] = dis[dq] + 1, q.push(b[i].to);
    }
    return dis[t];
}
void solve()
{
    memset(ins, false, sizeof(ins));
    memset(ans, false, sizeof(ans));
    while (bfs())
        dinic(s, INF);
//        printf("%d\n", dinic(s, INF));
    for (int i = 1; i <= (n + m); i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= cntb; i++)
        if (b[i].flow != b[i].cap && belong[b[i].from] != belong[b[i].to])
            ans[b[i].bh] = true;
    int pans = 0;
    for (int i = 1; i <= tm; i++)
        if (ans[i])
            ++pans;
    printf("%d\n", pans);
    for (int i = 1; i <= tm; i++)
        if (ans[i])
            printf("%d ", i);
}
int main()
{
    freopen("d.in", "r", stdin);
    freopen("d.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &tm);
    for (int i = 1; i <= n; i++)
    {
        adn(s, i, 1);
        adn(i, s, 0);
    }
    for (int i = 1; i <= m; i++)
    {
        adn(bh(i), t, 1);
        adn(t, bh(i), 0);
    }
    for (int i = 1; i <= tm; i++)
    {
        int srx, sry;
        scanf("%d%d", &srx, &sry);
        adn(srx, bh(sry), 1);
        adn(bh(sry), srx, 0);
        b[cntb - 1].bh = i;
    }
    solve();
    return 0;
}

/*
3 3 6
1 1
2 1
2 2
3 1
3 2
3 3
*/

By 智障 Cansult