最大公约数和问题.cpp

这是一个二分图完全匹配问题

#include<iostream>
#include<math.h>
using namespace std;
/*
定理：
设M是一个带权完全二分图
G的一个完备匹配，给每个顶点一个
可行顶标(第i个x顶点的可行标用lx[i]表示
，第j个y顶点的可行标用ly[j]表示)，如果对所有的边(i,j)
 in G,都有lx[i]+ly[j]>=w[i,j]成立(w[i,j]表示边的权)，
 且对所有的边(i,j) in M,都有lx[i]+ly[j]=w[i,j]成立，
 则M是图G的一个最佳匹配。*/
 
 
const int MAX = 102;
int map[MAX][MAX];
int match[MAX],n,lx[MAX],ly[MAX];
bool x[MAX],y[MAX];

int gcd(int a, int b)
{
    if(a < b)return gcd(b, a);
    if(b == 0)return a;
    return gcd(b, a%b);
}

 
bool dfs(int v)
{
  int i,t;
  x[v] = true;
  for(i = 0; i < n; i++)
  if(!y[i] && lx[v]+ly[i] == map[v][i]){
  y[i] = true;
  t = match[i];
  match[i] = v;
  if(t == -1 || dfs(t))
  return true;
  match[i] = t;
}
return false;
}

int main()
{
 int i, j, test;
 int num[102];
  
  cin >> test;
 while(test--)
{
  cin >> n;   
  for(i = 0; i < n; i++)
  cin >> num[i];
  
  for(i = 0; i < n; i++)
  for(j = 0; j < n; j++)
  map[i][j] = -gcd(i+1, num[j]);         
           
 //初始化可行顶标 
 for(i = 0; i < n; i++)
 {
  lx[i] = -0x1FFFFFFF;
  ly[i] = 0;
  for(j = 0; j < n; j++)
  {
  if(lx[i] < map[i][j])
  lx[i] = map[i][j];
  }
 }
  memset(match,-1,sizeof(match));
 
 for(int k = 0; k < n; k++)
 { 
  while(1)
  {
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    if(dfs(k))//找到退出 
    break;
    int dx = 0x7FFFFFFF;
    for(i = 0; i < n; i++)
    {
     if(x[i])
     for(j = 0; j < n; j++)
     if(!y[j] && dx > (lx[i]+ly[j]-map[i][j]))
     dx = lx[i]+ly[j]-map[i][j];
    }
  //修改可行顶标 
     for(i = 0; i < n; i++)
    {
    if(x[i])
    lx[i] -= dx;
    if(y[i])
    ly[i] += dx;
    }
  }
  
  
 }
  int sum = 0;
  for(i = 0; i < n; i++)
  {
        sum += map[match[i]][i];
  }
  cout << -sum << endl;
}
 return 0;
}