BZOJ2502 清理雪道【网络流】

tonyfang posted @ 2016年2月25日 20:04 in BZOJ with tags c++ OI , 236 阅读

Description

       滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。
由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。
 

Input

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

Output

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

Sample Input

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

Sample Output

4

HINT

 

Source

【题解】带上下界最小流,具体可以看《妈妈我终于会了最小流系列》

http://blog.csdn.net/popoqqq/article/details/48467349

# include <stdio.h>
# include <string.h>
# include <queue>

using namespace std;

const int M=1000010;
int S,T,SS,TT,head[M],c[M],next[M],to[M],flow[M],w[M],tot=1;
int n;
queue<int> q;
// remember: tot starts from 1

inline void add(int u,int v,int fl) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	flow[tot]=fl;
}

inline void Add(int u,int v,int fl) {
	add(u,v,fl);
	add(v,u,0);
}

inline void qc() {
	while(!q.empty()) q.pop();
}

inline bool bfs() {
	qc(); memset(c,-1,sizeof(c));
	q.push(S);c[S]=1;
	while(!q.empty()) {
		int top=q.front(); q.pop();
		for (int i=head[top];i;i=next[i]) {
			int _to=to[i];
			if(c[_to]>=0 || flow[i]==0) continue;
			c[_to]=c[top]+1;
			q.push(_to);
			if(_to==T) return 1;
		}
	}
	return 0;
}

inline int dfs(int x,int low) {
	if(x==T) return low;
	int fl,r=low;
	for (int i=head[x];i;i=next[i]) {
		int _to=to[i];
		if(c[_to]!=c[x]+1 || flow[i]==0) continue;
		fl=dfs(_to,min(r,flow[i]));
		r-=fl;
		flow[i]-=fl;
		flow[i^1]+=fl;
		if(!r) return low;
	}
	if(r==low) c[x]=-1;
	return low-r;
}

inline int dinic() {
	int ans=0;
	while(bfs()) ans+=dfs(S,200011300); 
	return ans; 
}

int deg[M];


int main() {
	scanf("%d",&n);
	S=102,SS=103,T=104,TT=105;
	for (int i=1,t,tt;i<=n;++i) {
		scanf("%d",&t);
		for (int j=1;j<=t;++j) {
			scanf("%d",&tt);
			deg[i]--;
			deg[tt]++;
			Add(i,tt,200011300);
		}
	}
	for (int i=1;i<=n;++i) {
		if(deg[i]>0) Add(S,i,deg[i]);
		if(deg[i]<0) Add(i,T,-deg[i]);
		Add(SS,i,200011300);
		Add(i,TT,200011300);
	}
	Add(TT,SS,200011300);
	dinic();
	int ans1=0;
	for (int i=head[S];i;i=next[i])
		flow[i]=flow[i^1]=0;
	for (int i=head[T];i;i=next[i])
		flow[i]=flow[i^1]=0;
	for (int i=head[TT];i;i=next[i]) {
		if(to[i]==SS) {
			ans1+=flow[i^1];
			flow[i]=flow[i^1]=0;
			break;
		}
	}
	Add(S,TT,200011300);
	Add(SS,T,200011300);
	int ans2=dinic();
	printf("%d\n",ans1-ans2);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter