「网络流24题」家园

发表于 | 分类于 | | 浏览量： 次

你必须从四维空间的角度来解这一题…

传送门

洛谷P2754

LOJ6015

题解

此题的重难点在于建模。

不难发现，如果单单考虑空间，这题的模型还是难以建立。

所以需要将时间也考虑在内，从四维空间的角度来建模。（什么鬼？？？）

设图中的每一个节点都表示某一个时间上的一个星球，比如“第$i$天的第$j$个星球”。

考虑宇宙飞船的飞行，其实就是在四维空间内穿梭，每一次飞行相当于“从第$i$天的第$j$个星球飞往第$i+1$天的第$k$个星球”。

然后建模就很方便了。

对于第$i​$天的星球$j​$，都连向第$i+1​$天的星球$j​$，容量为$+\infty​$。

弄一个源，连向每一天的地球；再由每一天的月球连向一个汇，容量均为为$+\infty$。

对于一次飞行，在起点与终点之间连一条容量为飞船大小的边。

然后最大流就是当前最多能运送的人员数量。

于是乎就可以从小到大枚举答案，每次答案增加时就在网络中加入一套新的节点和边。

当最大流大于等于人数的时候就行了。

由于每次都是在上一次的基础之上继续刷最大流，用Dinic会比较快。（网络流管什么时间复杂度）

如果地球和月球不在一个联通块里，就无解，通过并查集可以解决。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=12000,maxe=31000,inf=0x3F3F3F3F;
int n,m,k,S=1,T=2,tot,lnk[maxn],dep[maxn],son[maxe],nxt[maxe],cap[maxe],que[maxn],ans,MF,fa[100];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y,int z){tot++;son[tot]=y;cap[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
struct SpaceShip{int r,S[20],H;}A[25];
inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline void Merge(int x,int y)
{
	if(getfa(x)==getfa(y)) return;
	fa[fa[x]]=fa[y];
}
inline int id(int x)
{
	if(x==0) return 1;
	if(x==-1) return 2;
	return x+2;
}
int DFS(int now,int lim)
{
	if(lim==0||now==T) return lim;
	int ret=0;
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(dep[now]+1==dep[son[i]])
		{
			int tep=DFS(son[i],min(lim,cap[i]));
			ret+=tep;
			cap[i]-=tep;
			cap[(i&1)?i+1:i-1]+=tep;
		}
	}
	return ret;
}
inline void Dinic()
{
	while(true)
	{
		memset(dep,63,sizeof(dep));
		int hed=0,til=1;
		que[1]=S;dep[S]=1;
		while(hed!=til)
		{
			hed++;
			for(int i=lnk[que[hed]];i;i=nxt[i])
			{
				if(cap[i]>0&&dep[que[hed]]+1<dep[son[i]])
				{
					dep[son[i]]=dep[que[hed]]+1;
					til++;que[til]=son[i];
				}
			}
		}
		if(dep[T]==inf) return;
		MF+=DFS(S,inf);
	}
}
int main()
{
	n=read();m=read();k=read();
	for(int i=1;i<=n+2;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		A[i].H=read();A[i].r=read();
		for(int j=1;j<=A[i].r;j++) A[i].S[j]=read();
		for(int j=1;j<A[i].r;j++) Merge(id(A[i].S[j]),id(A[i].S[j+1]));
	}
	if(getfa(id(0))!=getfa(id(-1))){printf("%d\n",0);return 0;}
	add_e(S,3,inf);add_e(3,S,0);add_e(4,T,inf);add_e(T,4,0);
	while(true)
	{
		ans++;
		add_e(S,ans*(n+2)+3,inf);
		add_e(ans*(n+2)+3,S,0);
		add_e(ans*(n+2)+4,T,inf);
		add_e(T,ans*(n+2)+4,0);
		for(int i=1;i<=m;i++)
		{
			int a=(ans-1)*(n+2)+2+id(A[i].S[(ans-1)%A[i].r+1]),b=ans*(n+2)+2+id(A[i].S[ans%A[i].r+1]);
			add_e(a,b,A[i].H);add_e(b,a,0);
		}
		add_e((ans-1)*(n+2)+3,ans*(n+2)+3,inf);
		add_e(ans*(n+2)+3,(ans-1)*(n+2)+3,0);
		add_e((ans-1)*(n+2)+4,ans*(n+2)+4,inf);
		add_e(ans*(n+2)+4,(ans-1)*(n+2)+4,0);
		for(int i=1;i<=n;i++)
		{
			int a=(ans-1)*(n+2)+2+i+2,b=ans*(n+2)+2+i+2;
			add_e(a,b,inf);add_e(b,a,0);
		}
		Dinic();
		if(MF>=k){printf("%d\n",ans);return 0;}
	}
	return 0;
}