基础知识

最小生成树

prim加点法

正确性

prim将最小生成树分为两个部分，因为关键在于点，一个部分为已知的最小生成树构造，另外一个部分为未知的生成树，而加上两个部分最小的连边，同样能使两棵树联通，必然选择最短的边最好。

代码实现：

int dis[1001][1001];
int prim(){
  int i,j,k,mst(0);
  bool check[1001],mini[1001];
  memset(mini,1,sizeof(mini)),mini[1]=0;
  for(i=1;i<=n;++i){
    for(k=0,j=1;j<=n;++j)
        if(mini[k]>mini[j]&&!check[j])k=j;
    check[k]|=true,mst+=mini[k];
    for(j=1;j<=n;++j)
      if(dis[k][j]<mini[j]&&!is[j])
        mini[j]=dis[k][j];
  }
  return mst;
}

kruscal排序

正确性

kruscal将边从小到大排序，即变成n颗树，而最小生成树必然是由这些树所构成的，而对于最小生成树包含的两棵生成树，将两者联通，必然是选择所有未选的边可以将其联通的最小的边。

代码实现

struct edge{
int p1,p2,len;
il bool operator<(edge&x){
    return len<x.len;
}
}e[1001];
struct union_find{
    int father[2001];
    il void clear(int n){
        for(int i(1);i<=n;++i)father[i]=i;
    }
    il int find(int x){
        if(father[x]==x)return x;
        return father[x]=find(father[x]);
    }
    il void link(int x,int y){
        father[find(x)]=find(y);
    }
}u;int n,m;
il int kruscal(){
    int i,mst(0);
    sort(e+1,e+m+1),u.clear(n);
    for(i=1;i<=m;++i)
        if(u.find(e[i].p1)!=u.find(e[i].p2))
            u.link(e[i].p1,e[i].p2),mst+=e[i].len;
    return mst;
}

联系

思想

1. 红蓝点
2. 数学归纳集合关系（不看单个点关系，看树与树之间关系）
3. 排序优化（最短最少一般可以排序）
4. 反证法给予证明

适用范围

spfa判负环

前身

bellmanford

思想

蔓延（不断地更新必然能最小），而负环使之无限更新。

代码

bfs

struct point{
    point*next;int to,len;
}*head[1001],*pt;
bool exist[1001];
int n,dis[1001],num[1001];
il bool check(){
    memset(dis,0,sizeof(dis)),memset(num,0,sizeof(num)),
        memset(exist,0,sizeof(exist));int i;
    for(i=1;i<=n;++i)if(spfa(i))return true;
    return false;
}
il bool spfa(int s){
    queue<int>team;int i;
    team.push(s),exist[s]|=true;
    while(!team.empty()){
        s=team.front(),team.pop(),exist[s]&=false;
        for(pt=head[s];pt!=NULL;pt=pt->next)
            if(dis[pt->to]>dis[s]+pt->len){
                dis[pt->to]=dis[s]+pt->len;
                if(!exist[pt->to]){
                    team.push(pt->to);
                    if(++num[pt->to]>n)return true;
                }
            }
    }return false;
}

dfs

struct point{
    point*next;int to,len;
}*head[1001],*pt;
bool exist[1001];
int n,dis[1001];
il bool check(){
    memset(dis,0,sizeof(dis)),memset(exist,0,sizeof(exist));
    for(int i(1);i<=n;++i)if(spfa(i))return true;
    return false;
}
il bool spfa(int x){
    exist[x]|=true;
    for(point *i(head[x]);i!=NULL;i=i->next)
        if(dis[i->to]>dis[x]+i->len){
            dis[i->to]=dis[x]+i->len;
            if(exist[i->to]||spfa(i->to))
                return true;
        }
    return exist[x]&=false;
}

01分数规划

问题

给定\(\{a_i\}\{b_i\}\),求\(\{x_i\}(x_i=0\ or\ 1)\)使\(\frac{\sum_{i=1}^na_ix_i}{\sum_{i=1}^nb_ix_i}\)最大，
感性的理解，即有n对a，b，从中选出x对，使a之和除以b之和最大。

解

最大问题即最优化问题，目前算法已经有

1. 递推
2. 贪心（常用排序）
3. 搜索
4. 二分
5. 迭代

而式子的问题常与二分扯上关系，于是我们来倒腾一下式子，设

\[s=\frac{\sum_{i=1}^na_ix_i}{\sum_{i=1}^nb_ix_i}\]

\[\sum_{i=1}^nsb_ix_i=\sum_{i=1}^na_ix_i\]

注意到相同的x，于是考虑合并

\[\sum_{i=1}^nx_i(a_i-b_is)=0\]

不妨将这个式子叫做分数规划的二分式，注意到sigma最左边为一常数，于是考虑预处理，接着考虑如何在这个式子中取到最大，显然是选择所有的整数，此时如果

\[\sum_{i=1}^nx_i(a_i-b_is)>0\]

\[\sum_{i=1}^nsb_ix_i<\sum_{i=1}^na_ix_i\]

\[s<\frac{\sum_{i=1}^na_ix_i}{\sum_{i=1}^nb_ix_i}\]

于是在我们所变出的式子中找到的最大值大于0的话，意思即存在更大的解可以满足条件，于是我们可以进行二分，这是一种方法。

但是注意到我们所选出来的式子也是一组比较大的解，于是可以让之作为端点，再以之为基础继续寻找最优解，无限接近答案，也就是迭代，这是另一种方法。

于是我们现在来考虑它们的区别

于是我们可以得出结论，如果答案好算，当然迭代会快一些，否则二分会更好，两者互补，共同组成了分数规划这一知识点，接下来所有题目也是围绕他们俩展开的。

套路总结

1. 二分式正负随意，注意变换使之顺应问题。

分数规划

原文：https://www.cnblogs.com/a1b3c7d9/p/10802542.html