「CTSC1999」家园 - 按时间拆点+动态加点最大流

题目大意

    现有$n$个太空站处于地球与月球之间（编号$1\ldots n$），$m$艘公共交通太空船在其中来回穿梭，每个太空站$S_i$可容纳无限的人，每艘太空船$p_i$只可容纳$H_{p_i}$人。对于每一艘太空船$p_i$，将周期性地停靠一系列的太空站（$S_{i_1},S_{i_2},\ldots,S_{i_r}$），如：（$1,3,4$）表示停靠太空站$1\,3\,4\,1\,3\,4\,1\,3\,4\ldots。任一艘太空船从任一个太空站驶往另一个任意的太空站耗时为$1$。人只能在太空船停靠太空站（或地球、月球）时上船或下船。初始时的人全在地球上，太空船全在初始站（太空船$p_i$处于$S_{i_1}$），目标是让所有的人尽快地全部转移到月球上。

---

题目分析

按照时间对每个星球拆点，枚举时间动态加边，动态求网络流，当剩余的运输人数$\le0$即可输出答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=5005;

struct Edge {
	int from,to,cap,flow;
	Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v) {
		edges.push_back(Edge(x,y,v,0));
		edges.push_back(Edge(y,x,0,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		memset(vst,0,sizeof(vst));
		memset(dist,0,sizeof(dist));
		queue<int>Q;
		Q.push(t);
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&e.cap>e.flow) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	int dfs(int Now,int a) {
		if(Now==t||a==0)return a;
		int flow=0;
		for(int& i=cur[Now]; i<G[Now].size(); i++) {
			Edge& e=edges[G[Now][i]];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			int nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				e.flow+=nextflow;
				edges[G[Now][i]^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		int flow=0;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,INT_MAX);
		}
		return flow;
	}
} dinic;

int n,m,k,map[25][25],Num[25],People[25];
#define All(cnt) (cnt)*(n+2)

int main() {
	n=Get_Int();
	m=Get_Int();
	k=Get_Int();
	for(int i=1; i<=m; i++) {
		People[i]=Get_Int();
		Num[i]=Get_Int();
		for(int j=1; j<=Num[i]; j++) {
			map[i][j]=Get_Int();
			if(map[i][j]==-1)map[i][j]=n+1;
		}
	}
	for(int i=1; i<=80; i++) {
		for(int j=0; j<=n+1; j++)dinic.AddEdge(All(i-1)+j,All(i)+j,INT_MAX/2); //停留
		for(int j=1; j<=m; j++)dinic.AddEdge(All(i-1)+map[j][(i-1)%Num[j]+1],All(i)+map[j][i%Num[j]+1],People[j]); //运输
		k-=dinic.maxflow(0,All(i)+n+1);
		if(k<=0) {
			printf("%d",i);
			return 0;
		}
	}
	puts("0");
	return 0;
}