題意：

公司得到了一共N個可以作為通訊信號中轉站的地址，而由于這些地址的地理位置差異，在不同的地方建造通訊中轉站需要投入的成本也是不一樣的，所幸在前期調查之后這些都是已知數據：建立第i個通訊中轉站需要的成本為Pi（1≤i≤N）。 ?另外公司調查得出了所有期望中的用戶群，一共M個。關于第i個用戶群的信息概括為Ai, Bi和Ci：這些用戶會使用中轉站Ai和中轉站Bi進行通訊，公司可以獲益Ci。（1≤i≤M, 1≤Ai, Bi≤N）

?THU集團的CS&T公司可以有選擇的建立一些中轉站（投入成本），為一些用戶提供服務并獲得收益（獲益之和）。那么如何選擇最終建立的中轉站才能讓公司的凈獲利最大呢？（凈獲利 = 獲益之和 - 投入成本之和）

解題思路：這道題是《最小割模型在信息學競賽中的應用》介紹到的“最大獲利問題”，詳細的證明過程要參看論文。這里只講建圖的思路。

把每個用戶和每個站點看成是一個頂點，建立網絡，從源點s向每個用戶連一條容量為利潤的邊，每個用戶向相關站點連一條容量為無窮大的邊，每個站點向匯點連一條容量為成本的邊。求出的最小割就是maxflow = （未被選的用戶收益之和+被選的站點成本之和），設sum為總收益，我們要求的是（被選的用戶收益之和-被選的站點成本之和），剛好等于sum-maxflow。至于原因參看論文。

這里要使用非遞歸版本的dinic，我的是遞歸版本的超時了。

TLE:

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 60000; const int inf = 0x3f3f3f3f; struct Edge {int to,next,flow; }edge[maxn<<2]; int n,m,cnt,pre[maxn],layer[maxn];void addedge(int u,int v,int flow) {edge[cnt].to = v;edge[cnt].flow = flow;edge[cnt].next = pre[u];pre[u] = cnt++;swap(u,v);edge[cnt].to = v;edge[cnt].flow = 0;edge[cnt].next = pre[u];pre[u] = cnt++; }bool bfs(int s,int t) {queue<int> q;memset(layer,0,sizeof(layer));layer[s] = 0;q.push(s);while(!q.empty()){int u = q.front();q.pop();if(u == t) return true;for(int i = pre[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(edge[i].flow > 0 && layer[v] == 0){layer[v] = layer[u] + 1;q.push(v);}}}return false; }int dfs(int u,int t,int maxflow) {if(u == t) return maxflow;int uflow = 0;for(int i = pre[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(layer[v] == layer[u] + 1 && edge[i].flow > 0){int flow = min(maxflow - uflow,edge[i].flow);flow = dfs(v,t,flow);edge[i].flow -= flow;edge[i^1].flow += flow;uflow += flow;if(uflow == maxflow) break;}}if(uflow == 0)layer[u] = 0;return uflow; }int dinic(int s,int t) {int maxflow = 0;while(bfs(s,t) == true)maxflow += dfs(s,t,inf);return maxflow; }int main() {int s,t,u,v,w;while(scanf("%d%d",&n,&m)!=EOF){s = 0, t = n + m + 1;cnt = 0;memset(pre,-1,sizeof(pre));for(int i = 1; i <= n; i++){scanf("%d",&w);addedge(i,t,w);}int sum = 0;for(int i = 1; i <= m; i++){scanf("%d%d%d",&u,&v,&w);sum += w;addedge(s,n+i,w);addedge(n+i,u,inf);addedge(n+i,v,inf);}printf("%d\n",sum - dinic(s,t));}return 0; }

總結

以上是生活随笔為你收集整理的hdu 3879(最小割模型求解最大权闭合图)的全部內容，希望文章能夠幫你解決所遇到的問題。

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