題干：

Problem Description 度度熊國王率領著喵哈哈族的勇士，準備進攻嘩啦啦族。 嘩啦啦族是一個強悍的民族，里面有充滿智慧的謀士，擁有無窮力量的戰士。 所以這一場戰爭，將會十分艱難。 為了更好的進攻嘩啦啦族，度度熊決定首先應該從內部瓦解嘩啦啦族。 第一步就是應該使得嘩啦啦族內部不能同心齊力，需要內部有間隙。 嘩啦啦族一共有n個將領，他們一共有m個強關系，摧毀每一個強關系都需要一定的代價。 現在度度熊命令你需要摧毀一些強關系，使得內部的將領，不能通過這些強關系，連成一個完整的連通塊，以保證戰爭的順利進行。 請問最少應該付出多少的代價。 ? ? Input 本題包含若干組測試數據。 第一行兩個整數n，m，表示有n個將領，m個關系。 接下來m行，每行三個整數u,v,w。表示u將領和v將領之間存在一個強關系，摧毀這個強關系需要代價w 數據范圍： 2<=n<=3000 1<=m<=100000 1<=u,v<=n 1<=w<=1000 ? ? Output 對于每組測試數據，輸出最小需要的代價。 ? ? Sample Input ? 2 1 1 2 1 3 3 1 2 5 1 2 4 2 3 3 ? ? Sample Output ? 1 3 ? ? Source 2017"百度之星"程序設計大賽 - 資格賽 ?

題目大意：

求全局最小割

解題報告：

求全局最小割

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 3e3 + 5; const int INF = 0x3f3f3f3f; int G[MAX][MAX]; int dis[MAX],id[MAX]; bool vis[MAX]; int n,m; int SW(int n) {int res = INF;for(int i = 0; i<n; i++) id[i]=i;while(n>1) {memset(dis,0,sizeof dis);int k = 0;for(int i = 1; i<n; i++) {swap(id[k],id[i-1]);for(int j = k = i; j<n; j++) {dis[id[j]] += G[id[i-1]][id[j]];if(dis[id[j]] > dis[id[k]]) k = j;}}res = min(res,dis[id[k]]);int s = id[n-2],t=id[n-1];for(int i = 0; i<n-2; i++) {int u = id[i];G[u][s]=G[s][u]+=G[u][t];}id[k]=id[n--];}return res; } int main() {while(~scanf("%d%d",&n,&m)) {for(int i = 0; i<=n; i++)for(int j = 0; j<=n; j++)G[i][j]=0;for(int u,v,w,i = 1; i<=m; i++) {scanf("%d%d%d",&u,&v,&w);u--,v--;G[u][v]+=w;G[v][u]+=w;}printf("%d\n",SW(n));} return 0 ; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【HDU - 6081】度度熊的王国战略（SW算法，全局最小割）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。