USACO milk6 最小割

这道题的意思的大意是给你一个有向图以及对应的边权， 求出源点到汇点的最小割， 要求边数最小，当变数相同的时候要求字典序最小。由于最多有1000条边， 因此我们给边权*1001+1这样求出最大流后mod1001就是最小割的边数， div1001就是最小割，求解最小割的边我们可以去掉一条边将新的最大流和这一条边在的时候的最大流作比较， 如果新的最大流刚好少了所去掉边的边权那么这条边就是最小割中的点，注意求出最小割的边以后要将这条边去掉得到新图再求解。代码如下：

/*
    ID: m1500293
    LANG: C++
    PROG: milk6
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;
typedef long long LL;
const int maxn = 35;

struct Dinic
{
    int n;       //n¸ö¶¥µã
    struct edge
    {
        int from, to;
        LL cap;
    };
    vector<int> G[maxn];
    vector<edge> e;
    int level[maxn], iter[maxn];
    void init()
    {
        for(int i=0; i<=n; i++) G[i].clear();
        e.clear();
    }
    void add_edge(int u, int v, LL cap)
    {
        e.push_back((edge){u, v, cap});
        e.push_back((edge){v, u, 0});
        int m = e.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    void bfs(int s)
    {
        memset(level, -1, sizeof(level));
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty())
        {
            int u = que.front();
            que.pop();
            for(int i=0; i<G[u].size(); i++)
            {
                edge &te = e[G[u][i]];
                if(te.cap>0 && level[te.to]<0)
                {
                    level[te.to] = level[u] + 1;
                    que.push(te.to);
                }
            }
        }
    }
    LL dfs(int v, int t, LL f)
    {
        if(v == t) return f;
        for(int &i=iter[v]; i<G[v].size(); i++)
        {
            edge &tpe = e[G[v][i]];
            if(tpe.cap>0 && level[v]<level[tpe.to])
            {
                LL d = dfs(tpe.to, t, min(f, tpe.cap));
                if(d > 0)
                {
                    tpe.cap -= d;
                    e[G[v][i]^1].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    LL max_flow(int s, int t)
    {
        LL flow = 0;
        for(;;)
        {
            bfs(s);
            if(level[t]<0) return flow;
            memset(iter, 0, sizeof(iter));
            LL   f;
            while((f=dfs(s, t, 0x3fffffff)) > 0)
                flow += f;
        }
    }
} di, di2;
int main()
{
    //freopen("milk6.in", "r", stdin);
    //freopen("milk6.out", "w", stdout);
    int N, M;        //顶点的数量
    cin>>N>>M;
    di.n = N;
    di.init();
    for(int i=1; i<=M; i++)
    {
        int u, v;
        LL c;
        cin>>u>>v>>c;
        di.add_edge(u, v, c*(M+1)+1);
    }
    di2 = di;
    LL f = di2.max_flow(1, N);
    int car[1010], ncar=0;
    LL da=0;
    for(int i=0; i<M; i++)   //一共有m条边
    {
        di2 = di;
       // cout<<"di2= "<<di2.max_flow(1, N)<<endl;
        LL cp = di2.e[i*2].cap;
        di2.e[i*2].cap = 0;
        LL f1 = di2.max_flow(1, N);
        //cout<<"f1: "<<f1<<"cp: "<<cp<<endl;
        if(cp+f1 == f)   //这条边在答案里面
        {
            car[ncar++] = i+1;
            da += (cp-1)/(M+1);
            f -= di.e[i*2].cap;    //找到最小割的边以后要将其去掉 即最大流减少
            di.e[i*2].cap = 0;     //正向边容量为0
        }
    }
    cout<<da<<' '<<ncar<<endl;
    for(int i=0; i<ncar; i++)
        printf("%d\n", car[i]);
    return 0;
}

原文链接: https://www.cnblogs.com/xingxing1024/p/5173254.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍