1、Floyd算法:数据较小情况，算出每两点的最短距离

    1. for(int k=1;k<=n;k++)
    2. {
    3.     for(int i=1;i<=n;i++)
    4.     {
    5.         for(int j=1;j<=n;j++)
    6.         {
    7.             mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));
    8.             //求从一点到另一点所有路的最大值
    9.         }
    10.     }
    11. }

    2、Spfa算法：可计算一点到其他所有点最短距离，可以算负环

    1. //二维数组保存数据
    2. Memset(dis,inf,sizeof(dis));
    3. void spfa(int a)
    4. {
    5.     queue<int>q;
    6.     memset(vis,0,sizeof(vis));
    7.     q.push(a);
    8.     dis[a]=0;
    9.     vis[a]=1;
    10.     while(!q.empty())
    11.     {
    12.         int p=q.front();
    13.         q.pop();
    14.         vis[p]=0;
    15.         for(int i=1; i<=n; i++)
    16.         {
    17.             if(mp[p][i]!=inf)
    18.             {
    19.                 if(dis[i]>mp[p][i]+dis[p])
    20.                 {
    21.                     dis[i]=mp[p][i]+dis[p];
    22.                     if(vis[i]==0)
    23.                     {
    24.                         q.push(i);
    25.                         vis[i]=1;
    26.                     }
    27.                 }
    28.             }
    29.         }
    30.     }
    31.     cout<<dis[n]<<endl;
    32. }
    34. //前向星保存数据
    35. void add(int u,int v,int w)
    36. {
    37.     e[cnt].to=v;
    38.     e[cnt].w=w;
    39.     e[cnt].next=head[u];
    40.     head[u]=cnt++;
    41. }
    42. long long spfa()
    43. {
    44.     memset(dis,dis+n,inf);
    45.     memset(vis,0,sizeof(vis));
    46.     queue<int>q;
    47.     q.push(1);
    48.     dis[1]=0;
    49.     vis[1]=0;
    50.     while(!q.empty())
    51.     {
    52.         int u=q.front();
    53.         q.pop();
    54.         vis[u]=0;
    55.         for(int i=head[u];i!=-1;i++)
    56.         {
    57.             if(dis[e[i].to]>dis[u]+e[i].w)
    58.             {
    59.                 dis[e[i].to]=dis[u]+e[i].w;
    60.                 if(!vis[e[i].to])
    61.                 {
    62.                     q.push(e[i].to);
    63.                     vis[e[i].to]=1;
    64.                 }
    65.             }
    66.         }
    67.     }
    68. }

    3、输出字典序最小的最短路（floyd用dis[ i ][ j ]数组保留路径，dis[ i ][ j ]=h表示从 i 到 j 是 i 先到 h 再到 j 的）

    1. const int maxl=1010;
    2. const int inf=0x3f3f3f3f;
    3. int mp[maxl][maxl];
    4. int dis[maxl][maxl];
    5. int p[maxl];
    6. int main()
    7. {
    8.     int n;
    9.     while(scanf("%d",&n)&&n)
    10.     {
    11.         memset(dis,0,sizeof(dis));
    12.         for(int i=1; i<=n; i++)
    13.         {
    14.             for(int j=1; j<=n; j++)
    15.             {
    16.                 dis[i][j]=j;
    17.                 scanf("%d",&mp[i][j]);
    18.                 if(mp[i][j]==-1)
    19.                     mp[i][j]=inf;
    20.             }
    21.         }
    22.         for(int i=1; i<=n; i++)
    23.             scanf("%d",&p[i]);
    24.         for(int k=1; k<=n; k++)
    25.         {
    26.             for(int i=1; i<=n; i++)
    27.             {
    28.                 for(int j=1; j<=n; j++)
    29.                 {
    30.                     if(mp[i][j]>mp[i][k]+p[k]+mp[k][j])
    31.                     {
    32.                         mp[i][j]=mp[i][k]+p[k]+mp[k][j];
    33.                         dis[i][j]=dis[i][k];//i到j中间点就是k
    34.                     }
    35.                     if(mp[i][j]==mp[i][k]+p[k]+mp[k][j])
    36.                     {
    37.                         dis[i][j]=min(dis[i][j],dis[i][k]);//按字典序保存
    38.                     }
    39.                 }
    40.             }
    41.         }
    42.         int a,b;
    43.         while(scanf("%d%d",&a,&b))
    44.         {
    45.             if(a==-1&&b==-1)
    46.                 break;
    47.             int c=a;
    48.             int d=b;
    49.             int pre[maxl];
    50.             int cnt=0;
    51.             while(a!=b)
    52.             {
    53.                 pre[cnt++]=dis[a][b];
    54.                 a=dis[a][b];
    55.             }
    56.             printf("From %d to %d :\n",c,d);
    57.             printf("Path: %d",c);
    58.             for(int i=0; i<cnt; i++)
    59.                 printf("-->%d",pre[i]);
    60.             printf("\n");
    61.             if(mp[c][d]<inf)
    62.                 printf("Total cost : %d\n",mp[c][d]);
    63.             else
    64.                 printf("-1\n");
    65.             printf("\n");
    66.         }
    67.     }
    68.     return 0;
    69. }

    4、加一条边，使得最短路最大

    1. //给出一个由 n 个点和 m 条边组成的无向图，其中有 k 个点被标记了，题目要求选出两个被标记的点，连接一条边，使得从点 1 到点 n 的最短路最大。
    2. //题解：先来考虑一个比较简单的事情，假如现在有两个点 i 和 j ，如果其建边的话，最短路可能是 1 -> i -> j -> n 或者 1 -> j -> i -> n，这样代表的距离也就是 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 和 dis[ i ][ 1 ] + dis[ j ][ 0 ] + 1 了，因为题目要求的是最短路，所以很显然会选择更小的那一个，换句话说，当满足 dis[ i ][ 0 ] + dis[ j ][ 1 ] + 1 < dis[ i ][ 1 ] + dis[ j ][ 0 ] + 1 时，我们会选择前者，通过移项以及约分，不难化简到：dis[ i ][ 0 ] - dis[ i ][ 1 ] < dis[ j ][ 0 ] - dis[ j ][ 1 ]，这个公式又代表什么呢？也就是说，当我们现在有两个被标记的点时，dis[ i ][ 0 ] - dis[ i ][ 1 ] 更小的这个点会放在前面，而另外一个点会放在后面，这样我们O(n)枚举一遍位于后面的点 j ，然后找到点 j 前面的 dis[ i ][ 0 ] 的最大值，也就是前缀的最大值，这样可以保证相加之和是最大的，最后记得特判一下上限就好了，上限是原图的最短路。
    3. int id[N],dis[N][2];
    4. void bfs(int st,int pos)
    5. {
    6.     queue<int>q;
    7.     q.push(st);
    8.     dis[st][pos]=0;
    9.     while(q.size())
    10.     {
    11.         int u=q.front();
    12.         q.pop();
    13.         for(int i=0; i<node[u].size(); i++)
    14.         {
    15.             int to=node[u][i];
    16.             if(dis[to][pos]>dis[u][pos]+1)
    17.             {
    18.                 dis[to][pos]=dis[u][pos]+1;
    19.                 q.push(to);
    20.             }
    21.         }
    22.     }
    23. }
    24. bool cmp(int a,int b)
    25. {
    26.     return dis[a][0]-dis[a][1]<dis[b][0]-dis[b][1];
    27. }
    28. int main()
    29. {
    30.     memset(dis,inf,sizeof(dis));
    31.     int n,m,k;
    32.     scanf("%d%d%d",&n,&m,&k);
    33.     for(int i=1; i<=k; i++)
    34.         scanf("%d",id+i);
    35.     while(m--)
    36.     {
    37.         int u,v;
    38.         scanf("%d%d",&u,&v);
    39.         node[u].push_back(v);
    40.         node[v].push_back(u);
    41.     }
    42.     bfs(1,0);
    43.     bfs(n,1);
    44.     sort(id+1,id+k+1,cmp);
    45.     int maxn=0,minx=0,ans=0;
    46.     int flag=0; 
    47.     for(int i=2;i<=k;i++)
    48.     {
    49.             ans=max(ans,min(dis[id[i-1]][0]+dis[id[i]][1]+1,dis[n][0]));
    50.     }
    51.     cout<<ans<<endl;
    52.     return 0;
    53. }

    5、统计最短路条数：

    加一个way[]数组统计，每次更新dist时，way[to]=way[u]当dist相等时way[to]+=way[u]

    1. //计算到每个点最短路的数量
    2. void djks()//djks算法 
    3. {
    4.     memset(dis,inf,sizeof(dis));
    5.     memset(vis,0,sizeof(vis));
    6.     memset(c,0,sizeof(c));
    7.     dis[1]=0;
    8.     for(int i=1;i<n;i++)
    9.  {
    10.         int minx=inf;int k;
    11.         for(int j=1;j<=n;j++)
    12.         {
    13.             if(!vis[j]&&dis[j]<minx)
    14.             {
    15.                 minx=dis[j];
    16.                 k=j;
    17.             }
    18.         }
    19.         vis[k]=1;
    20.         for(int j=1;j<=n;j++)
    21.         {
    22.             if(!mp[k][j]) continue;
    23.             if(!vis[j]&&dis[j]>dis[k]+mp[k][j])
    24.             {
    25.                 c[j]=0;
    26.                 dis[j]=dis[k]+mp[k][j];
    27.             }
    28.             if(dis[j]==dis[k]+mp[k][j]&&!vis[j])
    29.                 c[j]++;
    30.         }
    31.     }
    32. }
    33. void add(int a, int b, int c)
    34. {
    35.     str[cnt].to = b;
    36.     str[cnt].w = c;
    37.     str[cnt].next = head[a];
    38.     head[a] = cnt++;
    39. }
    40. Spfa算法求
    41. void spfa()
    42. {
    43.     for (int i = 1; i <= n; i++)
    44.     {
    45.         vis[i] = 0;
    46.         c[i] = 0;
    47.         dis[i] = inf;
    48.     }
    49.     dis[1] = 0;
    50.     c[1] = 1;
    51.     queue<int>q;
    52.     q.push(1);
    53.     vis[1] = 1;
    54.     while (!q.empty())
    55.     {
    56.         int p = q.front();
    57.         q.pop();
    58.         vis[p] = 0;
    59.         for (int i = head[p]; i != -1; i = str[i].next)
    60.         {
    61.             int to = str[i].to;
    62.             if (dis[to] > dis[p] + str[i].w)
    63.             {
    64.                 dis[to] = dis[p] + str[i].w;
    65.                 if (!vis[to])
    66.                 {
    67.                     q.push(to);
    68.                     vis[to] = 1;
    69.                 }
    70.                 c[to] = c[p]%mod;
    71.             }
    72.             else if (dis[to] == dis[p] + str[i].w)
    73.             {
    74.                 c[to] = (c[to] + c[p]) % mod;
    75.             }
    76.         }
    77.     }
    78. }

    6、次短路与最短路计数

    1. //我们可以记录最短路和短路的长度及其次数并不断更新他们。每次更新是无非5种情况：比最小值小，等于最小值，大于最小值小于次小值，等于次小值，大于次小值；
    2. using namespace std;
    3. const int maxl=1100;
    4. const int inf=0x3f3f3f3f;
    5. int vis[maxl][2];
    6. int ans[maxl][2];//记录最短路和次短路数量
    7. int dis[maxl][2];//记录每个点最短路和次短路距离
    8. int n,m,s,e,cnt;
    9. struct node
    10. {
    11.     int to,next,w;
    12. } ve[maxl];
    13. int head[maxl*maxl];
    14. void add(int u,int v,int w)
    15. {
    16.     ve[cnt].to=v;
    17.     ve[cnt].w=w;
    18.     ve[cnt].next=head[u];
    19.     head[u]=cnt++;
    20. }
    21. void djks(int s,int e)
    22. {
    23.     for(int i=0;i<=n;i++)
    24.     {
    25.         dis[i][0]=dis[i][1]=inf;
    26.         ans[i][0]=ans[i][1]=inf;
    27.     }
    28.     dis[s][0]=0;
    29.     ans[s][0]=1;
    30.     memset(vis,0,sizeof(vis));
    31.     for(int i=1;i<=n*2;i++)
    32.     {
    33.         int minx=inf,flag,k=-1;
    34.         for(int j=0;j<n;j++)
    35.         {
    36.             if(!vis[j][0]&&minx>dis[j][0])
    37.             {
    38.                 minx=dis[j][0];
    39.                 flag=0;
    40.                 k=j;
    41.             }
    42.             else if(!vis[j][1]&&minx>dis[j][1])
    43.             {
    44.                 minx=dis[j][1];
    45.                 flag=1;
    46.                 k=j;
    47.             }
    48.         }
    49.         if(k==-1) break;
    50.         vis[k][flag]=1;
    51.         for(int j=head[k];j!=-1;j=ve[j].next)
    52.         {
    53.             int to=ve[j].to;
    54.             int w=ve[j].w;
    55.             if(minx+w<dis[to][0])// 比最小值小
    56.             {
    57.                 dis[to][1]=dis[to][0];//次小等于最小
    58.                 ans[to][1]=ans[to][0];
    59.                 dis[to][0]=minx+w;
    60.                 ans[to][0]=ans[k][flag];
    61.             }
    62.             else if(minx+w==dis[to][0]) ans[to][0]+=ans[k][flag];
    63.             else if(minx+w==dis[to][1]) ans[to][1]+=ans[k][flag];
    64.             else if(minx+w<dis[to][1])
    65.             {
    66.                 dis[to][1]=minx+w;
    67.                 ans[to][1]=ans[k][flag];
    68.             }
    69.         }
    70.     }
    71.     cout<<dis[e][1]<<" "<<ans[e][1]<<endl;
    72. }
    73. int main()
    74. {
    75.     while(cin>>n>>m>>s>>e)
    76.     {
    77.         memset(head,-1,sizeof(head));
    78.         cnt=0;
    79.         int a,b,c;
    80.         for(int i=0; i<m; i++)
    81.         {
    82.             cin>>a>>b>>c;
    83.             add(a,b,c);
    84.         }
    85.         djks(s,e);
    86.     }
    87.     return 0;
    88. }

    7、求路径上最大值最小(最小路径最大值)的路径

    1. //找每条路最小值，再求所有最小值的最大值（prim算法变形）;
    2. void dijk()
    3. {
    4.     memset(vis,0,sizeof(vis));
    5.     for(int i=1; i<=n; i++)
    6.         d[i]=mmp[1][i];
    7.     d[1]=0;
    8.     vis[0]=1;
    9.     for(int i=1; i<=n; i++)
    10.     {
    11.         int u=-1,m=0;
    12.         for(int j=1; j<=n; j++)
    13.         {
    14.             if(!vis[j]&&d[j]>m)
    15.             {
    16.                 m=d[j];
    17.                 u=j;
    18.             }
    19.         }
    20.         vis[u]=1;
    21.         for(int i=1; i<=n; i++)
    22.         {
    23.             if(mmp[u][i])
    24.                 d[i]=max(d[i],min(d[u],mmp[u][i]));
    25.         }
    26.     }
    27. }

    8、往返最短路，正反都跑一次最短路

    1. using namespace std;
    2. const int N=1000000+10;
    3. const int INF=0x3f3f3f3f;
    4. struct edge
    5. {
    6.     int to,w,nxt;
    7. };
    8. edge e[N];
    9. int n,cnt,head[N],a1[N],a2[N],c[N];
    10. long long dis[N];
    11. int vis[N];
    12. void add(int u,int v,int w)
    13. {
    14.     e[cnt].to=v;
    15.     e[cnt].w=w;
    16.     e[cnt].nxt=head[u];
    17.     head[u]=cnt++;
    18. }
    19. long long spfa()
    20. {
    21.     fill(dis,dis+n+1,INF);
    22.     memset(vis,0,sizeof(vis));
    23.     queue<int>q;
    24.     q.push(1);
    25.     dis[1]=0;
    26.     vis[1]=1;
    27.     while(!q.empty())
    28.     {
    29.         int u=q.front();
    30.         q.pop();
    31.         vis[u]=0;
    32.         for(int i=head[u]; i!=-1; i=e[i].nxt)
    33.         {
    34.             if(dis[e[i].to]>dis[u]+e[i].w)
    35.             {
    36.                 dis[e[i].to]=dis[u]+e[i].w;
    37.                 if(!vis[e[i].to])
    38.                 {
    39.                     q.push(e[i].to);
    40.                     vis[e[i].to]=1;
    41.                 }
    42.             }
    43.         }
    44.     }
    45.     long long res=0;
    46.     for(int i=1; i<=n; ++i)
    47.         res+=dis[i];
    48.     return res;
    49. }
    50. int main()
    51. {
    52.     int T,m;
    53.     scanf("%d",&T);
    54.     while(T--)
    55.     {
    56.         cnt=0;
    57.         scanf("%d%d",&n,&m);
    58.         fill(head,head+n+1,-1);
    59.         for(int i=0; i<m; ++i)
    60.         {
    61.             scanf("%d%d%d",&a1[i],&a2[i],&c[i]);
    62.             add(a1[i],a2[i],c[i]);
    63.         }
    64.         long long ans=spfa();
    65.         cnt=0;
    66.         fill(head,head+n+1,-1);
    67.         for(int i=0; i<m; ++i)
    68.             add(a2[i],a1[i],c[i]);
    69.         ans+=spfa();
    70.         printf("%lld\n",ans);
    71.     }
    72.     return 0;
    73. }

    9、破坏路径最短路+打印最短路

    1. //随机破坏一条路径，求最坏情况下的最短路,如果有影响破坏的路径一定在原先最短路上，先求出路径，再对每一条边分别拆掉跑一次最短路
    2. const int maxl=1000+10;
    3. const int inf=0x3f3f3f3f;
    4. struct node
    5. {
    6.     int to,cost,id;
    7.     node(int a,int b,int c):to(a),cost(b),id(c){}
    8. };
    9. bool vis[maxl],str[maxl*50],flag;
    10. int pre[maxl],dis[maxl],rode[maxl];
    11. int n,m;
    12. vector<node>ve[maxl];
    13. void spfa()
    14. {
    15.     queue<int>q;
    16.     q.push(1);
    17.     memset(vis,0,sizeof(vis));
    18.     for(int i=1;i<=n;i++) dis[i]=inf;
    19.     dis[1]=0;
    20.     vis[1]=1;
    21.     while(!q.empty())
    22.     {
    23.         int p=q.front();
    24.         q.pop();
    25.         vis[p]=0;
    26.         for(int i=0;i<ve[p].size();i++)
    27.         {
    28.             int to=ve[p][i].to;
    29.             int cost=ve[p][i].cost;
    30.             int id=ve[p][i].id;
    31.             if(str[id]) continue;//如果被破坏不能走
    32.             if(dis[to]>dis[p]+cost)
    33.             {
    34.                 dis[to]=dis[p]+cost;//更新
    35.                 if(flag)//可以保存路径
    36.                 {
    37.                     rode[to]=id;//保存通向这个点的边
    38.                     pre[to]=p;//保存这个点的前驱
    39.                 }
    40.                 if(!vis[to])
    41.                 {
    42.                     q.push(to);
    43.                     vis[to]=1;
    44.                 }
    45.             }
    46.         }
    47.     }
    48. }
    49. int main()
    50. {
    51.     int t;
    52.     scanf("%d",&t);
    53.     while(t--)
    54.     {
    55.         int a,b,c;
    56.         scanf("%d%d",&n,&m);//点的个数，边的个数
    57.         for(int i=1;i<=n;i++) ve[i].clear();
    58.         for(int i=1;i<=m;i++)
    59.         {
    60.             scanf("%d%d%d",&a,&b,&c);
    61.             ve[a].push_back(node(b,c,i));//保存末位置，以及两点之间的权值以及每条边的标号
    62.             ve[b].push_back(node(a,c,i));
    63.         }
    64.         memset(str,false,sizeof(str));//用str数组来标记某条边被破坏
    65.         flag=true;//用来区分是保存路径还是开始美剧被破坏的路径
    66.         spfa();
    67.         flag=false;
    68.         if(dis[n]==inf)//没有被破坏就无法到达目的地
    69.         {
    70.             printf("-1\n");
    71.             continue;
    72.         }
    73.         int maxn=0;
    74.         for(int i=n;i!=1;i=pre[i])//遍历最短路
    75.         {
    76.             str[rode[i]]=true;//标记这条路被破坏
    77.             spfa();
    78.             str[rode[i]]=false;//回溯
    79.             if(dis[n]==inf)//破坏后无法到达
    80.             {
    81.                 maxn=inf;
    82.                 break;
    83.             }
    84.             maxn=max(maxn,dis[n]);//保存破坏后最短路最大值
    85.         }
    86.         if(maxn==inf)
    87.         {
    88.             printf("-1\n");
    89.         }
    90.         else
    91.         {
    92.             printf("%d\n",maxn);
    93.         }
    94.     }
    95.     return 0;
    96. }

    10、用spfa判断负环（虫洞问题，是否存在一条路有负环）

    1. #define N 5210
    2. #define INF 0xfffffff
    3. int cnt, dist[N], Head[N], num[N], vis[N];
    4. int n, m, w;
    6. struct Edge
    7. {
    8.     int v, w, next;
    9. }e[N];
    11. void Add(int u, int v, int w)
    12. {
    13.     e[cnt].v = v;
    14.     e[cnt].w = w;
    15.     e[cnt].next = Head[u];
    16.     Head[u] = cnt++;
    17. }
    19. bool spfa()///spfa模板；
    20. {
    21.     memset(vis, 0, sizeof(vis));
    22.     memset(num, 0, sizeof(num));
    23.     queue<int>Q;
    24.     vis[1] = 1;
    25.     dist[1] = 0;
    26.     Q.push(1);
    27.     num[1]++;
    28.     while(Q.size())
    29.     {
    30.         int p=Q.front();
    31.         Q.pop();
    32.         vis[p] = 0;
    33.         for(int i=Head[p]; i!=-1; i=e[i].next)
    34.         {
    35.             int q = e[i].v;
    36.             if(dist[q] > dist[p] + e[i].w)
    37.             {
    38.                 dist[q] = dist[p] + e[i].w;
    39.                 if(!vis[q])
    40.                 {
    41.                     vis[q] = 1;
    42.                     Q.push(q);
    43.                     num[q] ++;
    44.                     if(num[q]>=n)
    45.                         return true;
    46.                 }
    47.             }
    48.         }
    49.     }
    50.     return false;
    51. }
    53. int main()
    54. {
    55.     int T, a, b, c;
    56.     scanf("%d", &T);
    57.     while(T--)
    58.     {
    59.         scanf("%d%d%d", &n, &m, &w);
    61.         cnt = 0;
    62.         memset(Head, -1, sizeof(Head));
    63.         for(int i=1; i<=n; i++)
    64.             dist[i] = INF;
    66.         for(int i=1; i<=m; i++)
    67.         {
    68.             scanf("%d%d%d", &a, &b, &c);
    69.             Add(a, b, c);
    70.             Add(b, a, c);
    71.         }
    72.         for(int i=1; i<=w; i++)
    73.         {
    74.             scanf("%d%d%d", &a, &b, &c);
    75.             Add(a, b, -c);
    76.         }
    78.         if( spfa() )///存在负环；
    79.             printf("YES\n");
    80.         else
    81.             printf("NO\n");
    82.     }
    83.     return 0;
    84. }

    11、 单源最短路

    1. struct Node
    2. {
    3.     int to, lat, val; //边的右端点，边下一条边，边权
    4. };
    5. Node edge[1000005];
    6. int head[1005],tot,dis[1005],N,M,sb[1005],vis[1005];
    7. int pos[1005];
    8. void add(int from, int to, int dis)
    9. {
    10.     edge[++tot].lat = head[from];
    11.     edge[tot].to = to;
    12.     edge[tot].val = dis;
    13.     head[from] = tot;
    14. }
    15. void spfa(int s)
    16. {
    18.     memset(dis, 0x3f, sizeof(dis));
    19.     memset(vis, 0, sizeof(vis));
    20.     vis[s] = 1;
    21.     dis[s] = 0;
    22.     queue<int>Q;
    23.     Q.push(s);
    24.     while (!Q.empty()) {
    25.         int u = Q.front();
    26.         Q.pop();
    27.         vis[u] = 0;
    28.         for (int i = head[u];i;i = edge[i].lat) {
    29.             int to = edge[i].to;
    30.             int di = edge[i].val;
    31.             if (dis[to]>dis[u] + di) {
    32.                 dis[to] = dis[u] + di;
    33.                 if (!vis[to]) {
    34.                     vis[to] = 1;
    35.                     Q.push(to);
    36.                 }
    37.             }
    38.         }
    39.     }
    41. }
    42. int main()
    43. {
    44.     int val, e, s, k, c;
    45.     int t, x;
    46.     scanf("%d", &t);
    47.     while (t--)
    48.     {
    49.         memset(head, 0, sizeof(head));
    50.         tot = 0;
    51.         scanf("%d %d %d %d %d", &N, &e, &s, &k, &c);//点的个数、边的个数、英雄点、消防点的个数
    52.          for (int i = 1; i <= k; ++i)//输入消防点，并和超级点连接
    53.         {
    54.             scanf("%d", &pos[i]);
    55.         }
    56.         while (e--)
    57.         {
    58.             int a, b, dis;
    59.             scanf("%d %d %d", &a, &b, &dis);
    60.             add(a, b, dis),add(b,a,dis);
    61.         }
    62.         spfa(s);
    63.         int ans2 = -1;
    64.         for (int i = 1; i <= N; ++i) ans2 = max(ans2, dis[i]);
    65.         for (int i = 1; i <= k; ++i)
    66.         {
    67.             add(0, pos[i], 0);
    68.             add(pos[i], 0, 0);
    69.         }
    70.         spfa(0);
    71.         int ans1= -1;
    72.         for (int i = 1; i <= N; ++i) ans1 = max(ans1, dis[i]);
    73.     }
    74.     return 0;
    75. }

    12、通过建辅助点减少建边

    1. //如果有两个城市群、将两个城市群的每个城市与另一个城市群的每个城市建边，暴力肯定超时，越界，给每个城市群建一个进出口（两个点）城市群城市群之间靠进出口联系，这样减少可时间和空间
    3. using namespace std;
    4. const int maxl=200000+10;
    5. const long long  inf=1e18;
    6. int cnt,n,m;
    7. struct node
    8. {
    9.     int to,next;
    10.     long long cost;
    11. } str[maxl*3];
    12. int vis[maxl*3];
    13. long long  dis[maxl*3];
    14. int head[maxl*3];
    15. void add(int v,int to,int cost)
    16. {
    17.     str[cnt].to=to;
    18.     str[cnt].cost=cost;
    19.     str[cnt].next=head[v];
    20.     head[v]=cnt++;
    21. }
    22. void spfa(int st,int en)
    23. {
    24.     for(int i=1;i<=n+m+m;i++)
    25.     {
    26.         dis[i]=1e18;将到所有点的距离设为无穷大
    27.         vis[i]=0;
    28.     }
    29.     queue<int>q;
    30.     vis[st]=1;
    31.     dis[st]=0;
    32.     q.push(st);
    33.     while(!q.empty())
    34.     {
    35.         int p=q.front();
    36.         q.pop();
    37.         vis[p]=0;
    38.         for(int i=head[p];i!=-1;i=str[i].next)
    39.         {
    40.             int to=str[i].to;
    41.             if(dis[to]>dis[p]+str[i].cost)
    42.             {
    43.                 dis[to]=dis[p]+str[i].cost;
    44.                 if(!vis[to])
    45.                 {
    46.                     vis[to]=1;
    47.                     q.push(to);
    48.                 }
    49.             }
    50.         }
    51.     }
    52.     if(dis[en]==inf)
    53.     {
    54.         printf("-1\n");
    55.     }
    56.     else
    57.     {
    58.         printf("%lld\n",dis[en]);
    59.     }
    60. }
    61. int main()
    62. {
    63.     scanf("%d%d",&n,&m);//n个城市，m个城市群
    64.     memset(head,-1,sizeof(head));
    65.     cnt=0;
    66.     int ans;
    67.     for(int i=1; i<=m; i++)
    68.     {
    69.         scanf("%d",&ans);//第i个城市群的城市个数
    70.         int p;
    71.         for(int j=1; j<=ans; j++)
    72.         {
    73.             scanf("%d",&p);
    74.             add(p,i+n,0);//将城市与出口连接
    75.             add(i+n+m,p,0);//将城市与入口连接
    76.         }
    77.     }
    78.     scanf("%d",&ans);//城市与城市之间边的个数
    79.     int a,b,c;
    80.     for(int i=1; i<=ans; i++)
    81.     {
    82.         scanf("%d%d%d",&a,&b,&c);
    83.         add(a,b,c);//建边
    84.         add(b,a,c);
    85.     }
    86.     scanf("%d",&ans);//城市群和城市群之间的边数
    87.     for(int i=1; i<=ans; i++)
    88.     {
    89.         scanf("%d%d%d",&a,&b,&c);c代表权值
    90.         add(a+n,b+n+m,c);//一个城市群的入口和另一个城市群的出口连接
    91.         add(b+n,a+n+m,c);
    92.     }
    93.     int st,en;
    94.     scanf("%d%d",&st,&en);
    95.     spfa(st,en);
    96.     return 0;
    97. }

    13、树的重心（ 树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡）

    1. const int maxl=50005;
    2. int n;
    3. struct node
    4. {
    5.     int to,next;
    6. }str[maxl*2];
    7. int head[maxl];
    8. int cnt;
    9. int sum[maxl];
    10. int dp[maxl];
    11. //int dis[maxl];
    12. void add(int x,int y)
    13. {
    14.     str[++cnt].to=y;
    15.     str[cnt].next=head[x];
    16.     head[x]=cnt;
    17. }
    18. //找重心，最长子树的节点最少
    19. void dfs(int fa,int u)
    20. {
    21.     sum[fa]=1;
    22.     for(int i=head[fa];i!=-1;i=str[i].next)
    23.     {
    24.         int to=str[i].to;
    25.         if(to!=u)
    26.         {
    27.             dfs(to,fa);
    28.             sum[fa]+=sum[to];//记录每个子树的节点数
    29.             dp[fa]=max(dp[fa],sum[to]);
    30.         }
    31.     }
    32.     dp[fa]=max(dp[fa],n-sum[fa]);
    33. }
    34. //给每个节点赋值
    35. void spfa(int fa,int u)
    36. {
    37.     for(int i=head[fa];i!=-1;i=str[i].next)
    38.     {
    39.         int to=str[i].to;
    40.         if(to!=u)
    41.         {
    42.             sum[to]=sum[fa]+1;//该题边权为1，不同的体需要更换为每个点对应的边权
    43.             spfa(to,fa);
    44.         }
    45.     }
    46. }
    47. int main()
    48. {
    49.    // int n;
    50.     cin>>n;
    51.     cnt=0;
    52.     for(int i=0;i<=n;i++)
    53.     {
    54.         head[i]=-1;
    55.         sum[i]=0;
    56.     }
    57.     int x,y;
    58.     for(int i=1;i<n;i++)
    59.     {
    60.         cin>>x>>y;
    61.         add(x,y);
    62.         add(y,x);
    63.     }
    64.     dfs(1,1);
    65.     int id=1;
    66.     for(int i=2;i<=n;i++)
    67.     {
    68.         if(dp[i]<dp[id])
    69.             id=i;
    70.     }
    71.     sum[id]=0;
    72.     spfa(id,id);
    73.     long long ans=0;
    74.     for(int i=1;i<=n;i++)
    75.     {
    76.         ans+=sum[i];
    77.     }
    78.     cout<<id<<" "<<ans<<endl;
    79.     return 0;
    80. }

    14、最小生成树prim

    1. int prim()
    2. {
    3.     for(int i=0; i<n; i++)
    4.     {
    5.         str1[i]=mp[0][i];
    6.     }
    7.     vis[0]=1;
    8.     int sum=0;
    9.     int k;
    10.     for(int i=1; i<n; i++)
    11.     {
    12.         int minx=inf;
    13.         for(int j=0; j<n; j++)
    14.         {
    15.             if(!vis[j]&&str1[j]<minx)
    16.             {
    17.                 k=j;
    18.                 minx=str1[j];
    19.             }
    20.         }
    21.         vis[k]=1;
    22.         sum+=minx;
    23.         for(int j=0; j<n; j++)
    24.         {
    25.             if(!vis[j]&&str1[j]>mp[k][j])
    26.             {
    27.                 str1[j]=mp[k][j];
    28.             }
    29.         }
    30.     }
    31.     return sum;
    32. }
    33. int main()
    34. {
    35.     cin>>n>>m;
    36.     memset(head,-1,sizeof(head));
    37.     int a,b,c;
    38.     for(int i=0;i<m;i++)
    39.     {
    40.         cin>>a>>b>>c;
    41.         add(a,b,c);
    42.         add(b,a,c);
    43.     }
    44.     prim();
    45.     return 0;
    46. }

    15、记录最小生成树路径上任意两点之间最长的边

    1. void prim()
    2. {
    3.     for(int i=1; i<=n; i++)
    4.     {
    5.         dis[i]=mp[1][i];
    6.         pre[i]=1;
    7.     }
    8.     vis[1]=1;
    9.     dis[1]=0;
    10.     double sum=0;
    11.     int k;
    12.     for(int i=1; i<n; i++)
    13.     {
    14.         double minx=inf;
    15.         for(int j=1; j<=n; j++)
    16.         {
    17.             if(!vis[j]&&minx>dis[j])
    18.             {
    19.                 minx=dis[j];
    20.                 k=j;
    21.             }
    22.         }
    23.         sum+=minx;
    24.         vis[k]=1;
    25.         //保存最小生成树每条路径大小
    26.         dp[pre[k]][k]=dp[k][pre[k]]=minx;
    27.         for(int j=1; j<=n; j++)
    28.         {
    29.             if(!vis[j]&&dis[j]>mp[k][j])
    30.             {
    31.                 pre[j]=k;
    32.                 dis[j]=mp[k][j];
    33.             }
    34.         }
    35.         //寻找最小生成树中每两个点之间最大边
    36.         for(int j=1; j<=n; j++)
    37.         {
    38.             if(vis[j]&&j!=k)
    39.             {
    40.                 dp[j][k]=max(dp[j][pre[k]],minx);
    41.                 dp[k][j]=dp[j][k];
    42.             }
    43.         }
    44.     }
    45.     double ans=0;
    46.     for(int i=1; i<=n; i++)
    47.     {
    48.         for(int j=1; j<=n; j++)
    49.         {
    50.             if(i!=j)
    51.             {
    52.                 ans=max(ans,(double)(p[i]+p[j])/(sum-dp[i][j]));
    53.             }
    54.         }
    55.     }
    56.     cout<<fixed<<setprecision(2)<<ans<<endl;
    57. }

    16、最小生成树唯一性，同时可以判断如果改变某一条边的值最小生成树是否会变化、

    1. const int inf=0x3f3f3f3f;
    2. const int maxl=100+10;
    3. int n,m;
    4. int vis[maxl],mp[maxl][maxl],dis[maxl],pre[maxl];
    5. int use[maxl][maxl],maxn[maxl][maxl];
    6. int ret;
    7. void init()
    8. {
    9.     memset(mp,inf,sizeof(mp));
    10.     memset(vis,0,sizeof(vis));
    11.     memset(use,0,sizeof(use));
    12.     memset(maxn,0,sizeof(maxn));
    13. }
    14. void prim()
    15. {
    16.     ret=0;
    17.     for(int i=1; i<=n; i++)
    18.     {
    19.         dis[i]=mp[1][i];
    20.         pre[i]=1;
    21.     }
    22.     pre[1]=0;
    23.     vis[1]=1;
    24.     for(int i=1; i<n; i++)
    25.     {
    26.         int minx=inf;
    27.         int k;
    28.         for(int j=1; j<=n; j++)
    29.         {
    30.             if(!vis[j]&&dis[j]<minx)
    31.             {
    32.                 minx=dis[j];
    33.                 k=j;
    34.             }
    35.         }
    36.         ret+=minx;
    37.         vis[k]=1;
    38.         use[pre[k]][k]=use[k][pre[k]]=1;//记录最小生成树边
    39.         maxn[k][pre[k]]=maxn[pre[k]][k]=minx;//记录最小生成树边的权值
    40.         for(int j=1; j<=n; j++)
    41.         {
    42.             if(vis[j]&&j!=k)
    43.             {
    44.                 maxn[k][j]=maxn[j][k]=max(maxn[pre[k]][j],minx);//记录点和最小生成树其他点连接线上的最大权值
    45.             }
    46.             if(!vis[j]&&dis[j]>mp[k][j])
    47.             {
    48.                 pre[j]=k;
    49.                 dis[j]=mp[k][j];
    50.             }
    51.         }
    52.     }
    53. }
    54. int main()
    55. {
    56.     int t;
    57.     while(cin>>t)
    58.     {
    59.         while(t--)
    60.         {
    61.             int flag=1;
    62.             init();
    63.             cin>>n>>m;
    64.             int a,b,c;
    65.             for(int i=1; i<=m; i++)
    66.             {
    67.                 cin>>a>>b>>c;
    68.                 mp[a][b]=mp[b][a]=c;
    69.             }
    70.             prim();
    71.             for(int i=1; i<=n; i++)
    72.             {
    73.                 for(int j=i+1; j<=n; j++)
    74.                 {
    75.                     if(use[i][j]==1||mp[i][j]==inf)
    76.                         continue;
    77.                     if(maxn[i][j]==mp[i][j])
    78.                     {
    79.                         flag=0;
    80.                         break;
    81.                     }
    82.                 }
    83.                 if(flag==0)
    84.                     break;
    85.             }
    86.             if(flag)
    87.             {
    88.                 cout<<ret<<endl;
    89.             }
    90.             else
    91.             {
    92.                 cout<<"Not Unique!"<<endl;
    93.             }
    94.         }
    95.     }
    96.     return 0;
    97. }

    17、用并查集合并树中的节点（对边的排序处理）

    1. //例题：给出N个点，它们之间有N−1条路径相连，其中K个特殊点，我们要删去一些边使得这K个点不连通，求最少的删除代价。
    2. const int maxl=100000+10;
    3. const int inf=0x3f3f3f3f;
    4. int father[maxl],vis[maxl];
    5. struct node
    6. {
    7.     int x,y,w;
    8. } str[maxl];//记录边
    9. bool cmp(node a,node b)
    10. {
    11.     return a.w>b.w;
    12. }
    13. int getf(int x)
    14. {
    15.     if(father[x]==x)
    16.         return x;
    17.     return father[x]=getf(father[x]);//合并路径
    18. }
    19. //合并点集
    20. void cmbe(int a,int b)
    21. {
    22.     int t1=getf(a);
    23.     int t2=getf(b);
    24.     if(!vis[t1]&&vis[t2])
    25.         father[t1]=t2;
    26.     else
    27.         father[t2]=t1;
    28. }
    29. int main()
    30. {
    31.     int n,m;
    32.     cin>>n>>m;
    33.     for(int i=0; i<n; i++)
    34.         father[i]=i;
    35.     int a,b,c;
    36.     memset(vis,0,sizeof(vis));
    37.     for(int i=0; i<m; i++)
    38.     {
    39.         cin>>a;
    40.         vis[a]=1;//特殊点记录下来
    41.     }
    42.     for(int i=0; i<n-1; i++)
    43.     {
    44.         cin>>str[i].x>>str[i].y>>str[i].w;
    45.     }
    46.     sort(str,str+n-1,cmp);
    47.     long long ans=0;
    48.     for(int i=0; i<n-1; i++)
    49.     {
    50.         int x=str[i].x;
    51.         int y=str[i].y;
    52.         int w=str[i].w;
    53.         if(vis[getf(x)]&&vis[getf(y)])
    54.             ans+=w;
    55.         else
    56.             cmbe(x,y);
    57.     }
    58.     cout<<ans<<endl;
    59.     return 0;
    60. }

    18、拓扑排序

    1. void tuopu()
    2. {
    3.     int k=0;
    4.     queue<int>q;
    5.     for(int i=1; i<=n; i++)
    6.     {
    7.         if(str[i]==0)//入度为0
    8.         {
    9.             q.push(i);
    10.             arr[i]=1;
    11.         }
    12.     }
    13.     while(!q.empty())
    14.     {
    15.         int p=q.front();
    16.         q.pop();
    17.         vis[k++]=p;
    18.         for(int i=1; i<=n; i++)
    19.         {
    20.             if(mp[p][i]==1)
    21.                 str[i]--;
    22.             if(str[i]==0&&arr[i]==0)
    23.             {
    24.                 q.push(i);
    25.                 arr[i]=1;
    26.             }
    27.         }
    28.     }
    29. }

    19、匈牙利算法最大匹配

    1. #include<iostream>
    2. #include<string.h>
    3. #include<algorithm>
    4. #include<string>
    5. #include<cmath>
    6. using namespace std;
    7. const int maxl = 1000 + 10;
    8. int vis[maxl];
    9. int mach[maxl];
    10. int mp[maxl][maxl];
    11. int m, p;
    12. bool dfs(int u)
    13. {
    14.     for (int i = 1; i <= p; i++)
    15.     {
    16.         if (vis[i] == 0 && mp[u][i])
    17.         {
    18.             vis[i] = 1;
    19.             if (mach[i] == 0 || dfs(mach[i]))
    20.             {
    21.                 mach[i] = u;
    22.                 return true;
    23.             }
    24.         }
    25.     }
    26.     return false;
    27. }
    28. int main()
    29. {
    30.     int n;
    31.     while (cin >> n)
    32.     {
    33.         if (n == 0)
    34.             break;
    35.         cin >> m >> p;
    36.         int a, b;
    37.         memset(mach, 0, sizeof(mach));
    38.         memset(mp, 0, sizeof(mp));
    39.         for (int i = 0; i < n; i++)
    40.         {
    41.             cin >>a>>b;
    42.             mp[a][b] = 1;
    43.         }
    44.         int ans = 0;
    45.         for (int i = 1; i <= m; i++)
    46.         {
    47.             memset(vis, 0, sizeof(vis));
    48.             if (dfs(i))
    49.                 ans++;
    50.         }
    51.         cout << ans << endl;
    52.     }
    53.     return 0;
    54. }

    拓展题

    • 一个人在某一排选座位，每排有两个座位
      1. const int maxl=4000+10;
      2. struct node
      3. {
      4.   int to,next;
      5. } str[11000];
      6. int vis[maxl],mach[maxl][2];
      7. int head[maxl],cnt;
      8. void add(int a,int b)
      9. {
      10.   str[++cnt].to=b;
      11.   str[cnt].next=head[a];
      12.   head[a]=cnt;
      13. }
      14. bool dfs(int u)
      15. {
      16.   for(int i=head[u]; i!=-1; i=str[i].next)
      17.   {
      18.       int to=str[i].to;
      19.       if(!vis[to])
      20.       {
      21.           vis[to]=1;
      22.           if(mach[to][0]==0||dfs(mach[to][0]))//二维数组作为两个座位
      23.           {
      24.               mach[to][0]=u;
      25.               return true;
      26.           }
      27.           if(mach[to][1]==0||dfs(mach[to][1]))
      28.           {
      29.               mach[to][1]=u;
      30.               return true;
      31.           }
      32.       }
      33.   }
      34.   return false;
      35. }
      36. int main()
      37. {
      38.   int n;//n排座位，2*n个人
      39.   cin>>n;
      40.   int a,b;
      41.   cnt=0;
      42.   memset(head,-1,sizeof(head))；
      43.       memset(mach, 0, sizeof(mach));
      44.   for(int i=1; i<=2*n; i++)
      45.   {
      46.       scanf("%d%d",&a,&b);
      47.       add(i,a);//人对应座位
      48.       add(i,b);
      49.   }
      50.   int ans=0;
      51.   for(int i=1; i<=2*n; i++)
      52.   {
      53.       memset(vis,0,sizeof(vis));
      54.       if(dfs(i))
      55.           ans++;
      56.   }
      57.   cout<<ans<<endl;
      58.   return 0;
      59. }
    • 有n个位数相同的数组，从每个数组中选出一个数，要求是连续递增，最长有多长。
    1. const int maxl = 1000000 + 10;
    2. const int maxn = 10000 + 5;
    3. int vis[maxn];
    4. int mach[maxl],n;
    5. struct node
    6. {
    7.     int to, next;
    8. }str[2*maxl];
    9. int head[2 * maxn];
    10. int cnt;
    11. void add(int x, int y)
    12. {
    13.     str[++cnt].to = y;
    14.     str[cnt].next = head[x];
    15.     head[x] = cnt;
    16. }
    17. bool  dfs(int a)
    18. {
    19.     if (vis[a]) return false;//不能去找已经选完的点
    20.     vis[a] = 1;//标记数字
    21.     for (int i = head[a]; i != -1; i = str[i].next)//不需要去判断是否有关系
    22.     {
    23.         int to=str[i].to;
    24.         if (mach[to] == 0 || dfs(mach[to]))
    25.         {
    26.             mach[to] = a;
    27.             return true;
    28.         }
    29.     }
    30.     return false;
    31. }
    32. int main()
    33. {
    34.     cin >> n;
    35.     int a, b;
    36.     memset(mach, 0, sizeof(mach));
    37.     memset(head, -1, sizeof(head));
    38.     cnt = 0;
    39.     //反思想建表，一个数字对应多个数组，标记数字
    40.     for (int i = 1; i <= n; i++)
    41.     {
    42.         scanf("%d%d", &a, &b);
    43.         add(a, i);
    44.         add(b, i);
    45.     }
    46.     int ans = 0;
    47.     for (int i = 1; i <= 10000; i++)//从小到大按顺序找
    48.     {
    49.         memset(vis, 0, sizeof(vis));
    50.         if (dfs(i))
    51.             ans++;
    52.         else
    53.             break;
    54.     }
    55.     printf("%d\n", ans);
    56.     return 0;
    57. }

    20、 二分图判断

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3. const int maxn = 20010;
    4. vector<int> ve[maxn];
    5. int color[maxn], fa[maxn], n, m, vis[maxn],str[maxn],arr[maxn];
    6. bool dfs(int v,int c){
    7.     color[v] = c;
    8.     for(int i = 0;i < ve[v].size(); i++){
    9.         //如果相邻的两个颜色相同不符合
    10.         if(color[ve[v][i]] == c) return false;
    11.         //如果相邻的两个颜色不同则给这个节点附上颜色，并且检查这个字节点的情况
    12.         if(color[ve[v][i]] == 0 && !dfs(ve[v][i],-c)) return false;
    13.     }
    14.     return true;
    15. }
    17. int main() {
    18.     int x, y, a, b;
    19.     while(cin >> n >> m) {
    20.         int flag = 0;
    21.         memset(color, 0, sizeof(color));
    22.         for(int i = 0; i <= n; i++) {
    23.             ve[i].clear();
    24.         }
    25.         //输入存图
    26.         for(int i = 1; i <= m; i++) {
    27.             cin >> a >> b;
    28.             ve[a].push_back(b);
    29.             ve[b].push_back(a);
    30.         }
    31.         for(int i = 1; i <= n; i++) {
    32.             if(color[i] == 0) {
    33.                 //如果不符合
    34.                 if(!dfs(i,1)) {
    35.                     color[i] = 1;
    36.                     flag = 1;
    37.                     break;
    38.                 }
    39.             }
    40.         }
    41.     }
    42.     return 0;
    43. }

    21、最大流

    1. const int maxn=2e5+10;
    2. const int inf=0x3f3f3f3f;
    3. struct node
    4. {
    5.     int to,w,next;
    6. } e[maxn];
    7. int n,m,s,en;
    8. int dis[maxn];
    9. int head[maxn];
    10. int cnt;
    11. void add(int a,int b,int w)
    12. {
    13.     e[cnt].to=b;
    14.     e[cnt].w=w;
    15.     e[cnt].next=head[a];
    16.     head[a]=cnt;
    17.     cnt++;
    18. }
    19. bool bfs(int s,int en)//找增广路
    20. {
    21.     memset(dis,0,sizeof(dis));
    22.     dis[s]=1;
    23.     queue<int>q;
    24.     q.push(s);
    25.     while(!q.empty())
    26.     {
    27.         int p=q.front();
    28.         q.pop();
    29.         for(int i=head[p]; i!=-1; i=e[i].next)
    30.         {
    31.             int to=e[i].to;
    32.             if(e[i].w>0&&!dis[to])//边的权不为0且没有被记录
    33.             {
    34.                 dis[to]=dis[p]+1;//加一
    35.                 q.push(to);//入队
    36.             }
    37.         }
    38.     }
    39.     return dis[en]>0;//看最后边的权是否为0
    40. }
    41. int dfs(int s,int exp)//计算最大流
    42. {
    43.     if(s==en) return exp;
    44.     int add=0;
    45.     for(int i=head[s]; i!=-1; i=e[i].next)
    46.     {
    47.         int to=e[i].to;
    48.         if(dis[to]!=dis[s]+1||e[i].w<=0) continue;
    49.         int x=dfs(to,min(exp-add,e[i].w));
    50.         if(!x){dis[to]=-1;continue;}
    51.         if(x)
    52.         {
    53.             e[i].w-=x;
    54.             e[i^1].w+=x;//建反边
    55.             add+=x;
    56.         }
    57.     }
    58.     Return add;
    59. }
    60. int main()
    61. {
    62.     scanf("%d%d%d%d",&n,&m,&s,&en);
    63.     int x,y,w;
    64.     memset(head,-1,sizeof(head));
    65.     // memset(dis,0,sizeof(dis));
    66.     for(int i=1; i<=m; i++)
    67.     {
    68.         scanf("%d%d%d",&x,&y,&w);
    69.         add(x,y,w);
    70.         add(y,x,0);
    71.     }
    72.     cnt=0;
    73.     int ans=0;
    74.     while(bfs(s,en))//存在增广路
    75.     {
    76.         ans+=dfs(s,inf);
    77.     }
    78.     printf("%d\n",ans);
    79.     return 0;
    80. }

    22、二分时间+最大流

    1. //题目描述：若干个石油起点汇点，每个起点有一定的储存石油，每个汇点有一定的石油需求，每个起点可以通向多个汇点，但都要相应的时间，现在要以最短的时间满足汇点的需求，可以采用二分时间+最大流，建一个超级起点超级汇点、起点连接石油起点，边权为石油储存量、终点连接汇点，边权为需求量，起点和汇点之间连接按照是否满足时间来确定是否连接，边权为无穷大。
    2. const int inf=0x3f3f3f3f;
    3. const int maxl=1000000+10;
    4. struct node
    5. {
    6.     int u,to,next,w;
    7. } ve[maxl*2];
    8. struct point
    9. {
    10.     int u,v,w;
    11. } e[maxl*2];
    12. int cnt,head[maxl];
    13. int dis[maxl],st,en;
    14. int str[maxl],arr[maxl];
    15. void add(int u,int v,int w)
    16. {
    17.     ve[cnt].u=u;
    18.     ve[cnt].to=v;
    19.     ve[cnt].next=head[u];
    20.     ve[cnt].w=w;
    21.     head[u]=cnt++;
    22. }
    23. bool bfs(int s,int en)
    24. {
    25.     queue<int>q;
    26.     memset(dis,0,sizeof(dis));
    27.     dis[s]=1;
    28.     q.push(s);
    29.     while(!q.empty())
    30.     {
    31.         int p=q.front();
    32.         q.pop();
    33.         for(int i=head[p]; i!=-1; i=ve[i].next)
    34.         {
    35.             int to=ve[i].to;
    36.             if(ve[i].w>0&&!dis[to])
    37.             {
    38.                 dis[to]=dis[p]+1;
    39.                 q.push(to);
    40.             }
    41.         }
    42.     }
    43.     return dis[en]>0;
    44. }
    45. int dfs(int s,int exp)
    46. {
    47.     if(s==en) return exp;
    48.     int add=0;
    49.     for(int i=head[s]; i!=-1&&add<exp; i=ve[i].next)
    50.     {
    51.         int to=ve[i].to;
    52.         if(dis[to]!=dis[s]+1||ve[i].w<=0) continue;
    53.         int x=dfs(to,min(exp-add,ve[i].w));
    54.         if(!x){dis[to]=-1;continue;}
    55.         if(x)
    56.         {
    57.             ve[i].w-=x;
    58.             ve[i^1].w+=x;
    59.             add+=x;
    60.         }
    61.     }
    62.     return add;
    63. }
    64. int ans,sum;
    65. int p,r,c;
    66. void dinic()
    67. {
    68.     while(bfs(st,en)) ans+=dfs(st,inf);
    69. }
    70. 对每次时间建图，看最大流是不是满最大流
    71.     bool check(int time)
    72. {
    73.     memset(ve,0,sizeof(ve));
    74.     memset(head,-1,sizeof(head));
    75.     memset(dis,0,sizeof(dis));
    76.     ans=0;
    77.     st=0;
    78.     en=p+r+10;
    79.     for(int i=1; i<=r; i++) add(st,i,arr[i]),add(i,st,0);
    80.     for(int i=1; i<=p; i++) add(i+r,en,str[i]),add(en,i+r,0);
    81.     for(int i=1; i<=c; i++)
    82.     {
    83.         if(time>=e[i].w)
    84.         {
    85.             add(e[i].v,e[i].u+r,inf);
    86.             add(e[i].u+r,e[i].v,0);
    87.         }
    88.     }
    89.     dinic();
    90.     if(ans==sum) return true;
    91.     return false;
    92. }
    93. int main()
    94. {
    95.     memset(head,-1,sizeof(head));
    96.     scanf("%d%d%d",&p,&r,&c);
    97.     for(int i=1; i<=p; i++)
    98.     {
    99.         scanf("%d",&str[i]);
    100.         sum+=str[i];
    101.     }
    102.     for(int i=1; i<=r; i++)
    103.         scanf("%d",&arr[i]);
    104.     for(int i=1; i<=c; i++)
    105.         scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    106.     int l=0,r=1e7+1;
    107.     bool flag=false;
    108.     int x=0;
    109.     while(l<=r)
    110.     {
    111.         int mid=(l+r)/2;
    112.         if(check(mid))
    113.         {
    114.             r=mid-1;
    115.             x=mid;
    116.             flag=1;
    117.         }
    118.         else
    119.         {
    120.             l=mid+1;
    121.         }
    122.     }
    123.     if(!flag) cout<<-1<<endl;
    124.     else
    125.         cout<<x<<endl;
    126.     return 0;
    127. }

    23、最小割（通过删除边让两点不能形成通路且权值最小）

    1. #include<iostream>
    2. #include<cstdio>
    3. #include<algorithm>
    4. #include<queue>
    5. #include<cstring>
    6. #include<string>
    7. #include<map>
    8. using namespace std;
    9. const int maxn=5000+10;
    10. const int maxm=200000+5;
    11. const int inf=0x3f3f3f3f;
    12. int que[maxn];
    13. int dep[maxn],cur[maxn],str[maxn];
    14. struct Edge
    15. {
    16.     int to,next,w,flow;
    17. } edge[maxm];
    18. int cnt;
    19. int head[maxn];
    20. void init()
    21. {
    22.     cnt=2;
    23.     memset(head,-1,sizeof(head));
    24. }
    25. void add(int u,int v,int w)
    26. {
    27.     edge[cnt].to=v;
    28.     edge[cnt].w=w;
    29.     edge[cnt].flow=0;
    30.     edge[cnt].next=head[u];
    31.     head[u]=cnt++;
    32.     edge[cnt].to=u;
    33.     edge[cnt].w=0;
    34.     edge[cnt].flow=0;
    35.     edge[cnt].next=head[v];
    36.     head[v]=cnt++;
    37. }
    38. bool bfs(int s,int t,int n)
    39. {
    40.     int header=0,tail=0;
    41.     memset(dep,-1,sizeof(dep));
    42.     dep[s]=0;
    43.     que[tail++]=s;
    44.     while(header<tail)
    45.     {
    46.         int u=que[header];
    47.         header++;
    48.         for(int i=head[u]; i!=-1; i=edge[i].next)
    49.         {
    50.             int v=edge[i].to;
    51.             if(edge[i].w>edge[i].flow&&dep[v]==-1)
    52.             {
    53.                 dep[v]=dep[u]+1;
    54.                 if(v==t) return true;
    55.                 que[tail++]=v;
    56.             }
    57.         }
    58.     }
    59.     return false;
    60. }
    61. int dinic(int s,int t,int n)
    62. {
    63.     int maxflow=0;
    64.     while(bfs(s,t,n))
    65.     {
    66.         for(int i=0; i<n; i++) cur[i]=head[i];
    67.         int u=s,tail=0;
    68.         while(cur[s]!=-1)
    69.         {
    70.             if(u==t)
    71.             {
    72.                 int sum=inf;
    73.                 for(int i=tail-1; i>=0; i--)
    74.                 {
    75.                     sum=min(sum,edge[str[i]].w-edge[str[i]].flow);
    76.                 }
    77.                 maxflow+=sum;
    78.                 for(int i=tail-1; i>=0; i--)
    79.                 {
    80.                     edge[str[i]].flow+=sum;
    81.                     edge[str[i]^1].flow-=sum;
    82.                     if(edge[str[i]].w-edge[str[i]].flow==0) tail=i;
    83.                 }
    84.                 u=edge[str[tail]^1].to;
    85.             }
    86.             else if(cur[u]!=-1&&edge[cur[u]].w>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to])
    87.             {
    88.                 str[tail++]=cur[u];
    89.                 u=edge[cur[u]].to;
    90.             }
    91.             else
    92.             {
    93.                 while(u!=s&&cur[u]==-1) u=edge[str[--tail]^1].to;
    94.                 cur[u] = edge [cur[u]].next;
    95.             }
    96.         }
    97.     }
    98.     return maxflow;
    99. }
    100. int main()
    101. {
    102.     int t;
    103.     scanf("%d",&t);
    104.     while(t--)
    105.     {
    106.         init();
    107.         int n,m,k;
    108.         cin>>n>>m>>k;
    109.         int start=0,End=2*n+1;
    110.         int u,v,w;
    111.         for(int i=1; i<=m; i++)
    112.         {
    113.             cin>>u>>v>>w;
    114.             add(u+n,v,w);
    115.         }
    116.         for(int i=1; i<=n; i++)
    117.         {
    118.             cin>>w;
    119.             add(start,i,w);
    120.         }
    121.         for(int i=1; i<=n; i++)
    122.         {
    123.             cin>>w;
    124.             add(i,i+n,w);
    125.         }
    126.         add(k+n,End,inf);
    127.         cout<<dinic(start,End,2*n+1)<<endl;
    128.     }
    129.     return 0;
    130. }

    24、最小费用最大流

    1. #define ll long long
    2. #define INF 0x3f3f3f3f
    3. const int maxn = 1e5+5;
    4. using namespace std;
    5. struct node
    6. {
    7.     int to;
    8.     int c;
    9.     int cost;
    10.     int next;
    11. } e[maxn];
    12. int head[maxn],cnt,l,r,n,m;
    13. int maxflow,mincost;
    14. bool vis[maxn];
    15. int dis[maxn],pre[maxn];
    16. void insert(int u,int v,int c,int w)
    17. {
    18.     e[cnt].to = v;
    19.     e[cnt].c = c;
    20.     e[cnt].cost = w;
    21.     e[cnt].next = head[u];
    22.     head[u] = cnt++;
    23. }
    24. void addedge(int u,int v,int c,int w)
    25. {
    26.     insert(u,v,c,w);
    27.     insert(v,u,0,-w);
    28. }
    29. bool SPFA(int s,int t)
    30. {
    31.     memset(vis,0,sizeof(vis));
    32.     memset(pre,-1,sizeof(pre));
    33.     memset(dis,0x3f3f3f3f,sizeof(dis));
    34.     queue<int> q;
    35.     q.push(s);
    36.     vis[s]=1;
    37.     dis[s]=0;
    38.     while(!q.empty())
    39.     {
    40.         int x = q.front();
    41.         q.pop();
    42.         vis[x] = 0;
    43.         for(int i = head[x]; i!=-1; i = e[i].next)
    44.         {
    45.             int to = e[i].to;
    46.             if(e[i].c && dis[to] > dis[x] + e[i].cost)
    47.             {
    48.                 dis[to] = dis[x] + e[i].cost;
    49.                 pre[to] = i;
    50.                 if(!vis[to])
    51.                 {
    52.                     vis[to] = 1;
    53.                     q.push(to);
    54.                 }
    55.             }
    56.         }
    57.     }
    58.     return pre[t] != -1;
    59. }
    60. void MCMF(int s,int t)
    61. {
    62.     int ans = 0;
    63.     while(SPFA(s,t))
    64.     {
    65.         int flow = INF;
    66.         for(int i = t; i != s; i = e[pre[i]^1].to)
    67.         {
    68.             flow = min(flow, e[pre[i]].c);
    69.         }
    70.         maxflow+=flow;
    71.         for(int i=t; i!=s; i = e[pre[i]^1].to)
    72.         {
    73.             e[pre[i]].c-=flow;
    74.             e[pre[i]^1].c+=flow;
    75.             mincost += e[pre[i]].cost*flow;
    76.         }
    77.     }
    78. }
    79. int main()
    80. {
    81.     int n,m,s,en;
    82.     scanf("%d%d%d%d", &n, &m, &s, &en);
    83.     memset(head, -1, sizeof(head));
    84.     cnt = 0;
    85.     int x, y, w, cost;
    86.     for (int i = 1; i <= m; i++)
    87.     {
    88.         scanf("%d%d%d%d", &x, &y, &w, &cost);
    89.         addedge(x, y, w, cost);
    90.     }
    91.     MCMF(s,en);
    92.     cout << maxflow << " " << mincost << endl;
    93.     return 0;
    94. }

    25、km算法（带权二分图的最优匹配，最大效率问题）

    1. //男女匹配问题，每个女生对男生都有一定的好感度，求最大和好感度（求最小匹配，将权值改为负数，最后答案输出绝对值）
    2.     using namespace std;
    3. const int inf=0x3f3f3f3f;
    4. const int maxl=310;
    5. int n;
    6. int mp[maxl][maxl];//记录好感度
    7. int vis[maxl],vb[maxl];//记录每一轮匹配锅的男生和女生
    8. int eb[maxl],eg[maxl];//每个男生女生的期望值
    9. int math[maxl];//能否匹配
    10. int slack[maxl];//记录男生能与女生匹配需要最少期望值
    11. int dfs(int id)
    12. {
    13.     vis[id]=1;
    14.     for(int i=0; i<n; i++)
    15.     {
    16.         if(vb[i]) continue;//每个男生只尝试一次
    17.         int sum=eg[id]+eb[i]-mp[id][i];
    18.         if(sum==0)
    19.         {
    20.             vb[i]=1;
    21.             if(math[i]==-1||dfs(math[i])) // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
    22.             {
    23.                 math[i]=id;
    24.                 return 1;
    25.             }
    26.         }
    27.         else
    28.         {
    29.             slack[i]=min(slack[i],sum);
    30.         }
    31.     }
    32.     return 0;
    33. }
    34. void km()
    35. {
    36.     memset(math,-1,sizeof(math));//没有匹配
    37.     memset(eb,0,sizeof(eb));//每个男生期望值为0
    38.     // 每个女生的初始期望值是与她相连的男生最大的好感度
    39.     for(int i=0; i<n; i++)
    40.     {
    41.         eg[i]=mp[i][0];
    42.         for(int j=1; j<n; j++)
    43.             eg[i]=max(mp[i][j],eg[i]);
    44.     }
    45.     // 尝试为每一个女生解决归宿问题
    46.     for(int i=0; i<n; i++)
    47.     {
    48.         memset(slack,inf,sizeof(slack)); // 因为要取最小值 初始化为无穷大
    49.         while(1)
    50.         {
    51.             // 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
    52.             // 记录每轮匹配中男生女生是否被尝试匹配过
    53.             memset(vis,0,sizeof(vis));
    54.             memset(vb,0,sizeof(vb));
    55.             int d=inf;
    56.             if(dfs(i)) break;//找到退出
    57.             for(int i=0;i<n;i++) if(!vb[i]) d=min(d,slack[i]);
    58.             for(int i=0; i<n; i++)
    59.             {
    60.                 // 所有访问过的女生降低期望值
    62.                 if(vis[i]) eg[i]-=d;
    63.                 // 所有访问过的男生增加期望值
    64.                 if(vb[i]) eb[i]+=d;
    65.                 else slack[i]-=d;
    66.             }
    67.         }
    68.     }
    69. }
    70. int main()
    71. {
    72.     while(cin>>n)
    73.     {
    74.         memset(mp,0,sizeof(mp));
    75.         for(int i=0; i<n; i++)
    76.         {
    77.             for(int j=0; j<n; j++)
    78.             {
    79.                 scanf("%d",&mp[i][j]);
    80.             }
    81.         }
    82.         km();
    83.         int ans=0;
    84.         for(int i=0; i<n; i++)
    85.         {
    86.             ans+=mp[math[i]][i];
    87.         }
    88.         cout<<ans<<endl;
    89.     }
    90.     return 0;
    91. }
    95. //Km算法优化
    96. using namespace std;
    97. typedef long long ll;
    98. const int MAX = 450;
    99. int n;
    100. ll b[MAX],c[MAX];
    101. ll d[MAX];
    102. int sum[MAX];
    103. struct node
    104. {
    105.     ll num;
    106.     int val;
    107. }a[MAX];
    108. int mp[MAX][MAX];
    109. int lx[MAX],ly[MAX],match[MAX],slack[MAX];
    110. int pre[MAX];
    111. bool vis[MAX];
    112. void dfs(int root)
    113. {
    114.     fill(vis+1,vis+1+n,false);
    115.     fill(slack+1,slack+1+n,INF);
    116.     int p;
    117.     match[p=0] =root;
    118.     do
    119.     {
    120.         vis[p]=true;
    121.         int x=match[p],yy;
    122.         int delta = INF;
    123.         for(int i=1; i<=n; i++)
    124.         {
    125.             if(!vis[i])
    126.             {
    127.                 if(lx[x]+ly[i]-mp[x][i]<slack[i])
    128.                     slack[i] = lx[x]+ly[i]-mp[x][i],pre[i]=p;
    129.                 if(slack[i]<delta) delta=slack[i],yy=i;
    130.             }
    131.         }
    132.         for(int i=0; i<=n; i++)
    133.         {
    134.             if(vis[i])
    135.                 lx[match[i]] -= delta,ly[i] += delta;
    137.             else
    138.                 slack[i] -= delta;
    139.         }
    140.         p=yy;
    141.     }
    142.     while(match[p]!= -1);
    143.     do
    144.     {
    145.         int pr = pre[p];
    146.         match[p] = match[pr],p=pr;
    147.     }
    148.     while(p);
    149. }
    150. void km()
    151. {
    152.     for(int i=1; i<=n; i++)
    153.     {
    154.         lx[i]=ly[i]=0;
    155.         match[i]=-1;
    156.         for(int j=1; j<=n; j++)
    157.         {
    158.             lx[i]=max(lx[i],mp[i][j]);
    159.         }
    160.     }
    161.     int ans =0;
    162.     for(int i = 1; i<=n; i++) dfs(i);
    163.     for(int i=1; i<=n; i++) ans += lx[i],ans += ly[i];
    164.     printf("%d\n",ans);
    165. }
    166. bool cmp(node a,node b)
    167. {
    168.     return a.num<b.num;
    169. }
    170. int main()
    171. {
    172.     scanf("%d",&n);
    173.     for(int i=1; i<=n; i++)
    174.     {
    175.         scanf("%lld",&a[i].num);
    176.     }
    177.     for(int i=1; i<=n; i++)
    178.     {
    179.         scanf("%d",&a[i].val);
    180.     }
    181.     for(int i=1; i<=n; i++)
    182.     {
    183.         scanf("%lld",&b[i]);
    184.     }
    185.     for(int i=1; i<=n; i++)
    186.     {
    187.         scanf("%lld",&c[i]);
    188.     }
    189.     sort(b+1,b+1+n);
    190.     sort(c+1,c+1+n);
    191.     sort(a+1,a+1+n,cmp);
    192.     sum[0]=0;
    193.     for(int i=1; i<=n; i++)
    194.     {
    195.         sum[i] = sum[i - 1] + a[i].val;
    196.         d[i]=a[i].num;
    197. }
    198. //存边
    199.     for(int i=1; i<=n; i++)
    200.     {
    201.         int last=1;
    202.         for(int j=1; j<=n; j++)
    203.         {
    204.             ll val = b[i] + c[j];
    206.             while(d[last] < val&&last<=n) last++;
    207.             mp[i][j]=sum[last-1];
    208.         }
    209.     }
    210.     km();
    211.     return 0;
    212. }

    26、强连通图（tarjan算法）

    1. const int maxl=100000+10;
    2. int head[maxl],dfn[maxl],low[maxl],fa[maxl],num[maxl],out[maxl];
    3. //dfn记录每个点被访问的顺序，low记录这个点前面最小的前序，fa记录该点所属的连通图，num记录
    4. //每个连通图有几个点，out记录每个连通图的出度
    5. bool vis[maxl];//是否在栈内
    6. stack<int>sta;
    7. int cnt,idx,sum,n,m;
    8. struct node
    9. {
    10.     int to,next;
    11. } ve[maxl];
    12. void add(int u,int v)
    13. {
    14.     ve[++cnt].to=v;
    15.     ve[cnt].next=head[u];
    16.     head[u]=cnt;
    17. }
    18. void tarjan(int u)
    19. {
    20.     low[u]=dfn[u]=++idx;
    21.     vis[u]=1;//入栈标记
    22.     sta.push(u);
    23.     for(int i=head[u]; i!=-1; i=ve[i].next)
    24.     {
    25.         int to=ve[i].to;
    26.         if(!dfn[to])
    27.         {
    28.             tarjan(to);
    29.             low[u]=min(low[u],low[to]);//取最小前序
    30.         }
    31.         else if(vis[to])//形成回路
    32.         {
    33.             low[u]=min(low[u],dfn[to]);
    34.         }
    35.     }
    36.     if(dfn[u]==low[u])//组成连通图
    37.     {
    38.         int v;
    39.         sum++;
    40. //遍历连通图中的点
    41.         do
    42.         {
    43.             v=sta.top();
    44.             fa[v]=sum;
    45.             vis[v]=0;
    46.             num[sum]++;
    47.             sta.pop();
    48.         }
    49.         while(v!=u);
    50.     }
    51. }
    52. void init()
    53. {
    54.     memset(head,-1,sizeof(head));
    55.     memset(vis,0,sizeof(vis));
    56.     memset(dfn,0,sizeof(dfn));
    57.     cnt=0;
    58.     sum=0;
    59.     idx=0;
    60.     memset(fa,0,sizeof(fa));
    61.     memset(low,0,sizeof(low));
    62.     memset(num,0,sizeof(num));
    63. }
    64. int main()
    65. {
    66.     cin>>n>>m;
    67.     int a,b;
    68.     init();
    69.     for(int i=0; i<m; i++)
    70.     {
    71.         cin>>a>>b;
    72.         add(a,b);
    73.     }
    74.     for(int i=1; i<=n; i++)
    75.     {
    76.         if(!dfn[i])
    77.             tarjan(i);
    78.     }
    79. //统计每个连通图的出度
    80.     for(int i=1; i<=n; i++)
    81.     {
    82.         for(int j=head[i]; j!=-1; j=ve[j].next)
    83.         {
    84.             int to=ve[j].to;
    85.             if(fa[i]!=fa[to]) out[fa[i]]++;
    86.         }
    87.     }
    88. //统计被其他n-1个牛欣赏的牛的个数
    89.     int ans=0;
    90.     for(int i=1; i<=sum; i++)
    91.     {
    92.         if(!out[i])
    93.         {
    94.             if(ans)
    95.             {
    96.                 ans=0;
    97.                 break;
    98.             }
    99.             ans=num[i];
    100.         }
    101.     }
    102.     cout<<ans<<endl;
    103.     return 0;
    104. }