题意
滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。
由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。
n<=100
分析
有上下界网络流处女题。。。
显然是每条边的下界均为1上界均为inf，然后跑最小流即可。
最小流：
建立超级源ss和超级汇tt，先跑一遍可行流，设其为sum，然后把ss有关的边和与tt有关的边还有t到s的连边都删掉，然后连接ss−>t和s−>tt，跑一遍最大流，设为ans，那么答案即为sum-ans.
这是因为流完可行流之后原图中会有一些多出来的流，那么就要尽量的退流。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 225
#define inf 0x3f3f3f3f
using namespace std;
int n,cnt,s,t,ss,tt,last[N],dis[N],d[N],ans;
struct edge{int to,c,next;}e[N*N*5];
queue <int> q;
void addedge(int u,int v,int c)
{
e[++cnt].to=v;e[cnt].c=c;e[cnt].next=last[u];last[u]=cnt;
e[++cnt].to=u;e[cnt].c=0;e[cnt].next=last[v];last[v]=cnt;
}
bool bfs()
{
memset(dis,0,sizeof(dis));
dis[ss]=1;
while (!q.empty()) q.pop();
q.push(ss);
while (!q.empty())
{
int u=q.front();
q.pop();
for (int i=last[u];i;i=e[i].next)
if (e[i].c&&!dis[e[i].to])
{
dis[e[i].to]=dis[u]+1;
if (e[i].to==tt) return 1;
q.push(e[i].to);
}
}
return 0;
}
int dfs(int x,int maxf)
{
if (x==tt||!maxf) return maxf;
int ret=0;
for (int i=last[x];i;i=e[i].next)
if (e[i].c&&dis[e[i].to]==dis[x]+1)
{
int f=dfs(e[i].to,min(maxf-ret,e[i].c));
e[i].c-=f;
e[i^1].c+=f;
ret+=f;
if (ret==maxf) break;
}
return ret;
}
int main()
{
scanf("%d",&n);
cnt=1;
for (int i=1;i<=n;i++)
{
int x,y;
scanf("%d",&x);
for (int j=1;j<=x;j++)
{
scanf("%d",&y);
d[i]--;d[y]++;
addedge(i,y,inf);
}
}
s=n+1;t=s+1;
ss=t+1;tt=ss+1;
for (int i=1;i<=n;i++)
{
addedge(s,i,inf);addedge(i,t,inf);
if (d[i]>0) addedge(ss,i,d[i]);
else if (d[i]<0) addedge(i,tt,-d[i]);
}
addedge(t,s,inf);
while (bfs()) dfs(ss,inf);
ans=e[cnt].c;
e[cnt].c=e[cnt^1].c=0;
for (int i=last[ss];i;i=e[i].next) e[i].c=e[i^1].c=0;
for (int i=last[tt];i;i=e[i].next) e[i].c=e[i^1].c=0;
addedge(ss,t,inf);addedge(s,tt,inf);
while (bfs()) ans-=dfs(ss,inf);
PRintf("%d",ans);
return 0;
}
