【BZOJ2521】 [Shoi2010]最小生成树

Description

Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 3中所示的都是图 2中的无向图的最小生成树：

当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB，至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 P1P2，再把图中除了这条边以外的边，每一条的权值都减少1。如图 4所示就是一次这样的操作：

Input

输入文件的第一行有3个正整数n、m、Lab分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。

接下来m行依次描述标号为1,2,3…m的无向边，每行描述一条边。每个描述包含3个整数x、y、d，表示这条边连接着标号为x、y的点，且这条边的权值为d。

输入文件保证1<=x,y<=N,x不等于y,且输入数据保证这个无向图一定是一个连通图。

Output

输出文件只有一行，这行只有一个整数，即，使得标号为Lab边一定出现最小生成树中的最少操作次数。

Sample Input

4 6 1
1 2 2
1 3 2
1 4 3
2 3 2
2 4 4
3 4 5

Sample Output

HINT

第1个样例就是问题描述中的例子。

1<=n<=500,1<=M<=800,1<=D<10^6

Source

day2

Solution

思路很神的一道题。

首先，其他所有边权值-1可以看做这条边+1。如果选定的边本来就在最小生成树上就不用管它。

如果不在MST上的话，就要考虑想办法让它在MST上。让它在MST上的条件是s,t两个联通块之间一定不存在权值比它更小的边。

对于所有比选定的边边权小的边，让它一定不出现在MST上的代价就是让它的边权变为选定的边权+1。问题就变成了选定一些边使得s和t不连通，且边权总和最小。然后就变成了最小割模型，用网络流来解决。

Code

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define maxn 510

 #define maxm 810

 #define R register

 #define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))

 #define inf 0x7fffffff

 int n;

 struct edge {int a, b, w; } ee[maxm];

 struct Edge {

     Edge *next, *rev;

     int to, cap;

 } *cur[maxn], *last[maxn], e[maxm << ], *ecnt = e;

 inline void link(R int a, R int b, R int w)

 {

     *++ecnt = (Edge) {last[a], ecnt + , b, w}; last[a] = ecnt;

     *++ecnt = (Edge) {last[b], ecnt - , a, }; last[b] = ecnt;

 }

 int s, t, dep[maxn], q[maxn], ans;

 inline bool bfs()

 {

     R int head = , tail = ;

     memset(dep, -, (n + ) << );

     dep[q[] = t] = ;

     while (head < tail)

     {

         R int now = q[++head];

         for (R Edge *iter = last[now]; iter; iter = iter -> next)

             if (iter -> rev -> cap && dep[iter -> to] == -)

                 dep[q[++tail] = iter -> to] = dep[now] + ;

     }

     return dep[s] != -;

 }

 int dfs(R int x, R int f)

 {

     if (x == t) return f;

     R int used = ;

     for (R Edge* &iter = cur[x]; iter; iter = iter -> next)

         if (iter -> cap && dep[iter -> to] +  == dep[x])

         {

             R int v = dfs(iter -> to, dmin(f - used, iter -> cap));

             iter -> cap -= v;

             iter -> rev -> cap += v;

             used += v;

             if (used == f) return f;

         }

     return used;

 }

 inline void dinic()

 {

     while (bfs())

     {

         memcpy(cur, last, sizeof cur);

         ans += dfs(s, inf);

     }

 }

 int main()

 {

     R int m, lab; scanf("%d%d%d", &n, &m, &lab);

     for (R int i = ; i <= m; ++i) scanf("%d%d%d", &ee[i].a, &ee[i].b, &ee[i].w);

     for (R int i = ; i <= m; ++i)

         if (ee[i].w <= ee[lab].w && i != lab)

         {

             link(ee[i].a, ee[i].b, ee[lab].w - ee[i].w + );

             link(ee[i].b, ee[i].a, ee[lab].w - ee[i].w + );

         }

     s = ee[lab].a; t = ee[lab].b;

     dinic();

     printf("%d\n", ans);

     return ;

 }

巴特西