題目描述

Secsa最近對(duì)最小生成樹(shù)問(wèn)題特別感興趣。他已經(jīng)知道如果要去求出一個(gè)n個(gè)點(diǎn)、m條邊的無(wú)向圖的最小生成樹(shù)有一個(gè)Krustal算法和另一個(gè)Prim的算法。另外，他還知道，某一個(gè)圖可能有多種不同的最小生成樹(shù)。例如，下面圖?3中所示的都是圖?2中的無(wú)向圖的最小生成樹(shù)：

?

當(dāng)然啦，這些都不是今天需要你解決的問(wèn)題。Secsa想知道對(duì)于某一條無(wú)向圖中的邊AB，至少需要多少代價(jià)可以保證AB邊在這個(gè)無(wú)向圖的最小生成樹(shù)中。為了使得AB邊一定在最小生成樹(shù)中，你可以對(duì)這個(gè)無(wú)向圖進(jìn)行操作，一次單獨(dú)的操作是指：先選擇一條圖中的邊?P1P2，再把圖中除了這條邊以外的邊，每一條的權(quán)值都減少1。如圖?4所示就是一次這樣的操作：

輸入

輸入文件的第一行有3個(gè)正整數(shù)n、m、Lab分別表示無(wú)向圖中的點(diǎn)數(shù)、邊數(shù)、必須要在最小生成樹(shù)中出現(xiàn)的AB邊的標(biāo)號(hào)。 接下來(lái)m行依次描述標(biāo)號(hào)為1,2,3…m的無(wú)向邊，每行描述一條邊。每個(gè)描述包含3個(gè)整數(shù)x、y、d，表示這條邊連接著標(biāo)號(hào)為x、y的點(diǎn)，且這條邊的權(quán)值為d。 輸入文件保證1<=x,y<=N,x不等于y,且輸入數(shù)據(jù)保證這個(gè)無(wú)向圖一定是一個(gè)連通圖。

輸出

輸出文件只有一行，這行只有一個(gè)整數(shù)，即，使得標(biāo)號(hào)為L(zhǎng)ab邊一定出現(xiàn)最小生成樹(shù)中的最少操作次數(shù)。

樣例輸入

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

樣例輸出

1

---

題解

網(wǎng)絡(luò)流最小割

除了這條邊以外其它邊都-1，相當(dāng)于其它邊不變，這條邊+1。

然后考慮Kruscal求最小生成樹(shù)的方法，一條邊一定出現(xiàn)在最小生成樹(shù)上，等價(jià)于所有邊權(quán)小于等于它的邊不能使得這兩個(gè)端點(diǎn)連通。

于是轉(zhuǎn)化為最小割問(wèn)題。

對(duì)于每條長(zhǎng)度小于等于給定的邊，連容量為 給定長(zhǎng)度-當(dāng)前長(zhǎng)度+1 的邊，然后跑最小割即可。

#include <queue> #include <cstdio> #include <cstring> #define N 510 #define K 810 #define M 100010 using namespace std; queue<int> q; int x[K] , y[K] , z[K] , head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N]; void add(int x , int y , int z) {to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;to[++cnt] = x , val[cnt] = z , next[cnt] = head[y] , head[y] = cnt; } bool bfs() {int x , i;memset(dis , 0 , sizeof(dis));while(!q.empty()) q.pop();dis[s] = 1 , q.push(s);while(!q.empty()){x = q.front() , q.pop();for(i = head[x] ; i ; i = next[i]){if(val[i] && !dis[to[i]]){dis[to[i]] = dis[x] + 1;if(to[i] == t) return 1;q.push(to[i]);}}}return 0; } int dinic(int x , int low) {if(x == t) return low;int temp = low , i , k;for(i = head[x] ; i ; i = next[i]){if(val[i] && dis[to[i]] == dis[x] + 1){k = dinic(to[i] , min(temp , val[i]));if(!k) dis[to[i]] = 0;val[i] -= k , val[i ^ 1] += k;if(!(temp -= k)) break;}}return low - temp; } int main() {int n , m , p , i , ans = 0;scanf("%d%d%d" , &n , &m , &p);for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d" , &x[i] , &y[i] , &z[i]);s = x[p] , t = y[p];for(i = 1 ; i <= m ; i ++ )if(i != p && z[i] <= z[p])add(x[i] , y[i] , z[p] - z[i] + 1);while(bfs()) ans += dinic(s , 1 << 30);printf("%d\n" , ans);return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7355935.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj2521】[Shoi2010]最小生成树 网络流最小割的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。