BZOJ1280: Emmy卖猪pigs

https://lydsy.com/JudgeOnline/problem.php?id=1280

分析:

这题感觉还好，因为是有时间顺序，所以拆点做最大流即可。
具体地我们让当前层每一个猪圈连向下一层，钥匙的猪圈用inf无向边连上。
看题解之后发现自己菜了，直接从人到人连边就完事了。
不过我过了就没改

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

#define inf 0x3f3f3f3f

#define N 200050

#define M 2000050

typedef double f2;

namespace Dinic {

	int head[N],to[M],nxt[M],flow[M],dep[N],Q[N],cnt=1;

	const int S=N-1,T=N-2;

	inline void add(int u,int v,int f) {

		to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f;

		to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0;

	}

	bool bfs() {

		memset(dep,0,sizeof(dep));

		int l=0,r=0; dep[S]=1;

		Q[r++]=S;

		while(l<r) {

			int x=Q[l++],i;

			for(i=head[x];i;i=nxt[i]) if(!dep[to[i]]&&flow[i]) {

				dep[to[i]]=dep[x]+1; if(to[i]==T) return 1; Q[r++]=to[i];

			}

		}return 0;

	}

	int dfs(int x,int mf) {

		if(x==T) return mf;

		int i,nf=0;

		for(i=head[x];i;i=nxt[i]) if(dep[to[i]]==dep[x]+1&&flow[i]) {

			int tmp=dfs(to[i],min(mf-nf,flow[i]));

			if(!tmp) dep[to[i]]=0;

			nf+=tmp; flow[i]-=tmp; flow[i^1]+=tmp;

			if(nf==mf) break;

		}

		return nf;

	}

	int dinic() {

		int f=0,mxf=0;

		while(bfs()) {

			while((f=dfs(S,inf))) mxf+=f;

		}return mxf;

	}

}

int n,m,idx[1050][1050],tt[1050];

int main() {

	using namespace Dinic;

	scanf("%d%d",&m,&n);

	int i,j,x,y;

	for(i=1;i<=n;i++) for(j=1;j<=m;j++) idx[i][j]=++idx[0][0];

	for(i=1;i<=m;i++) {

		scanf("%d",&x); add(S,idx[1][i],x);

	}

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

		scanf("%d",&x);

   		for(j=1;j<=x;j++) scanf("%d",&tt[j]);

   		sort(tt+1,tt+x+1);

   		for(j=1;j<=x;j++) {

   			add(idx[i][tt[j]],n*m+i,inf);

   		}

   		if(i<m) {

   			for(j=1;j<=m;j++) add(idx[i][j],idx[i+1][j],inf);

   			for(j=1;j<x;j++) add(idx[i+1][tt[j]],idx[i+1][tt[j+1]],inf),add(idx[i+1][tt[j+1]],idx[i+1][tt[j]],inf);

   		}

   		scanf("%d",&y);

   		add(n*m+i,T,y);

	}

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

}

巴特西

BZOJ1280: Emmy卖猪pigs

BZOJ1280: Emmy卖猪pigs

最新文章

热门文章