神奇脑洞题解——USACO追查坏牛奶(CSGO894)

COGS的这一题是超级满配版本

比洛谷的要强力的多：894. 追查坏牛奶 - COGS

额外要求是：求出最小割流量，同时求出割边最小，同时字典序最小的方案

输出割掉的边

最小割流量好求，最小割边的数量也好求，但同时确定哪条边不太好弄，因为存在方法互斥

首先：最小割流量就是跑最大流的结果

求最小割边的数量，需要在刚刚跑完最大流的网络上

把所有的满流边流量重新标记为1，不满流的重新标记为INF

在新的网络上跑一次最大流

这个时候得到的流量就是最小割边的数量

正确性：

满流边一定是某条流量通路的瓶颈路(虽然不一定是唯一瓶颈路)

把满流的边标记成1去跑增广路

得到的结果就是没有公共边的流量通路的条数(因为公共边只允许通过1点流量被计算一次)

那么就给这这些流量通路每个断开一条边即可(如果存在公共边先断开公共边)

如何求最小字典序的方案：

在最小割的情况下

首先要记住，我们一定是优先断开边权最大的必须满流边(删去这条边后，重新对整个网络跑最大流，最大流量会减小这个边的边权那么多(也就是这条边的传递作用无可替代))

那么找最小字典序方案也出来了：在正常的图上，先跑一次最大流

然后枚举所有边（首先把边按照边权(大到小)-字典序(小到大)两个关键字排序）

先复原整个网络到未增广形态

然后尝试删去这条边，看最大流结果减少的是否是这条边流量那么多

如果是，说明这是关键边，记录这条边会被删除(贪心保证了删除的边数目最少，因为这条边满流，不删它就要删和它在同一支流的多条边) 把这条边永久性删除，并将最大流的结果减小(该边的流量)那么多

这就导致你需要先用正常的边权跑DINIC，再用1和INF的边权跑DINIC，再用正常的边权去找应当被删除的边

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define int long long int
using namespace std;
const int N = 100, M = 40000;
int head[N], val[M], to[M], nxt[M],vals[M],id[M];
int layer[N],cnt=1,n,m,S,T;
void ADD(int x, int y, int v,int idx)
{
    to[++cnt] = y;
    val[cnt] = v;
    nxt[cnt] = head[x];
    head[x] = cnt;
    vals[cnt] = v;
    id[cnt] = idx;
    to[++cnt] = x;
    val[cnt] = 0;
    nxt[cnt] = head[y];
    head[y] = cnt;
    vals[cnt] = 0;
    id[cnt] = idx;
}
bool BFS()
{
    queue<int> q;
    memset(layer, 0, sizeof(layer));
    q.push(S);
    layer[S] = 1;
    while (q.size())
    {
        int now = q.front();
        q.pop();
        for (int i = head[now]; i; i = nxt[i])
        {
            int y = to[i];
            if (layer[y] || !val[i])
                continue;
            layer[y] = layer[now] + 1;
            q.push(y);
        }
    }
    if (layer[T])
        return 1;
    return 0;
}
int Update(int x, int flow)
{
    if (x == T)
    {
        return flow;
    }
    int rest = flow;
    for (int i = head[x]; i; i = nxt[i])
    {
        int y = to[i];
        if (layer[y] != layer[x] + 1 || !val[i])
            continue;
        int k = Update(y, min(rest, val[i]));
        if (!k)
        {
            layer[y] = 0;
            continue;
        }
        rest -= k;
        val[i] -= k;
        val[i ^ 1] += k;
    }
    return flow - rest;
}
int Dinic()
{
    int kel,maxflow=0;
    while (BFS())
    {
        while (kel = Update(S, 0x3f3f3f3f))
        {
            //cout << "S";
            maxflow += kel;
        }
    }
    return maxflow;
}
void Change1()
{
    for (int i = 2; i <= cnt; i += 2)
    {
        if (val[i])
        {
            val[i] = 0x3f3f3f3f;
            val[i ^ 1] = 0;
        }
        else
        {
            val[i] = 1;
            val[i ^ 1] = 0;
        }
    }
}
struct EDGE
{
    int x, y, v,ids;
};
EDGE e[M];
bool Function(EDGE A, EDGE B)
{
    if (A.v == B.v)
        return A.ids < B.ids;
    return A.v > B.v;
}
signed main()
{
    freopen("milk6.in", "r", stdin);
    freopen("milk6.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    int a1, a2, a3;
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld%lld%lld", &a1, &a2, &a3);
        e[i].x = a1;
        e[i].y = a2;
        e[i].v = a3;
        e[i].ids = i;
        //ADD(a1, a2, a3);
    }
    sort(e + 1, e + 1 + m,Function);
    for (int i = 1; i <= m; i++)
    {
        ADD(e[i].x, e[i].y, e[i].v, e[i].ids);
    }
    S = 1;
    T = n;
    int MINCOST = Dinic();
    Change1();
    int MINLINE = Dinic();
    memcpy(val, vals, sizeof(val));
    int anss[M], tot = 0;
    printf("%lld %lld\n", MINCOST, MINLINE);
    for (int i = 2; i <= cnt; i+=2)
    {
        int STD = val[i];
        val[i] = 0;
        val[i ^ 1] = 0;
        int SDS = Dinic();
        if (SDS== MINCOST - STD)
        {
            anss[++tot] = id[i];
            MINCOST-=STD;
            vals[i] = 0;
            vals[i ^ 1] = 0;
        }
        memcpy(val, vals, sizeof(val));
        if (MINCOST == 0)
            break;
    }
    sort(anss + 1, anss + 1 + tot);
    for (int i = 1; i <= tot; i++)
    {
        printf("%lld\n", anss[i]);
    }
    return 0;
}