棋盘V(最小费用最大流)

棋盘V

时间限制: 1 Sec 内存限制: 128 MB
提交: 380 解决: 44
[提交] [状态] [讨论版] [命题人:admin]

题目描述

有一块棋盘，棋盘的边长为100000，行和列的编号为1到100000。棋盘上有n个特殊格子，任意两个格子的位置都不相同。
现在小K要猜哪些格子是特殊格子。她知道所有格子的横坐标和纵坐标，但并不知道对应关系。换言之，她只有两个数组，一个存下了所有格子的横坐标，另一个存下了所有格子的纵坐标，而且两个数组都打乱了顺序。当然，小K猜的n个格子的位置也必须都不相同。
请求出一个最大的k，使得无论小K怎么猜，都能猜对至少k个格子的位置。

输入

输入数据第一行包含一个整数n。
接下来n行，每行描述一个特殊格子的位置。第i行含有两个整数xi和yi ，代表第i个格子的坐标。保证任意两个格子的坐标都不相同。

输出

输出一行，包含一个整数，代表最大的k。

样例输入

2
1 1
2 2

样例输出

提示

小K有可能会猜(1,2),(2,1)，此时一个都没对
对于30%的数据，n≤8。
另外有5%的数据，所有横坐标和纵坐标均不相同。
另外有15%的数据，所有横坐标或者纵坐标均不相同。
对于100%的数据，n≤50，1≤xi,yi≤100000。

思路：见其他博客！！！

注意：实际数据可能比所给的范围大一点！！！

如果暴力处理数据，要特意把数组开大一点应该才能过！！！

AC代码：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=3e5+50;
  4 const int inf=63;
  5 vector<int> v[200005];
  6 struct Edge
  7 {
  8     Edge() {};
  9     Edge(int a,int b,int c,int d,int g,int f)
 10     {
 11         u=a,v=b,cost=c,cap=d,flow=g,next=f;
 12     };
 13     int u,v,cost,cap,flow,next;
 14 } e[8000];
 15 struct Mcmf
 16 {
 17     int head[maxn],cnt;
 18     int dis[maxn],f[maxn],pre[maxn];
 19     bool vis[maxn];
 20     inline void init()
 21     {
 22         memset(head,-1,sizeof(head));
 23         cnt=0;
 24     }
 25     inline void add(int u,int v,int cost,int cap,int flow=0)
 26     {
 27         e[cnt]=Edge{u,v,cost,cap,flow,head[u]};
 28         head[u]=cnt++;
 29         e[cnt]=Edge{v,u,-cost,0,flow,head[v]};
 30         head[v]=cnt++;
 31     }
 32     bool spfa(int s,int t,int &cost,int &flow)
 33     {
 34         memset(vis,false,sizeof(vis));
 35         for (int i=0; i<maxn; i++)
 36             dis[i]=inf;
 37         queue<int>q;
 38         while(!q.empty()) q.pop();
 39         f[s]=inf;
 40         dis[s]=0;
 41         q.push(s);
 42         while(!q.empty())
 43         {
 44             int u=q.front();
 45             q.pop();
 46             vis[u]=false;
 47             for (int i=head[u]; i!=-1; i=e[i].next)
 48             {
 49                 int v=e[i].v;
 50                 if(e[i].cap>e[i].flow && dis[v]>dis[u]+e[i].cost)
 51                 {
 52                     dis[v]=dis[u]+e[i].cost;
 53                     f[v]=min(f[u],e[i].cap-e[i].flow);
 54                     pre[v]=i;
 55                     if(!vis[v])
 56                     {
 57                         vis[v]=1;
 58                         q.push(v);
 59                     }
 60                 }
 61             }
 62         }
 63         if(dis[t]==inf)
 64             return 0;
 65         cost+=dis[t]*f[t];
 66         flow+=f[t];
 67         for(int u=t; u!=s; u=e[pre[u]].u)
 68         {
 69             e[pre[u]].flow+=f[t];
 70             e[pre[u]^1].flow-=f[t];
 71         }
 72         return 1;
 73     }
 74     int minCost(int s,int t)
 75     {
 76         int cost=0,flow=0;
 77         while(spfa(s,t,cost,flow)) ;
 78         return cost;
 79     }
 80 } p;
 81 int main()
 82 {
 83     int s=3e5+4,t=3e5+5,n,res,sum;
 84     int x[1005],y[1005];
 85     p.init();
 86     //for(int i=0;i<=100004;i++) v[i].clear();
 87     scanf("%d",&n);
 88     for(int i=0; i<=n-1; i++)
 89     {
 90         scanf("%d %d",&x[i],&y[i]);
 91         v[x[i]].push_back(y[i]);
 92         p.add(x[i],y[i]+100000,1,1);
 93     }
 94     sort(x,x+n);
 95     sort(y,y+n);
 96     res=x[0];
 97     for(int j=0; j<=n-1; j++)
 98     {
 99         int flag=0;
100         for(int k=0; k<v[res].size(); k++)
101         {
102             if(v[res][k]==y[j])
103             {
104                 flag=1;
105                 break;
106             }
107         }
108         if(flag)
109             continue;
110         if(j==0)
111             p.add(res,y[j]+100000,0,1);
112         if(j>0 && y[j]!=y[j-1])
113             p.add(res,y[j]+100000,0,1);
114     }
115     for(int i=1; i<=n-1; i++)
116     {
117         if(x[i]==x[i-1])
118             continue;
119         else
120             res=x[i];
121         for(int j=0; j<=n-1; j++)
122         {
123             int flag=0;
124             for(int k=0; k<v[res].size(); k++)
125             {
126                 if(v[res][k]==y[j])
127                 {
128                     flag=1;
129                     break;
130                 }
131             }
132             if(flag)
133                 continue;
134             if(j==0)
135                 p.add(res,y[j]+100000,0,1);
136             if(j>0 && y[j]!=y[j-1])
137                 p.add(res,y[j]+100000,0,1);
138         }
139     }
140     sum=1;
141     for(int i=1; i<=n-1; i++)
142     {
143         if(x[i]!=x[i-1])
144         {
145             p.add(s,x[i-1],0,sum);
146             sum=1;
147         }
148         else
149             sum++;
150     }
151     p.add(s,x[n-1],0,sum);
152     sum=1;
153     for(int i=1; i<=n-1; i++)
154     {
155         if(y[i]!=y[i-1])
156         {
157             p.add(y[i-1]+100000,t,0,sum);
158             sum=1;
159         }
160         else
161             sum++;
162     }
163     p.add(y[n-1]+100000,t,0,sum);
164     printf("%d
",p.minCost(s,t));
165     return 0;
166 }
167 /*
168 4
169 1 3
170 2 3
171 2 4
172 2 5
173 
174 4
175 */

View Code