[BZOJ5251][多省联测2018]劈配

bzoj

luogu

sol

从前往后依次加边，每次对一个人做完劈配后就把当前这个残余网络存下来。这样第二问就可以二分排在第几名然后check一下在对应排名的残余网络上还能不能再增广。

给网络流开结构体直接赋值美滋滋。

然后这样就可以根据评测机的实际情况获得\(60-80\)不等的好成绩。

一个显而易见的优化就是：对于一个人，如果他已经确认了选择某个志愿，那么不仅更靠后的志愿是没用的，更靠前的志愿也是没用的。

所以对于一个人我们只需要保留他选的那个志愿对应的那至多\(C\)条边，这样边数和时间复杂度都降下来了。

按照上面的思路就可以成功通过本题了。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int inf = 1e9;

const int N = 405;

int n,m,S,T,a[N][N],b[N],id[N],s[N],ans[N];

queue<int>Q;

struct edge{int to,nxt,w;};

struct net{

	edge a[N*30];

	int head[N],cnt,dep[N],cur[N];

	inline void init(){memset(head,0,sizeof(head));cnt=1;}

	inline void link(int u,int v,int w)

		{

			a[++cnt]=(edge){v,head[u],w};head[u]=cnt;

			a[++cnt]=(edge){u,head[v],0};head[v]=cnt;

		}

	inline bool bfs()

		{

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

			dep[S]=1;Q.push(S);

			while (!Q.empty())

			{

				int u=Q.front();Q.pop();

				for (int e=head[u];e;e=a[e].nxt)

					if (a[e].w&&!dep[a[e].to])

						dep[a[e].to]=dep[u]+1,Q.push(a[e].to);

			}

			return dep[T];

		}

	int dfs(int u,int f)

		{

			if (u==T) return f;

			for (int &e=cur[u];e;e=a[e].nxt)

				if (a[e].w&&dep[a[e].to]==dep[u]+1)

				{

					int tmp=dfs(a[e].to,min(a[e].w,f));

					if (tmp) {a[e].w-=tmp;a[e^1].w+=tmp;return tmp;}

				}

			return 0;

		}

	inline int dinic()

		{

			int res=0;

			while (bfs())

			{

				for (int i=1;i<=T;++i) cur[i]=head[i];

				while (int tmp=dfs(S,1)) res+=tmp;

			}

			return res;

		}

}G[N>>1];

inline bool cmp(int i,int j){return b[i]<b[j];}

int main()

{

	freopen("mentor.in","r",stdin);

	freopen("mentor.out","w",stdout);

	int Case=gi();gi();

	while (Case--)

	{

		n=gi();m=gi();S=n+m+1;T=S+1;

		G[0].init();

		for (int i=1,x;i<=m;++i) x=gi(),G[0].link(i+n,T,x);

		for (int i=1,j,res;i<=n;++i)

		{

			for (j=1;j<=m;++j) a[i][j]=b[j]=gi(),id[j]=j;

			sort(id+1,id+m+1,cmp);

			j=1;while (j<=m&&!b[id[j]]) ++j;

			for (res=1;res<=m;++res)

			{

				G[i]=G[i-1];G[i].link(S,i,1);

				while (j<=m&&b[id[j]]==res) G[i].link(i,id[j]+n,1),++j;

				if (G[i].dinic()) break;

			}

			printf("%d ",ans[i]=res);

		}

		puts("");

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

		{

			s[i]=gi();

			if (ans[i]<=s[i]) {printf("0 ");continue;}

			int l=0,r=i-1,res=0;

			while (l<=r)

			{

				int mid=l+r>>1;

				net tmp=G[mid];tmp.link(S,i,1);

				for (int j=1;j<=m;++j) if (a[i][j]&&a[i][j]<=s[i]) tmp.link(i,j+n,1);

				if (tmp.dinic()) res=l=mid+1;else r=mid-1;

			}

			printf("%d ",i-res);

		}

		puts("");

	}

	return 0;

}