HDU1853(有向图最小权环覆盖)

HDU1853

对于每条边$(u,v)$

把点$x$拆分为$x$(入点)和$x+n$(出点)

源点$s$连向点$u$,费用$0$

$v+n$连向汇点$t$,费用$0$

$u+n$连向$v$,费用边$(u,v)$的费用

所有边流量都是$1$

---

这样跑最小费用流,若最大流是$n$即可

因为所有入点都作为一条边的起点,所有出点都作为一条边的出点

就是说每个点都处在环中

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; const int inf=1e9; int n,m,s,t,flow[maxn],vis[maxn]; struct edge{ int to,nxt,flow,w; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v,int flow,int w){ d[++cnt]=(edge){v,head[u],flow,w},head[u]=cnt; d[++cnt]=(edge){u,head[v],0,-w},head[v]=cnt; } int dis[maxn],pre[maxn]; bool spfa() { for(int i=s;i<=t;i++) dis[i]=inf; dis[s]=0,flow[s]=inf; queue<int>q; q.push(s); while( !q.empty() ) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( dis[v]>dis[u]+d[i].w&&d[i].flow ) { dis[v]=dis[u]+d[i].w; flow[v]=min( flow[u],d[i].flow ); pre[v]=i; if( !vis[v] ) vis[v]=1,q.push(v); } } } return ( dis[t]!=inf ); } int main() { while( cin >> n >> m ) { s=0,t=n+n+1; for(int i=1;i<=m;i++) { int l,r,w; scanf("%d%d%d",&l,&r,&w); if( l==r ) continue; add(l,r+n,1,w); } for(int i=1;i<=n;i++) add(s,i,1,0),add(i+n,t,1,0); int ans=0,maxflow=0; while( spfa() ) { int i,x=t; ans+=flow[t]*dis[t],maxflow+=flow[t]; while( x!=s ) { i = pre[x]; d[i].flow-=flow[t], d[i^1].flow+=flow[t]; x = d[i^1].to; } } if( maxflow!=n ) ans=-1; cout << ans << '\n'; cnt=1; for(int i=0;i<=t;i++) head[i]=0; } }