最小生成树/二分图

• 稠密图
• 步骤：
  • S：表示最小生成树的集合
  • 初始化距离
  • 找距离集合S最近的节点
  • 将节点加入集合S
  • 用该节点更新非S点到集合S点的距离
• 代码：

  const int N = 510;
  const int INF = 0x3f3f3f3f;
  int g[N][N];
  int d[N];//非生成树节点与生成树节点的最短距离
  int st[N];
  int n, m;
  
  int prim(){
      memset(d, 0x3f, sizeof d);//初始化
      
      int res = 0;//记录生成树权值和
      
      for(int i = 0; i < n; ++ i){//遍历n次选取n个点加入生成树
          
          int t = 0;
          for(int j = 1; j <= n; ++ j){
              if(!st[j] && (!t || d[j] < d[t]))//在非生成树集合中选取最小距离的点
                  t = j;
          }
          st[t] = 1;//加入生成树集合
          
          if(i && d[t] == INF) return INF;//某个点与生成树集合不联通，则不存在生成树
          if(i) res += d[t]; //累加最小权值
          
          for(int j = 1; j <= n; ++ j) //更新其他点到生成树的距离
              d[j] = min(d[j], g[t][j]);
      }
      
      return res;
      
  }
  int main(){
      cin >> n >> m;
      
      memset(g, 0x3f, sizeof g);
      
      while(m -- ){
          int u, v, w;
          cin >> u >> v >> w;
          g[u][v] = g[v][u] = min(g[u][v], w);//无向图去重边
      }
      
      int t = prim();
      if(t == INF) cout << "impossible";
      else cout << t;
      return 0;
  }
  

堆优化版Prim O(mlogn)

• 用堆优化找最短距离的过程将O(n)-->O(1)

• 将所有边的权值从小到大排序
• 枚举每条边u--v, w
• 若u，v不同时在生成树集合中，那么将这条边加入集合
• 利用并查集

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int f[N];
struct edge{
    int u, v, w;
    //运算符重载
    bool operator< (const edge &e)const{
        return w < e.w;
    }
}edges[N];

int n, m;

int find(int x){
    return x == f[x] ? x : (f[x] = find(f[x]));
}

int kruskal(){
    sort(edges + 1, edges + 1 + m);//权值排序
    
    for(int i = 1; i <= n; ++ i) f[i] = i;//并查集初始化
    
    int res = 0, cnt = 0;//res记录总权值，cnt记录边的条数
    for(int i = 1; i <= m; ++ i){//遍历每条边
        int u = edges[i].u;//获取信息
        int v = edges[i].v;
        int w = edges[i].w;
        u = find(u), v = find(v);//祖宗节点
        if(u != v){//不在同一集合中
            res += w;
            cnt ++ ;
            f[u] = v;//加入同一集合
        }
    }
    
    if(cnt < n - 1) return INF;//边数小于节点数-1，则不连通，不存在最小生成树
    else return res;
}
int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= m; ++ i){
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    
    int t = kruskal();
    if(t == INF) cout << "impossible";
    else cout << t;
    return 0;
}

const int N = 1e5 + 10;
const int M = 2 * N;
int h[N], e[M], ne[M], idx = 1;
int color[N];
int n, m;

void add(int u, int v){
    e[idx] = v;
    ne[idx] = h[u];
    h[u] = idx;
    idx ++ ;
}

//dfs染色，并且判断染色过程是否有矛盾
bool dfs(int u, int c){
    color[u] = c;//染色

    for(int i = h[u]; i; i = ne[i]){//遍历邻接点
        int j = e[i];
        if(!color[j]){//没有染色就染色
            if(!dfs(j, 3 - c)) return false;//染色出现矛盾
        }else if(color[j] == c) return false;//已经染色，判断相邻点是否同色
    }
    return true;
}

int main(){
    cin >> n >> m;
    while(m -- ){
        int u, v;
        cin >> u >> v;
        add(u, v);//无向图建边
        add(v, u);
    }
    
    bool flag = true;
    for(int i = 1; i <= n; ++ i){//以所有点为起点染色，因为可能不连通
        if(!color[i]){
            flag = dfs(i, 1);
            if(!flag) break;
        }
    }
    
    if(flag) cout << "Yes";
    else cout << "No";
    return 0;
}

const int N = 510;
const int M = 1e5 + 10;
int h[N], e[M], ne[M], idx = 1;
int match[N]; 
int st[N];
int n1, n2, m;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

bool find(int x){
    for(int i = h[x]; i; i = ne[i]){ //遍历该节点邻接的所有节点
        int j = e[i];
        if(!st[j]){
            st[j] = 1;//不管j有没有匹配过，强制标记为已经匹配，为了防止匹配j的节点再次将j匹配
            if(!match[j] || find(match[j])){ //j没有匹配或者匹配j的节点可以换一个匹配，在换匹配的过程中不会再匹配j，因为j已经被标记
                match[j] = x; //将x与j匹配
                return true; //成功匹配
            }
        }
    }
    return false;
}

int main(){
    cin >> n1 >> n2 >> m;
    
    while(m -- ){
        int a, b;
        cin >> a >> b;
        add(a, b); //只用一次
    }
    
    int res = 0;//记录最大匹配数
    for(int i = 1; i <= n1; ++ i){//匹配每一个节点
        memset(st, 0, sizeof st); 
        if(find(i)) res ++ ; //匹配成功
    }
    
    cout << res;
    return 0;
}