\(n^{2}\)过百万，暴力出奇迹！

一道比较暴力的题目，蒟蒻也只会暴力的做法。

思路

可以一眼看出是一个二分图，所以考虑网络流做法。

首先考虑暴力网络流。

源点向每一位选手连流量为一的边。

每一位评委向汇点连流量为 \(b_{i}\) 的边。

对于每一次操作都直接连边，暴力跑网络流，来解决两个问题。

我们发现复杂度太过巨大，可以进行一波优化。

如何优化

首先考虑第一个问题。

根据题意，我们发现，在最优情况下，每个选手“反悔”的老师只有同样志愿等级的老师。

我们很快就能想到动态连边和动态删边。

我们对每一个志愿等级的老师进行连边，如果还有余流，则记录答案；如果没有，则删掉这些边，继续遍历下一个志愿等级的老师。

至于之前选手跑过的残量网络不需删除，直接跑就行了，因为需要有反悔的余地。

当然，如果这位选手一个答案都没找到，那么连源点向他连得边都可以删掉。

接着再考虑第二个问题。

一个很容易看出的就是首先进行二分。

对于二分，我们考虑一个比较暴力的思路，记录下之前，最优解的每一个时间（每一个选手加入的时候）的残量网络，接着暴力加边，跑一遍网络流，检测有没有余流。

可以推算一下这个暴力做法的复杂度。

每一次二分为：\(O(\log n)\)

网络流跑二分图为：\(O(n \sqrt{m})\)

所以第二个问题复杂度为：\(O(n^{2} \sqrt{m}\log n)\)

发现复杂度好像是一个正确的。

只能说是暴力出奇迹吗。

Code

看着人均 \(2kb\) 的代码，\(4kb\) 的我陷入了沉思。

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e7;

int t , c , n , m , sl , tl , cnt = 1;

int head[500] , b[500] , s[500] , cnt2[500];

int dep[500] , ans[500] , cop[500][500];

pair<int , int> a[500][500];

struct edge
{
	int to , nxt , v;
}e[10000] , ce[300][10000];

inline int read()
{
	int asd = 0 , qwe = 1; char zxc;
	while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
	while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
	return asd * qwe;
}

inline void add(int x , int y , int z)
{
	e[++cnt] = (edge){y , head[x] , z} , head[x] = cnt;
	e[++cnt] = (edge){x , head[y] , 0} , head[y] = cnt;
}

inline bool bfs()
{
	memset(dep , 0 , sizeof(dep));
	queue<int> q; 
	
	dep[sl] = 1 , q.push(sl);
	
	while(q.empty() == 0)
	{
		int x = q.front(); q.pop();
		for(int i = head[x];i;i = e[i].nxt)
		{
			int y = e[i].to;
			if(dep[y] == 0 && e[i].v > 0) dep[y] = dep[x] + 1 , q.push(y);
		}
	}
	
	return dep[tl];
}

inline int dfs(int now , int flow , int &mflow)
{
	if(now == tl)
	{
		mflow += flow;
		return flow;
	}
	
	int used = 0;
	
	for(int i = head[now];i;i = e[i].nxt)
	{
		int x = e[i].to;
		if(e[i].v && dep[x] == dep[now] + 1)
		{
			int y = dfs(x , min(e[i].v , flow - used) , mflow);
			used += y , e[i].v -= y , e[i ^ 1].v += y;
			if(used == flow) return used;
		}
	}
	
	return used;
}

inline int Dinic()
{
	int sum = 0;
	while(bfs()) while(dfs(sl , inf , sum));
	return sum;
}

inline void solve1()
{
	cnt2[0] = cnt;
	memset(ce[0] , 0 , sizeof(ce[0]));
	memset(cop[0] , 0 , sizeof(cop[0]));
	
	for(int i = 1;i <= cnt;i++) ce[0][i] = e[i];
	for(int i = 1;i <= n + m + 2;i++) cop[0][i] = head[i];
	
	for(int i = 1;i <= n;i++) 
	{ 
		ans[i] = m + 1;
		int last = a[i][1].first;
		add(sl , i , 1);
		for(int j = 1;j <= m && a[i][j].first != inf;j++) 
		{ 
			if(a[i][j].first == last) 
				add(i , a[i][j].second + n , 1);
			else 
			{ 
				int sum = Dinic();
				if(sum == 1) 
				{ 
					ans[i] = last;
					break;
				} 
				else
				{ 
					cnt = cnt2[i - 1];
					memcpy(e , ce[i - 1] , sizeof(ce[i - 1]));
					memcpy(head , cop[i - 1] , sizeof(cop[i - 1]));
					add(sl , i , 1) , add(i , a[i][j].second + n , 1) , last = a[i][j].first;
				} 
					
			} 
		} 
		
		if(ans[i] == m + 1)
		{ 
			int sum = Dinic();
			if(sum == 1) ans[i] = last;
			else
			{ 
				cnt = cnt2[i - 1];
				memcpy(e , ce[i - 1] , sizeof(ce[i - 1]));
				memcpy(head , cop[i - 1] , sizeof(cop[i - 1]));
			} 
		} 
		
		memset(ce[i] , 0 , sizeof(ce[i]));
		memset(cop[i] , 0 , sizeof(cop[i]));
		
		cnt2[i] = cnt;
		for(int j = 1;j <= cnt;j++) ce[i][j] = e[j];
		for(int j = 1;j <= n + m + 2;j++) cop[i][j] = head[j];
		
		printf("%d " , ans[i]);
	}
	puts("");
}

inline void calc(int x , int y)
{
	cnt = cnt2[x - 1];
	memcpy(e , ce[x - 1] , sizeof(ce[x - 1]));
	memcpy(head , cop[x - 1] , sizeof(cop[x - 1]));
	add(sl , y , 1);
	for(int i = 1;i <= m && a[y][i].first <= s[y];i++) add(y , a[y][i].second + n , 1);
}

inline void solve2()
{
	for(int i = 1;i <= n;i++)
	{
		if(ans[i] <= s[i]) 
		{
			printf("0 ");
			continue;
		}
		
		
		int l = 1 , r = i - 1 , sum = 0;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			calc(mid , i);
			int num = Dinic();
			if(num == 1) l = mid + 1 , sum = mid;
			else r = mid - 1;
		}
		
		printf("%d " , i - sum);
	}
	puts("");
}

int main()
{
	t = read() , c = read();
	
	while(t--)
	{
		n = read() , m = read() , sl = n + m + 1 , tl = n + m + 2 , cnt = 1;
		
		for(int i = 1;i <= m;i++) b[i] = read();
		
		for(int i = 1;i <= n;i++)
		{
			for(int j = 1;j <= m;j++)
			{
				a[i][j].first = read() , a[i][j].second = j;
				if(a[i][j].first == 0) a[i][j].first = inf;
			}
			sort(a[i] + 1 , a[i] + m + 1);
		}
		
		for(int i = 1;i <= n;i++) s[i] = read();
		
		for(int i = 1;i <= m;i++) add(i + n , tl , b[i]);
		
		solve1() , solve2();
		
		
		memset(e , 0 , sizeof(e));
		memset(s , 0 , sizeof(s));
		memset(b , 0 , sizeof(b));
		memset(cnt2 , 0 , sizeof(cnt2));
		memset(head , 0 , sizeof(head));
		
	}
	
	return 0;
}