本文共 1138 字，大约阅读时间需要 3 分钟。

题意：曹操有一些船，这些船很多是连在一起的，现在让你派一些士兵去烧船，其中要求派出的士兵数最少（隐含意：由于一些船是连在一起的，所以就是一个连通块派出一个士兵）现在问你烧掉所有的船所需要的最少时间。

思路：先使用并查集将每个联通快，直接标记即可，然后遍历每个联通快里的节点，找出每个烧掉每个联通快所需要的最少时间，然后取所有联通快烧掉时所用时间最长的一个。

#include 
   
    using namespace  std;const int maxn=1050;int n;int mat[maxn][maxn];vector
    
      v[maxn];int a[maxn];vector
     
       sub[maxn];int vis[maxn];int id[maxn];int t[maxn];int inq[maxn];const int inf=0x3f3f3f;int dis[maxn];int fa[maxn];void Init(){    for(int i=0; i<=n; i++)    {        v[i].clear();        fa[i]=i;    }}int Find_x(int x){    return fa[x]=(x==fa[x]?x:Find_x(fa[x]));}int spfa(int u){    queue
      
        p;    p.push(u);    memset(inq,0,sizeof(inq));    inq[u]=1;    memset(dis,inf,sizeof(dis));    dis[u]=0;    while(!p.empty())    {        int s=p.front();        p.pop();        inq[s]=0;        for(int i=0; i
       
        dis[s]+mat[s][son])            {                dis[son]=dis[s]+mat[s][son];                if(!inq[son])                {                    inq[son]=1;                    p.push(son);                }            }        }    }    int ans=0;    for(int i=1; i<=n; i++)    {        if(dis[i]
       
      
     
    
   

转载地址：http://efgsi.baihongyu.com/