luogu2754 家园

网络流大神题

刚看到这道题的一瞬间我就知道我跪掉了，完全没思路啊。

挣扎了一个多小时愣是想不出来，看题解。感叹这题太牛逼的话我就不多说了，讲一下思路吧。

我们做这个题要有两个知识储备：

1.爱因斯坦的相对论

2.分层建图的思想

关于相对论我就不多科普了，但是这个题的确要用到类似的思想。举个栗子，这一秒的asia已经不是上一秒的asia了，他有可能更胖了，也有可能更神了，对不对？(手动@victorique)

放到这道题来说，就是我们可以把每一个单位时间的太空站看做不同的太空站。对于一个时刻的太空站上面的人来说，下一个时刻他可以留在太空站，也可以乘坐飞船到下一个太空站。所以我们要把每一个时刻的太空站与下一个时刻的太空站连一条inf的边，然后和下一时刻的下一站连一条为飞船承载人数的边。

这就要用到分层建图的思想。我们把这个图看做分层的，每一层都有一个自己的源点和汇点。然后从超级源向每一层的源点连一条inf，从超级汇向每一层的汇点连一条inf，就OK了。然后我们枚举每一天，看看这一天能不能有超过k个人到达汇点，如果有就退出。

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define big (1000000000 + 10)
#define maxn (100000 + 10)
using namespace std;
int dis[maxn],head[maxn],cur[maxn];
int cnt,n,m,k,ans,tot,s,t=1001;
int read(){
	char c;int r=0,f=1;
	c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9'){
		r=(r*10)+(c^48);
		c=getchar();
	}
	return r*f;
}
struct node{
	int key,num;
	int round[20];
}p[maxn];
struct edge{
	int next,to,dis;
}ljb[maxn];
void add_edge(int x,int y,int z){
	ljb[++cnt].next=head[x];
	ljb[cnt].to=y;
	ljb[cnt].dis=z;
	head[x]=cnt;
}
void add(int x,int y,int z){
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
bool bfs(){
	for (int i=s;i<=t;i++) dis[i]=-1;
	q.push(s); dis[s]=0;
	while (!q.empty()){
		int x=q.front(); q.pop();
		for (int i=head[x];i!=-1;i=ljb[i].next){
			int y=ljb[i].to;
			if (dis[y]==-1 && ljb[i].dis>0){
				dis[y]=dis[x]+1;
				q.push(y);
			}
		}
	}
	if (dis[t]!=-1) return 1;
	return 0;
}
int dfs(int x,int low){
	if (x==t) return low;
	for (int i=head[x];i!=-1;i=ljb[i].next){
		int y=ljb[i].to;
		if (dis[y]==dis[x]+1 && ljb[i].dis>0){
			int flow=dfs(y,min(low,ljb[i].dis));
			if (flow){
				ljb[i].dis-=flow;
				ljb[i^1].dis+=flow;
				return flow;
			}
		}
	}
	return 0;
}
int main(){
	n=read();m=read();k=read();
	n+=2; 
	for (int i=1;i<=m;i++){
		p[i].key=read();p[i].num=read();
		for (int j=0;j<p[i].num;j++){
			p[i].round[j]=read();
			p[i].round[j]+=2;
		}
	}
	for (int i=s;i<=t;i++) head[i]=-1;cnt=-1;
	int day=0;
	while (day<30){
		add(day*n+1,t,big);
		add(s,day*n+2,big);
		if (day){
			for (int i=1;i<=n;i++) add((day-1)*n+i,day*n+i,big);
			for (int i=1;i<=m;i++){
				int x=p[i].round[(day-1)%p[i].num];
				int y=p[i].round[day%p[i].num];
				add((day-1)*n+x,day*n+y,p[i].key); 
			} 
			while (bfs()){
				for (int i=s;i<=t;i++) cur[i]=head[i];
				do{
					tot=dfs(s,big);
					ans+=tot;
				}
				while (tot);
			}
		}
		if (ans>=k) break;
		++day;
	}
	printf("%d",(day==30)?0:day);
}

家园解题报告

建图相对论

luogu2754 家园