充分理清限制与条件+构造二分图+最小割：ARC142E

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133623334

https://www.luogu.com.cn/problem/AT_arc142_e

考虑 $$

他的充要条件是是什么：

  1. ai,aj≥min(bi,bj)a_i,a_j\ge min(b_i,b_j)

  2. 存在 ai≥max(bi,bj)a_i\ge max(b_i,b_j)

第一个条件直接预处理一下。

第二个条件，同时有非常多限制交叉，我们就非常想网络流建模来搞。（而且数据范围明细提示着我们）但是有个尴尬的问题，哪些点连源点，哪些连汇点。

然后就是此题最巧妙的地方了，可以构造二分图！

我们发现 (ai,bi)(a_i,b_i) 是成对的，这似乎提示着我们什么。考虑对其分类

对于一对限制 (i,j)(i,j) ，如果目前只满足条件1，不满足条件2 ， ai≥bia_i\ge b_i 和 aj≥bja_j\ge b_j 必然是一个成立，一个不成立。同时，这里 i,ji,j 独立，所以这就变成了一个二分图了！

最后是建模。我们这里发现是左边和右边至少满足一个，典型的最小割模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>

using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define M
//#define mo
#define N 100010


using namespace atcoder;

struct node {
	int u, v;  
};
int n, m, i, j, k, T;
int ans, a[N], b[N], u, v, S; 
vector<node>G; 

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}	
	mf_graph<int>F(200010); 
	n=read(); S=(n+5)*100+1; T=(n+5)*100+2; 
	for(i=1; i<=n; ++i) a[i]=read(), b[i]=read(); 
	m=read(); 
	for(i=1; i<=m; ++i) {
		u=read(); v=read(); 
		k=min(b[u], b[v]);  
		if(a[u]<k) ans+=k-a[u], a[u]=k; 
		if(a[v]<k) ans+=k-a[v], a[v]=k; 
		G.pb({u, v}); 
	}
//	printf("%lld\n", ans); 
	for(i=1; i<=n; ++i) {
//		printf("%lld %lld\n", a[i], b[i]); 
		if(a[i]>=b[i]) {
//			printf("> %lld\n", i); 
			for(j=a[i]+1; j<=100; ++j) 
				F.add_edge(S, i*100+j, 1); 
			for(j=1; j<100; ++j) 
				F.add_edge(i*100+j, i*100+j+1, 1e9); 
		}
		else {
			for(j=a[i]+1; j<=100; ++j) 
				F.add_edge(i*100+j, T, 1); 
			for(j=1; j<100; ++j) 
			F.add_edge(i*100+j+1, i*100+j, 1e9); 
		}
		
	}
	for(auto t : G) {
		u=t.u; v=t.v; 
		k=max(b[u], b[v]); 
		if(a[u]>=b[u] && a[v]>=b[v]) continue; 
		if(a[u]>=b[v] && a[v]>=b[u]) continue; 
//		if(k==13) continue; 
		if(a[u]>=b[u]) {
//					printf("%d -> %d\n", u*100+k, v*100+k); 

			F.add_edge(u*100+k, v*100+k, 1e9); 
		}
		else {
//					printf("%d -> %d\n", v*100+k, u*100+k); 

			F.add_edge(v*100+k, u*100+k, 1e9); 
		}
	}
	ans=ans+F.flow(S, T); 
	printf("%lld", ans); 
	return 0;
}