【bzoj2502】清理雪道有上下界最小流

题目描述

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

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

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

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

输入

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

输出

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

样例输入

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

样例输出

题解

有源汇有上下界网络流“最小流”

题目中每条边都可看作上下界为[1,inf]的边。

对于每个节点x，加入s->x，容量为inf的边，加入x->t，容量为inf的边。

这样问题就转化为有源汇有上下界网络流。

再加t->s，容量为inf的边，就变为无源汇问题。

然后是求最小流。

最小流的实现方法参照 PoPoQQQ的博客，退流的思想很巧妙。

#include <cstdio>

#include <cstring>

#include <queue>

#define inf 0x3fffffff

using namespace std;

queue<int> q;

int head[110] , to[30000] , val[30000] , next[30000] , cnt = 1 , dis[110] , s , t , in[110];

void add(int x , int y , int z)

{

	to[++cnt] = y;

	val[cnt] = z;

	next[cnt] = head[x];

	head[x] = cnt;

}

bool bfs()

{

	int x , i;

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

	memset(dis , 0 , sizeof(dis));

	dis[s] = 1;

	q.push(s);

	while(!q.empty())

	{

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

		for(i = head[x] ; i ; i = next[i])

		{

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

			{

				dis[to[i]] = dis[x] + 1;

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

				q.push(to[i]);

			}

		}

	}

	return 0;

}

int dinic(int x , int low)

{

	if(x == t) return low;

	int temp = low , i , k;

	for(i = head[x] ; i ; i = next[i])

	{

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

		{

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

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

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

			if(!(temp -= k)) break;

		}

	}

	return low - temp;

}

int main()

{

	int n , i , c , y , ans , tempid;

	scanf("%d" , &n);

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

	{

		scanf("%d" , &c);

		while(c -- )

		{

			scanf("%d" , &y);

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

			add(i , y , inf) , add(y , i , 0);

		}

	}

	add(n + 1 , 0 , inf) , tempid = cnt , add(0 , n + 1 , 0);

	s = n + 2 , t = n + 3;

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

	{

		add(0 , i , inf) , add(i , 0 , 0);

		add(i , n + 1 , inf) , add(n + 1 , i , 0);

		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);

	}

	while(bfs()) dinic(s , inf);

	for(i = head[s] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;

	for(i = head[t] ; i ; i = next[i]) val[i] = val[i ^ 1] = 0;

	ans = val[tempid ^ 1];

	val[tempid] = val[tempid ^ 1] = 0;

	add(s , n + 1 , inf) , add(n + 1 , s , 0);

	add(0 , t , inf) , add(t , 0 , 0);

	while(bfs()) ans -= dinic(s , inf);

	printf("%d\n" , ans);

	return 0;

}

巴特西

【bzoj2502】清理雪道有上下界最小流

最新文章

热门文章

巴特西

【bzoj2502】清理雪道 有上下界最小流

最新文章

热门文章

【bzoj2502】清理雪道有上下界最小流