[USACO 4.4] Pollutant Control [最小割]

ajcxsu
ajcxsu 2018年09月06日
  • 111 次阅读

似乎不是普通的最小割?

Problem

最小割
求最少边前提下,字典序最小方案

$n\leq 35$

Solution

第一问:https://www.luogu.org/blog/five20/solution-p1344

第二问:
以编号顺序枚举删边,查看边是否属于最小割
如果是,则将边永久删去,显然最小割也得减去这个权值,然后接着枚举下面的边是否属于新的最小割

这个正确性应该还是能够理解的

/*
ID: a1162731
TASK: milk6
LANG: C++11
*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=33;
ll e[N][N], bak[N][N], ed[1001][3];

int fl[N], n;
queue<int> qu;
bool bfs() {
    memset(fl, 0, sizeof(fl)), fl[1]=1;
    qu.push(1);
    int na;
    while(!qu.empty()) {
        na=qu.front(), qu.pop();
        for(int i=1;i<=n;i++)
            if(e[na][i] && !fl[i]) fl[i]=fl[na]+1, qu.push(i);
    }
    return fl[n];
}
int dfs(int x, ll op) {
    if(x==n) return op;
    ll flow=0;
    for(int i=1;i<=n;i++)
        if(fl[i]==fl[x]+1 && e[x][i]) {
            int d=dfs(i, min(op-flow, e[x][i]));
            flow+=d, e[x][i]-=d, e[i][x]+=d;
        }
    if(!flow) fl[x]=0;
    return flow;
}

int main() {
    #ifndef LOCAL
    freopen("milk6.in","r",stdin);
    freopen("milk6.out","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int m;
    cin>>n>>m;
    int u, v;
    ll w;
    for(int i=0;i<m;i++) cin>>u>>v>>w, e[u][v]+=w*1001+1, ed[i][0]=u, ed[i][1]=v, ed[i][2]=w;
    memcpy(bak, e, sizeof(e));
    ll tot=0;
    while(bfs()) tot+=dfs(1, 0x3f3f3f3f);
    cout<<tot/1001<<' '<<tot%1001<<endl;
    ll nflow;
    for(int i=0;i<m;i++) {
        u=ed[i][0], v=ed[i][1], w=ed[i][2];
        memcpy(e, bak, sizeof(bak)), e[u][v]-=w, nflow=0;
        while(bfs()) nflow+=dfs(1, 0x3f3f3f3f);
        if(nflow+w==tot) cout<<i+1<<endl, bak[u][v]-=w, tot-=w;
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol-usaco-milk6.html
本文采用 CC BY-NC-SA 3.0 协议进行许可