【Foreign】猜测 [费用流]

猜测

Time Limit: 10 Sec Memory Limit: 256 MB

Description

Input

Output

Sample Input

　　3
　　1 1
　　1 2
　　2 1

Sample Output

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

HINT

Main idea

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

Solution

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

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

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

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 const int ONE = ;

 const int INF = ;

 int n,x,y;

 int S,T;

 int E[][];

 int next[ONE],first[ONE],go[ONE],pas[ONE],Fro[ONE],tot=;

 int from[ONE],q[],dist[];

 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=;    char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         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]=;     Fro[tot]=v;

 } 

 int Bfs()

 {

         memset(dist,,sizeof(dist));

         dist[S]=;  q[]=S; vis[S]=;

         tou=;  wei=;

         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]=;

                     }

                 }

             }

             vis[u]=;

         }

         return dist[T]!=dist[T+];

 }

 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^]+=x;

             Ans += w[e]*x;

         }

 }

 int main()

 {

         n=get();

         for(int i=;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+,li+li_num+);

         li_num = unique(li+,li+li_num+) - li - ;

         S=;    T=*li_num+;

         for(int i=;i<=n;i++)

         {

             a[i].x = lower_bound(li+,li+li_num+, a[i].x) - li;

             a[i].y = lower_bound(li+,li+li_num+, a[i].y) - li;

             E[ a[i].x ][ a[i].y ] = ;

             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=;i<=Max.x;i++) if(time[i].x) Add(S,i,time[i].x,);

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

         for(int i=;i<=Max.x;i++)

         if(time[i].x)

         for(int j=;j<=Max.y;j++)

         if(time[j].y)

         {

             if(E[i][j]) Add(i,j+Max.x,,);

             else Add(i,j+Max.x,,);

         }

         while(Bfs()) Deal();

         printf("%d",Ans);

 }

巴特西