棋盘V
时间限制: 1 Sec 内存限制: 128 MB
提交: 380 解决: 44
[提交] [状态] [讨论版] [命题人:admin]
题目描述
有一块棋盘，棋盘的边长为100000，行和列的编号为1到100000。棋盘上有n个特殊格子，任意两个格子的位置都不相同。
现在小K要猜哪些格子是特殊格子。她知道所有格子的横坐标和纵坐标，但并不知道对应关系。换言之，她只有两个数组，一个存下了所有格子的横坐标，另一个存下了所有格子的纵坐标，而且两个数组都打乱了顺序。当然，小K猜的n个格子的位置也必须都不相同。
请求出一个最大的k，使得无论小K怎么猜，都能猜对至少k个格子的位置。
现在小K要猜哪些格子是特殊格子。她知道所有格子的横坐标和纵坐标，但并不知道对应关系。换言之，她只有两个数组，一个存下了所有格子的横坐标，另一个存下了所有格子的纵坐标，而且两个数组都打乱了顺序。当然，小K猜的n个格子的位置也必须都不相同。
请求出一个最大的k，使得无论小K怎么猜，都能猜对至少k个格子的位置。
输入
输入数据第一行包含一个整数n。
接下来n行，每行描述一个特殊格子的位置。第i行含有两个整数xi和yi ，代表第i个格子的坐标。保证任意两个格子的坐标都不相同。
接下来n行，每行描述一个特殊格子的位置。第i行含有两个整数xi和yi ，代表第i个格子的坐标。保证任意两个格子的坐标都不相同。
输出
输出一行，包含一个整数，代表最大的k。
样例输入
2
1 1
2 2
样例输出
0
提示
小K有可能会猜(1,2),(2,1)，此时一个都没对
对于30%的数据，n≤8。
另外有5%的数据，所有横坐标和纵坐标均不相同。
另外有15%的数据，所有横坐标或者纵坐标均不相同。
对于100%的数据，n≤50，1≤xi,yi≤100000。
思路：见其他博客！！！
注意：实际数据可能比所给的范围大一点！！！
如果暴力处理数据，要特意把数组开大一点应该才能过！！！
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+;
const int inf=;
vector<int> v[];
struct Edge
{
Edge() {};
Edge(int a,int b,int c,int d,int g,int f)
{
u=a,v=b,cost=c,cap=d,flow=g,next=f;
};
int u,v,cost,cap,flow,next;
} e[];
struct Mcmf
{
int head[maxn],cnt;
int dis[maxn],f[maxn],pre[maxn];
bool vis[maxn];
inline void init()
{
memset(head,-,sizeof(head));
cnt=;
}
inline void add(int u,int v,int cost,int cap,int flow=)
{
e[cnt]=Edge{u,v,cost,cap,flow,head[u]};
head[u]=cnt++;
e[cnt]=Edge{v,u,-cost,,flow,head[v]};
head[v]=cnt++;
}
bool spfa(int s,int t,int &cost,int &flow)
{
memset(vis,false,sizeof(vis));
for (int i=; i<maxn; i++)
dis[i]=inf;
queue<int>q;
while(!q.empty()) q.pop();
f[s]=inf;
dis[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;
for (int i=head[u]; i!=-; i=e[i].next)
{
int v=e[i].v;
if(e[i].cap>e[i].flow && dis[v]>dis[u]+e[i].cost)
{
dis[v]=dis[u]+e[i].cost;
f[v]=min(f[u],e[i].cap-e[i].flow);
pre[v]=i;
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
}
if(dis[t]==inf)
return ;
cost+=dis[t]*f[t];
flow+=f[t];
for(int u=t; u!=s; u=e[pre[u]].u)
{
e[pre[u]].flow+=f[t];
e[pre[u]^].flow-=f[t];
}
return ;
}
int minCost(int s,int t)
{
int cost=,flow=;
while(spfa(s,t,cost,flow)) ;
return cost;
}
} p;
int main()
{
int s=3e5+,t=3e5+,n,res,sum;
int x[],y[];
p.init();
//for(int i=0;i<=100004;i++) v[i].clear();
scanf("%d",&n);
for(int i=; i<=n-; i++)
{
scanf("%d %d",&x[i],&y[i]);
v[x[i]].push_back(y[i]);
p.add(x[i],y[i]+,,);
}
sort(x,x+n);
sort(y,y+n);
res=x[];
for(int j=; j<=n-; j++)
{
int flag=;
for(int k=; k<v[res].size(); k++)
{
if(v[res][k]==y[j])
{
flag=;
break;
}
}
if(flag)
continue;
if(j==)
p.add(res,y[j]+,,);
if(j> && y[j]!=y[j-])
p.add(res,y[j]+,,);
}
for(int i=; i<=n-; i++)
{
if(x[i]==x[i-])
continue;
else
res=x[i];
for(int j=; j<=n-; j++)
{
int flag=;
for(int k=; k<v[res].size(); k++)
{
if(v[res][k]==y[j])
{
flag=;
break;
}
}
if(flag)
continue;
if(j==)
p.add(res,y[j]+,,);
if(j> && y[j]!=y[j-])
p.add(res,y[j]+,,);
}
}
sum=;
for(int i=; i<=n-; i++)
{
if(x[i]!=x[i-])
{
p.add(s,x[i-],,sum);
sum=;
}
else
sum++;
}
p.add(s,x[n-],,sum);
sum=;
for(int i=; i<=n-; i++)
{
if(y[i]!=y[i-])
{
p.add(y[i-]+,t,,sum);
sum=;
}
else
sum++;
}
p.add(y[n-]+,t,,sum);
printf("%d\n",p.minCost(s,t));
return ;
}
/*
4
1 3
2 3
2 4
2 5 4
*/