[USACO 4.4] Pollutant Control [最小割]
似乎不是普通的最小割?
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://pst.iorinn.moe/archives/sol-usaco-milk6.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆