hdu 3081 Marriage Match II

怼烎@ 2021-10-15 11:55 194阅读 0赞

Sample Input

4 5 2

1 1

2 3

3 2

4 2

4 4

1 4

2 3

结合输入数据讲题意，1，就是一组输入数据，4表示有2 \*  4个人，女生编号为1-4, 男生编号也为1-4,

5表示下面接下来5对关系是没有吵过架的，2表示为有2对女生女生是好朋友的关系，也就是最后输入的那两行

题目是要我们求每个女生找一个男生，并且这个男生没有和她吵过架，如果她朋友没有跟这个男生吵过架也可以。

还有就是女生之间的朋友关系可以传递。

但是不能找以前她已经找过的男生。。当每个女生找到一个男生后，这个游戏就算玩了一次，然后接着继续玩。

要我们解决的问题是，这个游戏最多可以玩几圈。

算法：

1.并查集

因为女生之间的朋友关系可以传递，所以要用并查集处理女生好朋友之间的关系。

只要他们属于同一个集合，有相同的祖先，就说明这两个女生可以和她们相应没有吵过架的男生组队。

2.构图。。

0为源点，2 \* N + 1为汇点

女生编号为1 - N， 男生编号为N + 1 - 2 \* N

女生跟其没有吵过架的男生构成的边的权值为1

0 - (1 - N)构边权值Mid..

(N + 1- 2 \* N) to 2 \* N + 1构边权值Mid

至于Mid取值，则二分搜索。。

Mid 的取值区间为\[0-N\]

为什么是N呢。。根据题目要求最多能玩N次游戏。

假设最后求得的网络流是 N \* mid;

那么mid 就是圈数。

3.二分搜索

mid 到底取多少我们可以二分搜索。。。

只要当我们由当前mid求得的网络流等于 N \* mid..

则l = mid + 1,同时保存下当前mid.

如果不等于N \* mid,

r = mid -1;

4.网络流算法很多。。

我用的是sap算法。

5.代码

我看数据量比较小直接用矩阵存储图的。挺暴力的，300多ms.

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <algorithm>
    using namespace std;
    int mp[210][210];
    int m[210][210];
    int set[410];
    int N, M, f, sum, ans;
    const int inf = 0x7f7f7f7f;
    bool Find;
    int vh[410];
    int h[410];
    
    int find( int x)
    {
          
    return x == set[x] ? x : set[x] = find( set[x] );    
    }
    
    void init_flow( )
    {
          
      memset(h, 0, sizeof(h));
      memset(vh, 0, sizeof(vh));     
    }
    
    void init( )
    {
          
    for( int i = 0; i < 110; i++)
    set[i] = i;
      memset(mp, 0, sizeof(mp));
      memset(m, 0, sizeof(m));     
    }
    
    //源点0，汇点N + 1 
    void make_graph(int mid)
    { 
    //源点到各女生
      memset(mp, 0, sizeof(mp)); 
    for( int i = 1; i <= N; i++)
      {
          
         mp[0][i] = mid;      
      }
    //各男生到汇点
      for( int i = N + 1; i <= 2 * N; i++)
      {
          
         mp[i][2 * N + 1] = mid;     
      }
    for( int i = 1; i <= 2 * N; i++)
    for( int j = 1; j <= 2 * N; j++)
            mp[i][j] = m[i][j];
    //朋友关系是可以传递的 
      for( int i = 1; i <= 2 * N; i++)
      {
          
    for( int j = 1; j <= 2 * N; j++)
          {
          
    if( set[i] == set[j])
            {
          
    for( int k = 1; k <= 2 * N; k++)
                {
          
    if ( mp[j][k] && k != i)
                     mp[i][k] = 1;     
                }   
            }   
          }    
      }
    
    }
    
    void dfs( int x )
    {
          
    int hmin = 2 * N + 1, i;
    if( x == 2 * N + 1)
       {
          
          sum += ans;
          Find = true;
    return;   
       }
    for( i = 0; i <= 2 * N + 1; i++)
       {
          
    if( mp[x][i] > 0)
          {
          
    if( h[x] == h[i] + 1 )
            {
          
    if( mp[x][i] < ans )
                  ans = mp[x][i];
              dfs( i );
    if( Find )
    break;
    if( h[0] >= 2 * N + 1 )
    return;    
            }
    if( h[i] < hmin )
                hmin = h[i];    
          }        
       }
    if( Find )
       {
          
         mp[x][i] -= ans;
         mp[i][x] += ans;    
       }
    else
       {
          
         vh[h[x]]--;
    if( vh[h[x]] == 0 )
             h[0] = 2 * N + 1;
         h[x] = hmin + 1;
         vh[h[x]]++;    
       }     
    }
    
    int sap( )
    {
          
       sum = 0;
       init_flow( );
       vh[0] = 2 * N + 2;
    while( h[0] < 2 * N + 2 )
       {
          
         ans = inf;
         Find = false;
         dfs( 0 );          
       }
    return sum;     
    }
    
    int solve( )
    {
          
    int l = 0, r = N, temp = 0;
    while( l <= r )
      {
          
    int mid = (l + r) / 2;
         make_graph(mid);
    if( sap( ) == mid * N )
         {
          
             temp = mid;
             l = mid + 1;    
         }
    else
             r = mid - 1;       
      }
    return temp;    
    }
    
    int main( )
    {
          
    int T, a, b;
      cin>>T;   
    while( T-- )
      {
          
        cin>>N>>M>>f;
        init( );
    for( int i = 1; i <= M; i++)
        {
          
           cin>>a>>b;
           mp[a][b + N] = 1;
           m[a][b + N] = 1;
        }
    for( int i = 1; i <= f; i++)
        {
          
           cin>>a>>b;
    int x = find( a );
    int y = find( b );
    if( x != y )
    set[x] = y;
        }
    for( int i = 1; i <= N; i++)
        {
          
    set[i] = find( i );     
        }          
        printf("%d\n", solve( ));       
      }
    return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/03/19/2407111.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211015/7e742b17c8ab434281a620e7b8ccc0d0.png