【BZOJ2502】清理雪道

Description

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。

由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

Input

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行，描述1~n号地点出发的斜坡，第i行的第一个数为m (0 <= m < n) ，后面共有m个整数，由空格隔开，每个整数a互不相同，代表从地点i下降到地点a的斜坡。每个地点至少有一个斜坡与之相连。

Output

输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

Sample Input

8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0

Sample Output

题解：最小流做法：先建图，设源点s，汇点t，新建源点S，汇点T

从t向s连一条上界INF的边，跑从S到T的有上下界的网络流，然后记录从汇点到源点的那条边的反向边的容量x1，

再删掉S和T，跑从t到s正常的最大流x2，x1-x2即为答案

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

using namespace std;

int n,cnt,S,T,ans;

int in[110],to[100000],next[100000],val[100000],head[110],d[110];

queue<int> q;

int dfs(int x,int mf)

{

	if(x==T)	return mf;

	int i,k,temp=mf;

	for(i=head[x];i!=-1;i=next[i])

	{

		if(d[to[i]]==d[x]+1&&val[i])

		{

			k=dfs(to[i],min(temp,val[i]));

			if(!k)	d[to[i]]=0;

			val[i]-=k,val[i^1]+=k,temp-=k;

			if(!temp)	break;

		}

	}

	return mf-temp;

}

int bfs()

{

	int i,u;

	while(!q.empty())	q.pop();

	memset(d,0,sizeof(d));

	q.push(S),d[S]=1;

	while(!q.empty())

	{

		u=q.front(),q.pop();

		for(i=head[u];i!=-1;i=next[i])

		{

			if(!d[to[i]]&&val[i])

			{

				d[to[i]]=d[u]+1;

				if(to[i]==T)	return 1;

				q.push(to[i]);

			}

		}

	}

	return 0;

}

void add(int a,int b,int c)

{

	to[cnt]=b;

	val[cnt]=c;

	next[cnt]=head[a];

	head[a]=cnt++;

}

int main()

{

	memset(head,-1,sizeof(head));

	scanf("%d",&n);

	S=n+2,T=n+3;

	int i,j,a,b,c;

	for(i=1;i<=n;i++)

	{

		scanf("%d",&a);

		add(0,i,1<<30),add(i,0,0);

		add(i,n+1,1<<30),add(n+1,i,0);

		for(j=1;j<=a;j++)

		{

			scanf("%d",&b);

			in[i]--,in[b]++;

			add(i,b,(1<<30)-1),add(b,i,0);

		}

	}

	for(i=1;i<=n;i++)

	{

		if(in[i]>0)	add(S,i,in[i]),add(i,S,0);

		if(in[i]<0)	add(i,T,-in[i]),add(T,i,0);

	}

	add(n+1,0,1<<30),add(0,n+1,0);

	while(bfs())	dfs(S,1<<30);

	for(i=head[S];i!=-1;i=next[i])	val[i]=val[i^1]=0;

	for(i=head[T];i!=-1;i=next[i])	val[i]=val[i^1]=0;

	ans=val[cnt-1];

	val[cnt-1]=val[cnt-2]=0;

	S=n+1,T=0;

	while(bfs())	ans-=dfs(S,1<<30);

	printf("%d",ans);

	return 0;

}

雪道