【洛谷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");
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注