链式前向星

#include <iostream>
#include <string.h>
using namespace std;
const int MAX_N = 100;            //点
const int MAX_M = 10000;        //边
struct edge {
    int v,next;
    int len;
}E[MAX_M];
int p[MAX_N],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}
void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}
int main() {
    init();
    insert(1,2,10);
    insert(1,3,5);
    insert(2,3,1);
    insert(3,5,10);
    insert(3,4,6);
    insert(5,4,11);
    for(int u = 1;u <= 5;++u )
    {
        for(int i = p[u];i+1;i=E[i].next)
        {
            cout<<"("<<u<<", "<<E[i].v<<")"<<endl;
        }
    }
    return 0;
}

邻接矩阵的使用

问题描述

这一节我们来复习下前面刚学的邻接矩阵的使用。给出一个包含有向图和无向图的混合图 G，图上有 n 个点和 m 条边，现在你需要使用邻接矩阵来存储该混合图 G 并按格式输出邻接矩阵。
输入格式
输入第一行为两个正整数 n 和 m（1≤n,m≤100），表示混合图上的 n 个点和 m 条边。接下来输入 m 行，每行输入三个整数 a，x，y（0≤x,y< n），表示点 x 和点 y 之间有一条边。如果 a=0，则表示该边为有向边，如果 a=1，则表示该边为无向边。
输出格式
输出一个 n×n 的邻接矩阵，矩阵中第 i 行第 j 列的值描述了点 i 到点 j 的连边情况。如果值为 0 表示点 i 到点 j 没有边相连，值为 1 表示有边相连。在每一行中，每两个整数之间用一个空格隔开，最后一个整数后面没有空格。
样例输入
4 4
0 0 1
1 0 2
0 3 1
1 2 3
样例输出
0 1 1 0
0 0 0 0
1 0 0 1

0 1 1 0

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 105;
int G[105][105];
void init()
{
    memset(G,0,sizeof(G));
}
void insert1(int x,int y)
{
    G[x][y]=1;
}
void insert2(int x,int y)
{
    G[x][y]=G[y][x]=1;
}
int main()
{
    int n,m,a,x,y;
    while(cin>>n>>m)
    {
        init();
         for(int i=0;i<m;++i)
        {
            scanf("%d%d%d",&a,&x,&y);
            if(a==0)
            {
                insert1(x,y);
            }else if(a==1) 
            {
                insert2(x,y);
            }
        }
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(j==0)
            {
                cout<<G[i][j];
            }else 
            {
                cout<<" "<<G[i][j];
            }
        }
        cout<<endl;
    }
    return 0;
}

邻接表的使用

问题描述

这一节我们来复习下前面刚学的邻接矩阵的使用。给出一个包含有向图和无向图的混合图 G，图上有 n 个点和 m 条边，现在你需要使用邻接矩阵来存储该混合图 G 并按格式输出邻接矩阵。
输入格式
输入第一行为两个正整数 n 和 m（1≤n,m≤100），表示混合图上的 n 个点和 m 条边。接下来输入 m 行，每行输入三个整数 a，x，y（0≤x,y< n），表示点 x 和点 y 之间有一条边。如果 a=0，则表示该边为有向边，如果 a=1，则表示该边为无向边。
输出格式
输出一个 n×n 的邻接矩阵，矩阵中第 i 行第 j 列的值描述了点 i 到点 j 的连边情况。如果值为 0 表示点 i 到点 j 没有边相连，值为 1 表示有边相连。在每一行中，每两个整数之间用一个空格隔开，最后一个整数后面没有空格。
样例输入
4 4
0 0 1
1 0 2
0 3 1
1 2 3
样例输出
0 1 1 0
0 0 0 0
1 0 0 1

0 1 1 0

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 105;
const int maxm = 105;
struct esge{
    int v,len;
    int next;
}E[maxm];
int p[maxn],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid=0;
}
void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}
int main()
{
    int n,m;
    int a,x,y;
    while(cin>>n>>m)        //n个顶点m条边
    {
        init();
        for(int i=0;i<m;++i)    
        {
            scanf("%d%d%d",&a,&x,&y);
            if(a==0)
            {
                insert(x,y,1);
            }else 
            {
                insert(x,y,1);
                insert(y,x,1);
            }
        }
        for(int u=0;u<n;++u)
        {
            cout<<u<<":";
            for(int i=p[u];i+1;i=E[i].next)    //
            {
                cout<<" "<<E[i].v;
            }
            cout<<endl;
        }
    }
    return 0;
}

图的深度优先搜索

#include <iostream>
#include <string.h>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge{
    int v,next;
    int len;
}E[MAX_M];
int p[MAX_N],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid=0;
}
void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}
bool vst[MAX_N];
void dfs(int u)
{
    cout<<"visiting "<<u<<endl;
    vst[u] = true;
    for(int i=p[u];i+1;i=E[i].next)
    {
        if(!vst[E[i].v])
        {
            dfs(E[i].v);
        }
    }
}
int main() {
    init();
    insert(1,2,10);
    insert(1,3,5);
    insert(2,3,1);
    insert(3,5,10);
    insert(3,4,6);
    insert(5,4,11);
    memset(vst,false,sizeof(vst));
    dfs(1);
    return 0;
}

图的广度优先搜索

#include <iostream>
#include <string.h>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge{
    int v,next;
    int len;
}E[MAX_M];
int p[MAX_N],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}
void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}
bool vst[MAX_N];
void bfs(int v)
{
    memset(vst,false,sizeof(vst));
    queue<int> q;
    q.push(v);
    vst[v]=1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        cout<<"visiting "<<u<<endl;
        for(int i=p[u];i+1;i=E[i].next)
        {
            if(!vst[E[i].v])
            {
                vst[E[i].v]=1;
                q.push(E[i].v);
            }
        }
    }
}
int main() {
    init();
    insert(1,2,10);
    insert(1,3,5);
    insert(2,3,1);
    insert(3,5,10);
    insert(3,4,6);   
    insert(5,4,11);
    bfs(1);
    return 0;
}

树的存储与遍历

子树的节点个数

问题描述

有一个棵树，树上有 n 个结点。结点的编号分别为 1…n，其中 1 是树的根结点。现在希望你帮忙计算每个结点作为根结点的子树分别有多少结点。
输入格式
第一行输入一个数字 n，代表树上结点的个数。（2≤n≤1000）接下来的 n−1 行，每行俩个数字 a，b，代表结点 a 到结点 b 有一条边。
输出格式
按编号顺序输出每个结点作为根结点的子树，分别有多少结点，中间用空格分开。
样例输入
5
1 4
1 3
3 2
3 5
样例输出

5 1 3 1 1

#include <iostream>
#include <string.h>
using namespace std;
const int MAX_N = 1005;            //点
const int MAX_M = 1005;        //边
struct edge {
    int v,next;
    int len;
}E[MAX_M];
int p[MAX_N],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}
void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}
int cnt[MAX_N];  // 统计结果
bool vst[MAX_N];
void dfs(int u) {
    vst[u] = true;
    bool is_leaf = true;
    for (int i = p[u]; i != -1; i = E[i].next) {
        int v = E[i].v;
        if (!vst[v]) {
            dfs(v);
            is_leaf = false;
            cnt[u] += cnt[v];
        }
    }
    if (is_leaf) {
        cnt[u] = 1;
    }
}
int main() {
    init();
    int n;
    cin>>n;
    int a,b;
    for(int i=0;i<n-1;++i)
    {
        cin>>a>>b;
        insert(a,b,1);
    }
    //memset(cnt,1,sizeof(cnt));
    for(int i=0;i<MAX_N;++i)
    {
        cnt[i]=1;
    }
    dfs(1);
    for(int i=1;i<=n;++i)
    {
        if(i==1)
        {
            cout<<cnt[i];
        }else 
        {
            cout<<" "<<cnt[i];
        }
    }
    cout<<endl;
    return 0;
}

二叉树的遍历

先序遍历

int lch[MAX_N], rch[MAX_N];
void preorder(int u) {
    cout << "visiting " << u << endl;
    if (lch[u]) {
        preorder(lch[u]);
    }
    if (rch[u]) {
        preorder(rch[u]);
    }
}

中序遍历

int lch[MAX_N], rch[MAX_N];
void preorder(int u) {
    if (lch[u]) {
        preorder(lch[u]);
    }
    cout << "visiting " << u << endl;
    if (rch[u]) {
        preorder(rch[u]);
    }
}

后序遍历

int lch[MAX_N], rch[MAX_N];
void preorder(int u) {
    if (lch[u]) {
        preorder(lch[u]);
    }
    if (rch[u]) {
        preorder(rch[u]);
    }
    cout << "visiting " << u << endl;
}

图的基础算法

最小生成树

最小生成树的应用

1.最大边权最小的生成树

​ 直接求最小生成树，因为最小生成树的最大边一定是所有生成树里最大边权最小的

2.次小生成树

​ 枚举最小生成树上的 n条边,对于其中某条边,从图中删除它以后计算剩余图的最小生成树，一共n-1棵，从这n-1棵生成树中找出最小的一棵，就是整个图的次小生成树。

3.边权极差最小生成树

​ 给定一个无向连通图，求出它的所有的生成树中，最大边权和最小边权只差最小的生成树。

​ 枚举所有的生成树。

kruskal最小生成树算法

思路

将所有的边按从小到大排序，一次考虑每条边，如果将这个边加入最小生成树内不构成环，则加入，反之则不能加入。

演示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hQLaOSab-1569586399928)(C:Users红豆AppDataRoamingTyporatypora-user-images1557485052272.png)]

对于这棵树的最小生成树每次加入边的顺序为：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gwnMQxFC-1569586399936)(C:Users红豆AppDataRoamingTyporatypora-user-images1557485172691.png)]

四道模板题：

第一道：布设光纤

描述：

蒜国有 n 座基站，现在蒜头君想给基站之间布设光纤，使得任意两座基站都是连通的，光纤传输具有传递性，即如果基站 A 和基站 B 之间有光纤，基站 B 和基站 C 之间有光纤，则基站 A 和基站 C 也是连通的，可以通过中间基站 B 来完成传输。
不同的基站之间布设光纤的费用是不同的，现在蒜头君知道了任意两座基站之间布设光纤的费用，求问如何布设，可以使得任意两座基站都是连通的，且总费用最小。
输入格式
第一行输入一个整数 n(2≤n≤100)，表示蒜头基站总数。
接下来输入 n×n 的矩阵。第 i 行第 j 列的整数表示第 i 座基站和第 j 座基站之间布设光纤的费用 wij（0≤wij ≤10,000）。
输出格式
输出一个整数，表示布设光纤的最小总费用，且使任意两座基站都是连通的。
样例输入
4
0 1 5 1
1 0 6 3
5 6 0 2
1 3 2 0
样例输出

4

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
int map[105][105];
int fa[maxn];
struct node{
    int from;
    int to;
    int len;
}arr[maxn];
bool cmp(node a,node b)
{
    return a.len<b.len;
}
void init()
{
    for(int i=1;i<maxn;++i)
    {
        fa[i]=i;
    }
}
int find(int x)
{
    if(x!=fa[x])
    {
        fa[x]=find(fa[x]);
    }
    return fa[x];
}
void merge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        fa[p]=q;
    }
}
bool judge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        return true;
    }
    return false;
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                cin>>map[i][j];    
            }    
        }
        int stc=0;    
        for(int i=0;i<n;++i)
        {
            for(int j=i;j<n;++j)
            {
                arr[stc].from = i;
                arr[stc].to = j;
                arr[stc++].len = map[i][j];
            }
        }
        sort(arr,arr+stc,cmp);
        init();
        int cnt=0;
        int sum = 0;
        for(int i=0;i<stc;++i)
        {
            if(judge(arr[i].from,arr[i].to))
            {
                cnt++;
                merge(arr[i].from,arr[i].to);
                sum+=arr[i].len;
                if(cnt==n-1)
                {
                    break;
                }
            }    
        }
        cout<<sum<<endl;
    } 
    return 0;
}

第二道：连线问题

问题描述

蒜头君和花椰菜君经常出难题考对方。一天，花椰菜君给蒜头君出了这样一道难题：花椰菜君在坐标系上随机画了 N 个点，然后让蒜头君给点之间连线，要求任意两点之间都是连通的，且所连的线段长度之和最小。聪明的你快来帮蒜头君解决一下吧。
输入格式
第一行输入一个整数 N(1≤N≤100)，表示花椰菜君一共画了 N 个点。然后输入 N 行，每行输入两个整数 x,y（0≤x,y≤1,000），代表一个点的坐标。
输出格式
输出一行，输出一个实数，表示所连线段长度之和的最小值（结果四舍五入保留两位小数）。
样例输入
4
1 1
2 2
3 3
3 1
样例输出

4.24

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e6+5;
int fa[maxn];
int x[maxn];
int y[maxn];
void init()
{
    for(int i=1;i<maxn;++i)
    {
        fa[i]=i;
    }
}
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }    
    return fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        fa[p]=q;
    }
}
bool judge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        return true;
    }
    return false;
}
struct node
{
    int from;
    int to;
    double len;
}arr[10005];
bool cmp(node a,node b)
{
    return a.len<b.len;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>x[i]>>y[i];
    }
    int top=0;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(i!=j)
            {
                double dist = sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) );
                int from = x[i]*100+y[i];
                int to = x[j]*100+y[j];
                arr[top].from = from;
                arr[top].to = to;
                arr[top++].len = dist;    
            }
        }
    }
    sort(arr,arr+top,cmp);
    init();
    double sum = 0;
    int cnt = 0;
    for(int i=0;i<top;++i)
    {
        if(judge(arr[i].from,arr[i].to))
        {
            merge(arr[i].from,arr[i].to);
            cnt++;
            sum+=arr[i].len;
            if(cnt==n-1)
            {
                break;
            }
        }    
    }
    //cout<<sum<<endl;
    printf("%.2lf\n",sum);
    return 0;
}

第三道：穿越雷区

问题描述

蒜头君最近迷上了一款 RPG 游戏，这次他要去森林里的 n 个宝藏点收集宝藏，编号从 1 到 n。森林里有 m 条道路连接宝藏点，每条道路上都有数量不等的地雷，蒜头君想从中找出若干条道路，使得任意两个宝藏点都是连通的，这样蒜头君都能访问到每个宝藏点了。另外，由于遇到一个地雷，蒜头君会减少一定的血量。
现在蒜头君知道了这 m 条道路上的地雷数，蒜头君希望挑选若干条道路，使得挑选出的道路，地雷数量之和尽可能小。
输入格式
第一行输入两个整数 n,m（1≤n≤30,000，1≤m≤50,000），表示森林里有 n个宝藏点，m 条道路。两个宝藏点之间可能会有多条道路。
接下来输入 m 行，每行输入三个整数 x，y，z（1≤x,y≤n，0≤z≤1,000），表示 x 和 y 之间有 z 个地雷。
输出格式
输出一行，输出一个整数。表示蒜头君挑出了若干条道路，使得任意两个宝藏点都是连通的，输出道路的地雷数量之和最小值。
样例输入
3 4
1 2 121
1 3 202
2 1 497
2 3 135
样例输出

256

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 3e4+5;
int fa[maxn];
void init()
{
    for(int i=1;i<maxn;++i)
    {
        fa[i]=i;
    }
}
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }    
    return fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        fa[p]=q;
    }
}
bool judge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        return true;
    }
    return false;
}
struct node
{
    int from;
    int to;
    double len;
}arr[50005];
bool cmp(node a,node b)
{
    return a.len<b.len;
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int a,b,len;
        for(int i=0;i<m;++i)
        {
            cin>>arr[i].from>>arr[i].to>>arr[i].len;
        }
        sort(arr,arr+m,cmp);
        init();
        int sum = 0;
        int cnt=0;
        for(int i=0;i<m;++i)
        {
            if(judge(arr[i].from,arr[i].to))
            {
                merge(arr[i].from,arr[i].to);
                sum+=arr[i].len;
                cnt++;
                if(cnt==n-1)
                {
                    break;
                }    
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

第四道：高速公路

问题描述

蒜头君所在的国家有 n 个城市，现在需要在城市之间修高速公路，有 m 条修路的方案，每个方案表示 a, b 城市之间修一条限速为 c 的高速公路。蒜头君希望从这 m 个方案中选出若干方法试行，能够让 n 座城市联通，并且希望所有高速公路中最高限速和最低限速的差值最小。
输入格式
第一行输入两个整数 n,m（2≤n≤100，1<=m<=n(n-1)/2 ），表示有 n 个城市，m 条修路方案。两个城市之间可能会有多条修路方案。
接下来输入 m 行，每行输入三个整数 a，b，c（1≤a,b≤n，0≤c≤1,0000）。
输出格式
如果修路方案不能让 nn 个城市之间联通，输出 -1，否者输出最小的差值。
样例输入
4 4
1 2 2
2 3 4
1 4 1
3 4 2
样例输出

1

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 3e4+5;
int fa[maxn];
void init()
{
    for(int i=1;i<maxn;++i)
    {
        fa[i]=i;
    }
}
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }    
    return fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        fa[p]=q;
    }
}
bool judge(int x,int y)
{
    int p = find(x);
    int q = find(y);
    if(p!=q)
    {
        return true;
    }
    return false;
}
struct node
{
    int from;
    int to;
    int len;
}arr[10005];
bool cmp(node a,node b)
{
    return a.len<b.len;
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int a,b,len;
        for(int i=0;i<m;++i)
        {
            cin>>arr[i].from>>arr[i].to>>arr[i].len;
        }
        sort(arr,arr+m,cmp);
        int ans = 1<<30;
        for(int i=0;i<m;++i)
        {
            int min_val = 1<<30;
            int max_val = -1<<30;
            int cnt=0;
            init();
            for(int j=i;j<m;++j)
            {
                if(judge(arr[j].from,arr[j].to))
                {
                    merge(arr[j].from,arr[j].to);
                    min_val = min(min_val,arr[j].len);
                    max_val = max(max_val,arr[j].len);
                    cnt++;    
                }    
            }
            if(cnt!=n-1)
            {
                continue;
            }
            else 
            {
                ans = min(ans,(max_val-min_val));    
            }
        }
        if(ans ==  1<<30)
        {
            cout<<"-1"<<endl;
        }
        else 
        {
            cout<<ans<<endl;
        }
    }
    return 0;
}

Prim最小生成树算法

Prim算法对于使用邻接矩阵表示的图来说非常方便实现，所以在求稀疏图的最小生成树的时候常用Prim算法。

模板

#define INF 0x1f1f1f1f    //定义一个整数常量，表示无穷大
// prim函数返回得到的最小生成树的n-1条边的权值和
// 参数cost 为表示图的矩阵，n为顶点个数
int prim(int cost[][200],int n)
{
    //low表示每个点到生成树的最小距离，vis表示一个点是否已经加入生成树中
    int low[10000],vis[10000]=0;        //顶点数n<10000 
    int i,j,p;
    int min,res=0;                        //res表示最小生成树权值和 
    vis[0]=1;                            //将第一个顶点加入集合S 
    for(int i=1;i<n;++i)                //并更新该顶点到其他顶点的距离 
    {
        low[i] = cost[0][i];
    }
    for(int i=1;i<n;++i)                //尝试加入剩下的n-1条边 
    {
        min = INF;                        //寻找点集V-S中距离集合S最近的距离的点 
        p=-1;                            //min为权值，p为位置 
        for(int j=0;j<n;++j)
        {
            if(0==vis[j] && min>low[j])
            {
                min = low[j];
                p = j;
            }
        }    
        //min==INF 说明找不到能够加入的点了，说明图是不连通的（已经加入的点集和未加入的点集不连通）。
        if(min==INF) return -1;
        
        res+=min;
        vis[p]=1;        //P点加入生成树的点集 
        
        for(j=0;j<n;++j)    //加入该点后更新集合S到集合V-S之间的距离 
        {
            if(vis[j]==0 && low[j]>cost[p][j])
            {
                low[j] = cost[p][j];    
            }    
        } 
    }
    return res;    
} 

第一道：hdu

题目描述：

There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.

We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.

Input

The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.

Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

Output

You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.

#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x1f1f1f1f    //定义一个整数常量，表示无穷大
// prim函数返回得到的最小生成树的n-1条边的权值和
// 参数cost 为表示图的矩阵，n为顶点个数
int prim(int cost[][100],int n)
{
    //low表示每个点到生成树的最小距离，vis表示一个点是否已经加入生成树中
    int low[10000];
    int vis[10000]={0};        //顶点数n<10000 
    int i,j,p;
    int min,res=0;                        //res表示最小生成树权值和 
    vis[0]=1;                            //将第一个顶点加入集合S 
    for(int i=1;i<n;++i)                //并更新该顶点到其他顶点的距离 
    {
        low[i] = cost[0][i];
    }
    for(int i=1;i<n;++i)                //尝试加入剩下的n-1条边 
    {
        min = INF;                        //寻找点集V-S中距离集合S最近的距离的点 
        p=-1;                            //min为权值，p为位置 
        for(int j=0;j<n;++j)
        {
            if(0==vis[j] && min>low[j])
            {
                min = low[j];
                p = j;
            }
        }    
        //min==INF 说明找不到能够加入的点了，说明图是不连通的（已经加入的点集和未加入的点集不连通）。
        if(min==INF) return -1;
        
        res+=min;
        vis[p]=1;        //P点加入生成树的点集 
        
        for(j=0;j<n;++j)    //加入该点后更新集合S到集合V-S之间的距离 
        {
            if(vis[j]==0 && low[j]>cost[p][j])
            {
                low[j] = cost[p][j];    
            }    
        } 
    }
    return res;    
} 
int main()
{
    int a[100][100];
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                cin>>a[i][j];    
            }    
        }    
        int t,x,y;
        cin>>t;
        while(t--)
        {
            cin>>x>>y;
            a[x-1][y-1]=a[y-1][x-1]=0;
        }
        int ans = prim(a,n);
        cout<<ans<<endl;
    }
    return 0;    
}  

LCA 最近公共祖先

问题描述

树是一种很常见的数据结构。现在蒜头君面临一个问题，在一个有 n 个节点的树上，节点编号分别是1…n。蒜头想知道一些节点之间的最近公共祖先是那些节点。
输入格式
第一行输入一个整数 n（2≤n≤10,000），表示树上有 n 个节点。
接下来的 n−1 行，每行输入俩个整数 a，b（1≤a,b≤n）代表节点 a，b 之间有一条 a 到 b 边，a 是 b 的父亲。
接下来输入一个整数 q，代表蒜头君的 q 次提问。（1≤q≤1,000）
接下来的 q 行，每行输入俩个整数 c，d（1≤c,d≤n）代表询问 c，d 俩个节点的最近公共祖先。
输出格式
对于每次询问，输出公共祖先的节点编号，占一行。
样例输入
5
1 2
2 3
1 4
2 5
2
3 4
3 5
样例输出
1

2

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 100000;
const int MAX_M = 1000000;

struct edge{
    int v,next;
}E[MAX_M];
int p[MAX_N],eid;
int isleave[MAX_N];

void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}

void insert(int u,int v)
{
    E[eid].v = v;
    E[eid].next = p[u];
    p[u] = eid++;
}

int d[MAX_N],fa[MAX_N][20];
void dfs(int u)
{
    for(int i = p[u];i+1;i=E[i].next)
    {
        if(d[E[i].v]==-1)
        {
            d[E[i].v]=d[u]+1;
            fa[E[i].v][0]=u;
            dfs(E[i].v);
        }
    }
}
int lca(int x,int y)
{
    int i,j;
    if(d[x]<d[y])
    {
        swap(x,y);
    }
    for(i=0;(1<<i)<=d[x];++i);
    --i;
    for(j=i;j>=0;j--)
    {
        if(d[x]-(1<<j)>=d[y])
        {
            x = fa[x][j];
        }
    }
    if(x==y)
    {
        return x;
    }
    for(j=i;j>=0;--j)
    {
        if(fa[x][j]!=fa[y][j])
        {
            x=fa[x][j];
            y=fa[y][j];
        }
    }
    return fa[x][0];
}
int main() {
    int n;
    init();
    cin>>n;
    memset(isleave,0,sizeof(isleave));
    for(int i=0;i<n-1;++i)
    {
        int u,v;
        cin>>u>>v;
        insert(u,v);
        insert(v,u);
        isleave[v]=1;
    }                            
    memset(d,-1,sizeof(d));
    int root;                    //寻找根节点 
    for(int i=1;i<=n;i++) 
    {     
        if(isleave[i]==0)
        { 
            root=i; 
            break; 
        } 
    } 
    d[root]=1; 
    dfs(root);
    for(int level = 1;(1<<level)<=n;level++)
    {
        for(int i=1;i<=n;++i)
        {
            fa[i][level] = fa[fa[i][level-1]][level-1];
        }
    }   
    int q;
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    return 0;
}

拓扑排序

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge{
    int v,next;
    int len;
}E[MAX_M];
int p[MAX_N],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid  = 0;
}
void insert(int u,int v)
{
    E[eid].v=v;
    E[eid].next = p[u];
    p[u] = eid++;
}
int n,m;
int indegree[MAX_N];
void topo()
{
    queue<int> q;
    for(int i=1;i<=n;++i)
    {
        if(indegree[i]==0)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int now = q.front();
        cout<<now<<endl;
        q.pop();
        for(int i=p[now];i+1;i=E[i].next)
        {
            int v = E[i].v;
            indegree[v]--;
            if(indegree[v]==0)
            {
                q.push(v);
            }
        }
    }
}
int main() {
    init();
    memset(indegree,0,sizeof(indegree));
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int u,v;
        cin>>u>>v;
        insert(u,v);
        ++indegree[v];
    }
    topo();
    return 0;
}

欧拉回路

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Nm6gCUVq-1569586399938)(C:Users红豆AppDataRoamingTyporatypora-user-images1558084269359.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fY3YWgKd-1569586399940)(C:Users红豆AppDataRoamingTyporatypora-user-images1558084324968.png)]

无向图欧拉路径

const int MAX_N = 100;
int mat[MAX_N][MAX_N];
int match[MAX_N];  // 表示顶点剩余的度
int n;  // 顶点个数
void solve(int u) {
    if (match[u] > 0) {
        for (int i = 0; i < n; ++i) {
            if (mat[u][i]) {
                mat[u][i]--;
                mat[i][u]--;
                solve(i);
            }
        }
    }
    cout << "visiting " << u << endl;
}

有向图欧拉路径

const int MAX_N = 100;
const int MAX_M = 10000;
int mat[MAX_N][MAX_N];
int match[MAX_N];  // 表示顶点剩余的度
int n;  // 顶点个数
int stk[MAX_M], top = 0;  // 用数组 stk 来模拟一个栈
void solve(int u) {
    if (match[u] > 0) {
        for (int i = 0; i < n; ++i) {
            if (mat[u][i]) {
                mat[u][i]--;
                solve(i);
            }
        }
    }
    stk[top++] = u;  // 将顶点 u 插入栈中
}

判断是否存在欧拉回路，给你n个点，m条边。

样例输入：

10 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 3
3 1

样例输出：

1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1005;
const int maxm = 100005;
int g[maxn][maxn];
int degree[maxn];
int fa[maxn];
void init()
{
    for(int i=1;i<maxn;++i)
    {
        fa[i]=i;
    }
}
int find(int x)
{
    if(x==fa[x])
    {
        return fa[x];
    }
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    int q = find(x); 
    int p = find(y);
    if(p!=q)
    {
        fa[p]=q;    
    }  
}
int main()
{
    int n,m;
    int a,b;
    cin>>n>>m;
    memset(g,0,sizeof(g));
    memset(degree,0,sizeof(degree));
    init();
    for(int i=0;i<m;++i)
    {
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
        merge(a,b);
        degree[a]++;
        degree[b]++;
    }
    int cnt=0;
    int flag=0;
    for(int i=1;i<=n;++i)
    {
        if(degree[i]%2==1)
        {
            cnt++;
        }
    }
    for(int i=1;i<=n;++i)
    {
        if(i==fa[i])
        {
            flag++;
        }
    }
    if((cnt==2 || cnt==0) && flag==1)
    {
        cout<<"1"<<endl;
    }else 
    {
        cout<<"0"<<endl;
    }
    return 0;
}

Tarjan算法

在有向图G中，如果两点互相可达，则称这两个点强连通，如果G中任意两点互相可达，则称G是强连通图

定理： 1、一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

​ 2、非强连通有向图的极大强连通子图，称为强连通分量（SCC即Strongly Connected Componenet）。

#include <iostream>
#include <string.h>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge{
    int v,next;
    int len;
}E[MAX_M];
int p[MAX_N],eid;
int dfn[MAX_N],low[MAX_N];
int idx = 0;
int belong[MAX_N],scc = 0;
int s[MAX_N],top = 0;
bool in_stack[MAX_N];
void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}
void insert(int u,int v)
{
    E[eid].v = v;
    E[eid].next = p[u];
    p[u] = eid++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++idx;
    s[top++] = u;
    in_stack[u] = true;
    for(int i= p[u];i+1;i=E[i].next)
    {
        int v = E[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }else if(in_stack[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u])
    {
        ++scc;
        do{
            belong[s[--top]] = scc;
            in_stack[s[top]] = false;
        }while(s[top]!=u);
    }
}
int main() {
    int n,m;
    init();
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int u,v;
        cin>>u>>v;
        insert(u,v);
    }
    memset(dfn,0,sizeof(dfn));
    idx = 0;
    for(int i=1;i<=n;++i)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    for(int i=1;i<=scc;++i)
    {
        cout<<"block "<<i<<": ";
        for(int j=1;j<=n;++j)
        {
            if(belong[j]==i)
            {
                cout<<j<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}

最短路

dijkstra最短路

#include <iostream>
#include <string.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int G[110][110];
int dist[110];
bool vst[110];
int n,m;
void dijkstra(int s)
{
    memset(vst,false,sizeof(vst));
    memset(dist,0x3f,sizeof(dist));
    dist[s]=0;
    for(int i=0;i<n;++i)
    {
        int v,min_d = inf;
        for(int j=1;j<=n;++j)
        {
            if(!vst[j] && dist[j]<min_d)
            {
                min_d = dist[j];
                v = j;
            }
        }
        vst[v] = true;
        for(int j=1;j<=n;++j)
        {
            dist[j] = min(dist[j],dist[v]+G[v][j]);
        }
    }
}
int main() {
    cin>>n>>m;
    memset(G,0x3f,sizeof(G));
    for(int i=0;i<m;++i)
    {
        int u,v,len;
        cin>>u>>v>>len;
        G[u][v] = G[v][u] = len;
    }
    dijkstra(1);
    for(int i=1;i<=n;++i)
    {
        cout<<dist[i]<<" ";
    }
    return 0;
}

第一题：骑车比赛

问题描述

蒜头君准备去参加骑车比赛，比赛在 n 个城市间进行，编号从 1 到 n。选手们都从城市 1 出发，终点在城市 n。
已知城市间有 m 条道路，每条道路连接两个城市，注意道路是双向的。现在蒜头君知道了他经过每条道路需要花费的时间，他想请你帮他计算一下，他这次比赛最少需要花多少时间完成。
输入格式
第一行输入两个整数n,m（1≤n≤1,000,1≤m≤5,000），分别代表城市个数和道路总数。接下来输入 m 行，每行输入三个数字 a,b,c（1≤a,b≤n,1≤c≤200），分别代表道路的起点和道路的终点，以及蒜头君骑车通过这条道路需要花费的时间。保证输入的图是连通的。
输出格式
输出一行，输出一个整数，输出蒜头君完成比赛需要的最少时间。
样例输入
5 6
1 2 2
2 3 3
2 5 5
3 4 2
3 5 1
4 5 1
样例输出

6

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>//优先队列在这个库里
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;//定义一个小根堆（优先队列
int n,m,num,s;
int he[100010],d[100010],inq[100010];

//d数组表示点i和起点之间的距离，inq记录点i是否已确定，he是前向星存边~

void read(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
    x=f*x;
}//快读（有的时候可以神奇的卡入一些神奇的TLE嘿嘿嘿
struct node
{
    int nxt;
    int to;
    int dis;
}edg[200020];//前向星!
void add(int a,int b,int c)
{
    edg[++num].to=b;
    edg[num].dis=c;
    edg[num].nxt=he[a];
    he[a]=num;
}//存边！
void dst(int s)
{
    memset(d,0x3f3f3f3f,sizeof(d));//初始化
    memset(inq,0,sizeof(inq));
    q.push(make_pair(0,s));//起点入队（堆）了
    d[s]=0;//自己到自己，距离0
    while(!q.empty())//队（堆）不是空的，此时距离起点最小的 点在队首（堆顶）
    {
        int x=q.top().second;//x:找到了！就是这个点！
        q.pop();//出队（堆），去履行更新其他点的光荣义务
        if(inq[x])continue;//如果这是一个已经确定过的点 ，拜拜
        inq[x]=1;
        int t=he[x];
        while(t)//遍历一遍这个点连向的点，更新最短路
        {
            if(d[edg[t].to]>d[x]+edg[t].dis&&!inq[edg[t].to])
            {
                d[edg[t].to]=d[x]+edg[t].dis;
                q.push(make_pair(d[edg[t].to],edg[t].to));//被更新了，进去
            }
            t=edg[t].nxt;
        }
    }    
}//嗷~
int main()
{
    int xx,yy,ww;
    read(n);read(m);//read(s);
    for(int i=1;i<=m;i++)
    {
        read(xx);read(yy);read(ww);
        add(xx,yy,ww);//有向图
        add(yy,xx,ww);
    }
    dst(1);
    //for(int i=1;i<=n;i++)
    cout<<d[n];
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int G[1005][1005];
int dist[1005];
bool vst[1005];
int n,m;
int dijkstra(int s)
{
    //cout<<"start"<<endl;
    memset(dist,inf,sizeof(dist));
    memset(vst,false,sizeof(vst));
    dist[s]=0;
    for(int i=0;i<n;++i)
    {
        int v,min_d = inf;
        for(int j=1;j<=n;++j)
        {
            if(!vst[j] && dist[j]<min_d)
            {
                min_d = dist[j];
                v = j;
            }            
        }        
        vst[v] = true;
        //cout<<v<<endl;
        for(int j=1;j<=n;++j)
        {
            dist[j] = min(dist[j],dist[v]+G[v][j]);    
        } 
    }
    //cout<<"end"<<endl;
    return 0;
}
int main()
{
    int a,b,c;
    cin>>n>>m;
    memset(G,inf,sizeof(G));
    for(int i=0;i<m;++i)
    {
        cin>>a>>b>>c;
        G[a][b]=G[b][a]=c;
    }
    dijkstra(1);
    cout<<dist[n]<<endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>//优先队列在这个库里
using namespace std;
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
} e[MAX_M];
int p[MAX_N], eid, n,m;
void mapinit() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v, int w) {  // 插入带权有向边
    e[eid].v = v;
    e[eid].w = w;
    e[eid].next = p[u];
    p[u] = eid++;
}
void insert2(int u, int v, int w) {  // 插入带权双向边
    insert(u, v, w);
    insert(v, u, w);
}
int dist[MAX_N];  // 存储单源最短路的结果
bool vst[MAX_N];  // 标记每个顶点是否在集合 U 中
struct node {
    int u;
  int dist;
    node(int _u, int _dist) : u(_u), dist(_dist) {}
    bool operator < (const node &x) const {
        return dist > x.dist;
    }
}; // 记录点的结构体
bool dijkstra(int s) {
    // 初始化 dist、小根堆和集合 U
    memset(vst, 0, sizeof(vst));
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<node> min_heap;
    dist[s] = 0;
    min_heap.push(node(s, 0));
    while (!min_heap.empty())
    {
        // 获取堆顶元素，并将堆顶元素从堆中删除
        int v = min_heap.top().u;
        min_heap.pop();
        if (vst[v]) {
            continue;
        }
        vst[v] = true;
        // 进行和普通 dijkstra 算法类似的松弛操作
        for (int j = p[v]; j != -1; j = e[j].next) {
            int x = e[j].v;
            if (!vst[x] && dist[v] + e[j].w < dist[x]) {
                dist[x] = dist[v] + e[j].w;
                min_heap.push(node(x, dist[x]));
            }
        }
    }
    return true;
}
int main()
{
    int a,b,c;
    cin>>n>>m;
    mapinit();
    for(int i=0;i<m;++i)
    {
        cin>>a>>b>>c;
        insert2(a,b,c);
    }
    dijkstra(1);
    cout<<dist[n]<<endl;
    return 0;
}

spfa最短路

Dijkstra不能处理有负权的图，spfa可以处理任意不含负环的图的最短路，并能判断图中是否存在负环。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tVzfB2z2-1569586399943)(C:Users红豆AppDataRoamingTyporatypora-user-images1558091282113.png)]

bool inq[MAX_N];
int d[MAX_N];  // 如果到顶点 i 的距离是 0x3f3f3f3f，则说明不存在源点到 i 的最短路
void spfa(int s) {
    memset(inq, 0, sizeof(inq));
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    inq[s] = true;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (int i = p[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (d[u] + e[i].w < d[v]) {
                d[v] = d[u] + e[i].w;
                if (!inq[v]) {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UCmdCdtQ-1569586399944)(C:Users红豆AppDataRoamingTyporatypora-user-images1558091379147.png)]

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge{
    int v,next;
    int len;
}E[MAX_M];
int p[MAX_N],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}
void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++;
}
bool inq[MAX_N];
int d[MAX_N];
void spfa(int s)
{
    memset(inq,false,sizeof(inq));
    memset(d,0x3f,sizeof(d));
    d[s] =0;
    inq[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u]=false;
        for(int i=p[u];i+1;i=E[i].next)
        {
            int v = E[i].v;
            if(d[u]+E[i].len<d[v])
            {
               d[v]  = d[u]+E[i].len;
                if(!inq[v])
                {
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
}
int main() {
    int n,m;
    cin>>n>>m;
    init();
    for(int i=0;i<m;++i)
    {
        int u,v,len;
        cin>>u>>v>>len;
        insert(u,v,len);
        insert(v,u,len);
    }
    spfa(1);
    for(int i=1;i<=n;++i)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}

样例输入：
5 6 
1 2 3
2 3 2 
3 4 1
2 4 10
4 5 1
1 3 7
输出：
0 3 5 6 7

Floyd最短路

#include <iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
int G[110][110];
int n;
void floyd()
{
    for(int k=0;k<n;++k)
    {
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n;++j)
            {
                if(G[i][k]+G[k][j]<G[i][j])
                {
                    G[i][j] = G[i][k]+G[k][j];
                }
            }
        }
    }
}
int main() {
    cin>>n;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            cin>>G[i][j];
        }
    }
    floyd();
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            cout<<G[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

第一题：蒜场年会

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6Mt0Eagi-1569586399945)(C:Users红豆AppDataRoamingTyporatypora-user-images1558092210066.png)]

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 305;
const int inf = 0x3f3f3f3f;
int graph[maxn][maxn];
int arr[maxn];
int n,m;
void init()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i==j)
            {
                graph[i][j]=0;
            }else 
            {
                graph[i][j]=inf;
            }
        }
    }
}
void floyd()
{
    for(int k=1;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);    
            }
        }
    }
}
void print()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            cout<<graph[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main()
{
    cin>>n>>m;
    init();
    //cout<<"this"<<endl;
    while(m--)
    {
        int num;
        cin>>num;
        for(int i=1;i<=num;++i)
        {
            cin>>arr[i];
        }    
        for(int i=1;i<=num;++i)    
        {
            for(int j=i;j<=num;++j)
            {
                //if(i==j) continue;
                //graph[arr[i]][arr[j]]+=1;
                //graph[arr[j]][arr[i]]+=1;
                
                //                
                graph[arr[i]][arr[j]]=graph[arr[j]][arr[i]]=1;
                //cout<<"test "<<arr[i]<<" "<<arr[j]<<endl;
//                if(graph[arr[i]][arr[j]]==inf)
//                {
//                    graph[arr[i]][arr[j]]=graph[arr[j]][arr[i]]=1;
//                }else 
//                {
//                    graph[arr[i]][arr[j]]+=1;
//                    graph[arr[j]][arr[i]]+=1;                    
//                }
            }
        }
    }
    //print();
    floyd();
    //print();
    int cul;
    int ans = inf;
    for(int i=1;i<=n;++i)
    {
        cul = 0;
        for(int j=1;j<=n;++j)
        {
            cul+=graph[i][j];
        }
        ans = min(ans,cul);
    }
    double a = (double)ans/(n);
    cout<<(int)(a*100)<<endl;
    //cout<<(int)(ans/(n-1)*100)<<endl;
    return 0;
}

第二题：蒜头君的训练室

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gMMwdNAR-1569586399946)(C:Users红豆AppDataRoamingTyporatypora-user-images1558092255496.png)]

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 305;
const int inf = 0x3f3f3f3f;
int g[maxn][maxn];
int n,m,t;
void init()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i==j)
            {
                g[i][j]=0;
            }else 
            {
                g[i][j]=inf;
            }
        }
    }
}
void floyd()
{
    for(int k=1;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(i!=j && g[i][j]>max(g[i][k],g[k][j]))
                {
                    g[i][j]=max(g[i][k],g[k][j]);
                }    
            }    
        }        
    }
}
int main()
{
    cin>>n>>m>>t;
    int s,e,h;
    init();
    for(int i=0;i<m;++i)
    {
        cin>>s>>e>>h;
        g[s][e]=h;
    }    
    floyd();
    int a,b;
    for(int i=0;i<t;++i)
    {
        cin>>a>>b;
        if(g[a][b]==inf)
        {
            cout<<"-1"<<endl;
        }else 
        {
            cout<<g[a][b]<<endl;    
        }
    }
    return 0;
}

第三题：美好的邂逅

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6X2TaML9-1569586399949)(C:Users红豆AppDataRoamingTyporatypora-user-images1558092325160.png)]

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 105;
int g[maxn][maxn];
const int inf = 0x3f3f3f3f;
int n,m;
void init()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i==j)
            {
                g[i][j]=0;
            }
            else 
            {
                g[i][j]=inf;
            }
        }
    }
    return ;
}
void floyd()
{
    for(int k=1;k<=n;++k)
    {
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(i!=j)
                {
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
                }
            }
        }
    }
    return ; 
} 
void print()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }
    return ;
}
int main()
{
    int a,b;
    while(cin>>n>>m)
    {
        init();
        for(int i=0;i<m;++i)
        {
            cin>>a>>b;
            g[a][b]=g[b][a]=1;
        }
        //print();
        floyd();
        //print();
        int flag=1;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(i==j) continue;
                if(g[i][j]>7)
                {
                    flag=0;
                    break;
                }
            }
            if(flag==0)
            {
                break;
            }
        }
        if(flag==0)
        {
            cout<<"No"<<endl;
        }else 
        {
            cout<<"Yes"<<endl; 
        }
    }
    return 0;
}

二分图匹配

最小点覆盖集=最大匹配

#include <iostream>
#include <string.h>
using namespace std;
bool G[110][110];
bool vis[110];
int link[110];
int n;
bool match(int u)
{
    for(int i=1;i<=n;++i)
    {
        if(G[u][i] && !vis[i])
        {
            vis[i] = true;
            if(link[i]==-1 || match(link[i]))
            {
                link[i] = u;
                return true;
            }
        }
    }
    return false;
}
int hungury()
{
    int ans =0;
    memset(link,-1,sizeof(link));
    for(int i=1;i<=n;++i)
    {
        memset(vis,false,sizeof(vis));
        ans+=match(i);
    }
    return ans;
}
int main() {
    memset(G,false,sizeof(G));
    int m;
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        G[a][b]=1;
    }
    cout<<hungury()<<endl;
    return 0;
}

第一题：男女分组

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xKcJdoG2-1569586399950)(C:Users红豆AppDataRoamingTyporatypora-user-images1558092546302.png)]

#include <iostream>
#include <string.h>
using namespace std;
bool G[110][110];
bool vis[110];
int link[110];
int n,m,w;
bool match(int u)
{
    for(int i=m+1;i<=n;++i)
    {
        if(G[u][i] && !vis[i])
        {
            vis[i] = true;
            if(link[i]==-1 || match(link[i]))
            {
                link[i] = u;
                return true;
            }
        }
    }
    return false;
}
int hungury()
{
    int ans =0;
    memset(link,-1,sizeof(link));
    for(int i=1;i<=m;++i)
    {
        memset(vis,false,sizeof(vis));
        ans+=match(i);
    }  
    return ans;
}
int main() {
    memset(G,false,sizeof(G));
    cin>>m>>n;                //一共n个同学，m个女同学
    int a,b; 
    while(cin>>a>>b)
    {
        if(a==-1 && b==-1)
        {
            break;
        }
        G[a][b]=1;
        G[b][a]=1;
    }
    cout<<hungury()<<endl;
    for(int i=m+1;i<=n;++i)
    {
        if(link[i]!=-1)
        {
            cout<<link[i]<<" "<<i<<endl;
        }
    }      
    return 0;
}

最大流

#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge
{
    int v,c,next;
}e[MAX_M];
int p[MAX_N],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}
void insert(int u,int v,int c)
{
    e[eid].v=v;
    e[eid].next=p[u];
    e[eid].c=c;
    p[u] = eid++;
}
void addedge(int u,int v,int c)
{
    insert(u,v,c);
    insert(v,u,0);
}
int S,T;
int d[MAX_N];
bool bfs()
{
    memset(d,-1,sizeof(d));
    queue<int> q;
    q.push(S);
    d[S]=0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i=p[u];i!=-1;i=e[i].next)
        {
            int v = e[i].v;
            if(e[i].c>0 && d[v]==-1)
            {
                q.push(v);
                d[v] = d[u]+1;
            }
        }
    }
    return (d[T]!=-1);
}
int dfs(int u,int flow)
{
    if(u==T)
    {
        return flow;
    }
    int res = 0;
    for(int i=p[u];i!=-1;i=e[i].next)
    {
        int v = e[i].v;
        if(e[i].c>0 && d[u]+1==d[v])
        {
            int tmp = dfs(v,min(flow,e[i].c));
            flow -= tmp;
            e[i].c -= tmp;
            res += tmp;
            e[i^1].c+=tmp;
            if(flow==0)
            {
                break;
            }
        }
    }
    if(res==0)
    {
        d[u] = -1;
    }
    return res;
}
int dinic()
{
    int res = 0;
    while(bfs())
    {
        res += dfs(S,INF);
    }
    return res;
}
int main() {
    int n,m;
    init();
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int u,v,flow;
        cin>>u>>v>>flow;
        addedge(u,v,flow);
    }
    cin>>S>>T;
    cout<<dinic()<<endl;
    return 0;
}