猜测

Time Limit: 10 Sec Memory Limit: 256 MB

Description

img

Input

img

Output

img

Sample Input

3
  1 1
  1 2
  2 1

Sample Output

3
  explain:
  (1,1),(1,1),(2,2)不是一个合法猜测(有相同的格子),因此不管怎么猜总是能全部猜中。

HINT

img

Main idea

给定了若干个标准点,用这些点的横纵坐标分为x集和y集,定义猜点表示从x集和y集中各选一个,不能猜出重复的点,问在所有合法方案中最少包含上述几个标准点。

Solution

我们看到了这道题目,考虑从费用流的方法下手。

我们从S->x集:容量为数字出现次数,费用为0y集->T:容量为数字出现次数,费用为0x集->y集:容量为1,若组合成了标准点则费用为1,否则为0

然后我们这样连边,又由于题目要的是最少包含几个点,那么显然最小费用最大流就是答案了。

Code

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;

const int ONE = 2000001;
const int INF = 2147483640;

int n,x,y;
int S,T;
int E[1001][1001];
int next[ONE],first[ONE],go[ONE],pas[ONE],Fro[ONE],tot=1;
int from[ONE],q[1000001],dist[200001];
bool vis[ONE];
int tou,wei;
int Ans,w[ONE];
int li[ONE],li_num;

struct power
{
int x,y;
}a[ONE],time[ONE],Max;

int get()
{
int res,Q=1; char c;
while( (c=getchar())<48 || c>57)
if(c=='-')Q=-1;
if(Q) res=c-48;
while((c=getchar())>=48 && c<=57)
res=res*10+c-48;
return res*Q;
}

void Add(int u,int v,int liu,int z)
{
next[++tot]=first[u]; first[u]=tot; go[tot]=v; w[tot]=z; pas[tot]=liu; Fro[tot]=u;
next[++tot]=first[v]; first[v]=tot; go[tot]=u; w[tot]=-z; pas[tot]=0; Fro[tot]=v;
}

int Bfs()
{
memset(dist,63,sizeof(dist));
dist[S]=0; q[1]=S; vis[S]=1;
tou=0; wei=1;
while(tou<wei)
{
int u=q[++tou];
for(int e=first[u];e;e=next[e])
{
int v=go[e];
if(dist[v]>dist[u]+w[e] && pas[e])
{
dist[v]=dist[u]+w[e]; from[v]=e;
if(!vis[v])
{
q[++wei]=v;
vis[v]=1;
}
}
}
vis[u]=0;
}
return dist[T]!=dist[T+10];
}

void Deal()
{
int x=INF;
for(int e=from[T];e;e=from[Fro[e]]) x=min(x,pas[e]);
for(int e=from[T];e;e=from[Fro[e]])
{
pas[e]-=x;
pas[e^1]+=x;
Ans += w[e]*x;
}
}

int main()
{
n=get();
for(int i=1;i<=n;i++)
{
a[i].x=get(); a[i].y=get();
li[++li_num]=a[i].x; li[++li_num]=a[i].y;
}

sort(li+1,li+li_num+1);
li_num = unique(li+1,li+li_num+1) - li - 1;
S=0; T=2*li_num+1;

for(int i=1;i<=n;i++)
{
a[i].x = lower_bound(li+1,li+li_num+1, a[i].x) - li;
a[i].y = lower_bound(li+1,li+li_num+1, a[i].y) - li;
E[ a[i].x ][ a[i].y ] = 1;
time[a[i].x].x++; time[a[i].y].y++;
Max.x = max(Max.x, a[i].x); Max.y = max(Max.y, a[i].y);
}

for(int i=1;i<=Max.x;i++) if(time[i].x) Add(S,i,time[i].x,0);
for(int i=1;i<=Max.y;i++) if(time[i].y) Add(i+Max.x,T,time[i].y,0);

for(int i=1;i<=Max.x;i++)
if(time[i].x)
for(int j=1;j<=Max.y;j++)
if(time[j].y)
{
if(E[i][j]) Add(i,j+Max.x,1,1);
else Add(i,j+Max.x,1,0);
}

while(Bfs()) Deal();

printf("%d",Ans);

}