文档章节

AtCoder AGC037D Sorting a Grid (二分图匹配)

o
 osc_wws45aot
发布于 2019/08/20 15:21
字数 1000
阅读 6
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目链接

https://atcoder.jp/contests/agc037/tasks/agc037_d

题解

这场D题终于不像AGC032D和AGC036D一样神仙了…… 还是可做的吧 虽然考场上没好好想赛后直接看题解了= =

考虑倒推,首先谁都能看出来第二次操作之后要让每一行是这一行对应元素的一个排列; 这样的话我们可以把数$i$最后应在的行视为它的颜色,第二次操作就是要把所有颜色$i$的数挪到第$i$列。 那么第一次操作之后,我们就是要让每列是颜色的一个排列。 考虑二分图匹配模型: 最关键的思路是从左往右考虑每一列 左边对每一行建一个点,右边对每种颜色建一个点 如果当前还没考虑的部分里这一行有色$j$, 那么连边$(i,j)$ 跑一遍Dinic确定这一行的颜色,然后下一行重复此过程 为什么这样一定能解出来?考虑对$M$归纳,还剩下$M$行、每种颜色恰有$M$个的时候,对于任何行的集合$S$, 其所包括的颜色数显然不小于$|S|$, 根据Hall定理,存在完美匹配,转化为$M-1$的情况。 简单分析可得时间复杂度$O(N^{3.5})$ (Dinic二分图匹配复杂度为边数乘以点数的平方根,默认$N,M$同阶)

代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

namespace NetFlow
{
	const int N = 202;
	const int M = 40400;
	const int INF = 1e7;
	struct Edge
	{
		int v,w,nxt,rev;
	} e[(M<<1)+3];
	int fe[N+3];
	int te[N+3];
	int dep[N+3];
	int que[N+3];
	int n,en;
	void addedge(int u,int v,int w)
	{
//		printf("addedge%d %d %d\n",u,v,w);
		en++; e[en].v = v; e[en].w = w;
		e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;
		en++; e[en].v = u; e[en].w = 0;
		e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;
	}
	bool bfs()
	{
		for(int i=1; i<=n; i++) dep[i] = 0;
		int head = 1,tail = 1; que[tail] = 1; dep[1] = 1;
		while(head<=tail)
		{
			int u = que[head]; head++;
			for(int i=fe[u]; i; i=e[i].nxt)
			{
				if(dep[e[i].v]==0 && e[i].w>0)
				{
					dep[e[i].v] = dep[u]+1;
					tail++; que[tail] = e[i].v;
				}
			}
		}
		return dep[2]!=0;
	}
	int dfs(int u,int cur)
	{
		if(u==2) {return cur;}
		int rst = cur;
		for(int i=te[u]; i; i=e[i].nxt)
		{
			if(dep[e[i].v]==dep[u]+1 && e[i].w>0 && rst>0)
			{
				int flow = dfs(e[i].v,min(rst,e[i].w));
				if(flow>0)
				{
					e[i].w-=flow; e[e[i].rev].w += flow; rst-=flow;
					if(e[i].w>0) {te[u] = i;}
					if(rst==0) {return cur;}
				}
			}
		}
		if(cur==rst) {dep[u] = 0;}
		return cur-rst;
	}
	void dinic(int _n)
	{
		n = _n;
		int ret = 0;
		while(bfs())
		{
			for(int i=1; i<=n; i++) te[i] = fe[i];
			ret += dfs(1,INF);
		}
//		printf("ret=%d\n",ret);
	}
	void clear()
	{
		for(int i=1; i<=en; i++) e[i].v = e[i].w = e[i].nxt = e[i].rev = 0;
		for(int i=1; i<=n; i++) dep[i] = fe[i] = que[i] = te[i] = 0;
		n = en = 0;
	}
}
using NetFlow::e;
using NetFlow::fe;
using NetFlow::addedge;
using NetFlow::dinic;
using NetFlow::clear;

const int N = 100;
int a[N+3][N+3];
int b[N+3][N+3];
vector<int> vec[N+3][N+3];
int tmp[N+3];
int n,m;

int getclr(int x) {return (x-1)/m+1;}
bool cmp(int x,int y) {return getclr(x)<getclr(y);}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&a[i][j]),vec[i][getclr(a[i][j])].push_back(a[i][j]);
	for(int k=1; k<=m; k++)
	{
		for(int i=1; i<=n; i++)
		{
			for(int j=1; j<=n; j++)
			{
				if(vec[i][j].size()>0) {addedge(i+2,j+n+2,1);}
			}
			addedge(1,i+2,1);
			addedge(i+n+2,2,1);
		}
		dinic(n+n+2);
		for(int i=1; i<=n; i++)
		{
			int u = i+2;
			for(int j=fe[u]; j; j=e[j].nxt)
			{
				int v = e[j].v-n-2;
				if(v>0 && v<=n && e[j].w==0)
				{
//					printf("(%d,%d)\n",i,v);
					b[i][k] = *vec[i][v].rbegin();
					vec[i][v].pop_back();
				}
			}
		}
		clear();
	}
	for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) printf("%d ",b[i][j]); puts("");}
	for(int j=1; j<=m; j++)
	{
		for(int i=1; i<=n; i++) tmp[i] = b[i][j];
		sort(tmp+1,tmp+n+1,cmp);
		for(int i=1; i<=n; i++) b[i][j] = tmp[i];
	}
	for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) printf("%d ",b[i][j]); puts("");}
	return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
AtCoder Grand Contest 037 学习

考场状况 第一把 AtCoder, 把我校的省队大佬以及另外两个兄弟拉进来组了个车队。两个小老弟原定帮我解决ABC, 最后他们就做了AB, 省队大佬率先切掉E, 我切掉了CD. 没想到名次这么靠前,下回不...

osc_rnrep3wi
2019/08/21
1
0
做题记录

UOJ 176 新年的繁荣 一个奇特的想法。我们考虑从大到小枚举边权,显然每次合并的话只用考虑比当前枚举的i多一位的数 因为如果两个数有其它的重叠部分 就一定会在之前被合并掉了 复杂度:$O(...

osc_n3qafw1d
2019/08/18
2
0
POJ 1486 Sorting Slides 题解 《挑战程序设计竞赛》

POJ 1486 Sorting Slides故纸堆:桌上有n张幻灯片杂乱地叠在一起,给出每张幻灯片的边界和页码坐标,求在不翻动的情况下那些页码可以确定?3.5借助水流解决问题的网络流 二分图匹配如果页码u...

hankcs
2015/01/18
27
0
Atcoder/Topcoder 口胡记录

Atcoder/Topcoder 理论 AC Atcoder的❌游戏示范 兴致勃勃地打开一场 AGC 看 A 题,先 WA 一发,然后花了一年时间 Fix。 看 B 题,啥玩意?这能求? 睡觉觉。 emmmmm 虽然这些副本里的怪一点也...

osc_ugeljcjn
2019/07/22
2
0
【AtCoder】ARC088

C - Multiple Gift 题解 首项是X,每次乘个2,暴力统计 代码 D - Wide Flip 题解 从大到小枚举K(也可以二分)如果$2K <= N$,此时$K$一定合法否则看前$K$个和后$K$个交出来的中间一段,这段...

osc_3fk0fbkm
2018/12/24
5
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud开发人员如何解决服务冲突和实例乱窜?(IP实现方案)

点击上方“陶陶技术笔记”关注我 回复“资料”获取作者整理的大量学习资料! 一、背景 在我上一篇文章《Spring Cloud开发人员如何解决服务冲突和实例乱窜?》中提到使用服务的元数据来实现隔...

zlt2000
2019/09/06
0
0
Linux下diff命令用法详解

大家好,我是良许。 我们在平时工作的时候,经常要知道两个文件之间,以及同个文件不同版本之间有何异同点。在 Windows 下,有 beyond compare 这个好用的工具,而在 Linux 下,也有很多很强...

osc_th8jvcw7
53分钟前
7
0
万变不离其宗之UART要点总结

[导读] 单片机开发串口是应用最为广泛的通信接口,也是最为简单的通信接口之一,但是其中的一些要点你是否明了呢?来看看本人对串口的一些总结,当然这个总结并不能面面俱到,只是将个人认为...

osc_kyehmyzk
54分钟前
7
0
kafka的认识、安装与配置

认识Kafka 花费越少的精力在数据移动上,就能越专注于核心业务 --- 《Kafka:The Definitive Guide》 认识 Kafka 之前,先了解一下发布与订阅消息系统:消息的发送者不会直接把消息发送给接收...

osc_wy8nhxhn
56分钟前
0
0
使用pandas进行数据处理——DataFrame篇

  今天是pandas数据处理专题的第二篇文章,我们一起来聊聊pandas当中最重要的数据结构——DataFrame。   上一篇文章当中我们介绍了Series的用法,也提到了Series相当于一个一维的数组,只...

开源仔
56分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部