【思维题 并查集 图论】bzoj1576: [Usaco2009 Jan]安全路经Travel

Description

Input

* 第一行: 两个空格分开的数, N和M

* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output

* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

---

题目分析

做法一

暴力树剖线段树

做法二

并查集[bzoj1576] [Usaco2009 Jan]安全路经Travel

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxm = ;

 int n,m,dis[maxn];

 struct cmp

 {

     bool operator ()(int a, int b) const

     {

         return dis[a] > dis[b];

     }

 };

 struct Edge

 {

     int y,val;

     Edge(int a=, int b=):y(a),val(b) {}

 }edges[maxm];

 struct EdgeSv

 {

     int x,y,dis;

     bool operator < (EdgeSv a) const

     {

         return dis < a.dis;

     }

     EdgeSv(int a=, int b=, int c=):x(a),y(b),dis(c) {}

 }edgeSv[maxm];

 int fa[maxn],fat[maxn],tag[maxn],dep[maxn];

 bool disVis[maxn],treeTag[maxm];

 int edgeTot,svTot,nxt[maxm],pre[maxm],head[maxn];

 std::priority_queue<int, std::vector<int>, cmp> q;

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch = getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch = getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 void addedge(int u, int v)

 {

     int c = read();

     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

     edges[++edgeTot] = Edge(u, c), nxt[edgeTot] = head[v], head[v] = edgeTot;

 }

 int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}

 int main()

 {

     memset(dis, 0x3f3f3f3f, sizeof dis);

     memset(head, -, sizeof head);

     n = read(), m = read();

     for (int i=; i<=n; i++) fa[i] = i;

     for (int i=; i<=m; i++) addedge(read(), read());

     dis[] = , q.push();

     while (q.size())

     {

         int tt = q.top();

         q.pop();

         for (int i=head[tt]; i!=-; i=nxt[i])

             if (dis[edges[i].y] > dis[tt]+edges[i].val){

                 dis[edges[i].y] = dis[tt]+edges[i].val;

                 dep[edges[i].y] = dep[tt]+, pre[edges[i].y] = i, fat[edges[i].y] = tt;

                 q.push(edges[i].y);

             }

     }

     for (int i=; i<=n; i++) treeTag[pre[i]] = ;

     for (int i=; i<=edgeTot; i+=)

         if (!treeTag[i]&&!treeTag[i+]){

             int u = edges[i].y, v = edges[i+].y;

             edgeSv[++svTot] = EdgeSv(u, v, edges[i].val+dis[u]+dis[v]);

         }

     std::sort(edgeSv+, edgeSv+svTot+);

     for (int i=; i<=svTot; i++)

     {

         int u = edgeSv[i].x, v = edgeSv[i].y, lstu = , lstv = ;

         int topu = get(u), topv = get(v);

         while (topu!=topv)

         {

             if (dep[topu] < dep[topv])

                 std::swap(u, v), std::swap(lstu, lstv), std::swap(topu, topv);

             if (!tag[u]){

                 tag[u] = i;

                 if (lstu) fa[lstu] = u;

             }else if (lstu) fa[lstu] = topu;

             lstu = topu, u = fat[topu], topu = get(u);

         }

     }

     for (int i=; i<=n; i++)

         if (!tag[i]) puts("-1");

         else printf("%d\n",edgeSv[tag[i]].dis-dis[i]);

     return ;

 }

END