[文章目录]
Description
滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。n<=100 m<=n(n-1)/2
一开始以为是最长反链，实则覆盖的是边而不是点。
实际上等价于求原图的有上下界最小流，每条边的流量至少为1，s，t向个点连边询问s->t的最小流。
法1：不连t->s的边，求可行流，再连t->s求一遍可行流。反向弧流量即为答案。
法2：转化为无源汇可行流处理，先求原图的可行流，t->s的边的流量减去拆边后的t->s的最大流即为答案。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,s,t,ss,tt,S,T,ans,flo[110];
int head[110],to[30000],nxt[30000],f[30000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[110];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d",&n); int x,y; ss=n+1; tt=n+2; S=n+3; T=n+4;
for(int i=1;i<=n;++i)
{
scanf("%d",&x); if(x) add(i,T,x);
while(x--) scanf("%d",&y),add(i,y,inf),flo[y]++;
}
for(int i=1;i<=n;++i) if(flo[i]) add(S,i,flo[i]);
for(int i=1;i<=n;++i) add(ss,i,inf),add(i,tt,inf);
//***************************************
s=S; t=T; while(bfs()) dinic(s,inf); add(tt,ss,inf); while(bfs()) dinic(s,inf);
for(int i=head[tt];i;i=nxt[i]) if(to[i]==ss)
{
printf("%d",f[i^1]);
return 0;
}
/*add(tt,ss,inf); s=S; t=T; while(bfs()) dinic(s,inf);
for(int i=head[tt];i;i=nxt[i]) if(to[i]==ss) ans=f[i^1],f[i]=0,f[i^1]=0;
s=tt; t=ss; while(bfs()) ans-=dinic(s,inf);
printf("%d",ans);*/
return 0;
}