ChiBi ZOJ - 3080

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

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

#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; idis[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]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！