題目描述

JYY創建的電信公司，壟斷著整個JSOI王國的電信網絡。JYY在JSOI王國里建造了很多的通信基站。目前所有的基站都是使用2G網絡系統的。而現在3G時代已經到來了，JYY在思考，要不要把一些基站升級成3G網絡的呢？JSOI王國可以被看作為一個無窮大的二維平面，JYY一共建造了N個通信基站，第i個基站的坐標是(Xi,Yi)。每個基站有一個通信范圍Ri。第i號基站會向所有到其距離不超過Ri的基站發送信息。每個基站升級到3G網絡都會有一個收益Si，這個收益可能是正數（比如基站附近有個大城市，用戶很多，賺的流量費也就很多了），也可能是負數（比如基站周圍市場不佳，收益不能填補升級基站本身的投資）。此外，由于原有的使用2G網絡系統的基站無法解析從升級成3G網絡系統的基站所發來的信息（但是升級之后的基站是可以解析未升級基站發來的信息的），所以，JYY必須使得，在升級工作全部完成之后，所有使用3G網絡的基站，其通信范圍內的基站，也都是使用3G網絡的。由于基站數量很多，你可以幫助JYY計算一下，他通過升級基站，最多能獲得的收益是多少嗎？

輸入

第一行一個整數N； 接下來N行，每行4個整數，Xi，Yi，Ri，Si，表示處在(Xi,Yi)的基站的通信范圍是Ri，升級可以獲得的收益是Si。數據滿足任意兩個基站的坐標不同。 1≤N≤500，1≤Ri≤20000，|Xi|,|Yi|,|Si|≤10^4。

輸出

輸出一行一個整數，表示可以獲得的最大收益。

樣例輸入

5
0 1 7 10
0 -1 7 10
5 0 1 -15
10 0 6 10
15 1 2 -20

樣例輸出

5

---

題解

最大權閉合圖

選xxx就必須選xxx，求最大總收益，顯然最大權閉合圖問題。

用兩點間距離公式求出選某個就必須選哪些，然后建圖最小割，沒了。。

#include <queue> #include <cstdio> #include <cstring> #define N 510 #define M 1000010 #define inf 1 << 30 using namespace std; queue<int> q; int x[N] , y[N] , r[N] , v[N] , head[N] , to[M] , val[M] , next[M] , cnt = 1 , s , t , dis[N]; inline 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] = 0 , 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 , i , j , sum = 0;scanf("%d" , &n) , s = 0 , t = n + 1;for(i = 1 ; i <= n ; i ++ ){scanf("%d%d%d%d" , &x[i] , &y[i] , &r[i] , &v[i]);if(v[i] > 0) add(s , i , v[i]) , sum += v[i];else add(i , t , -v[i]);}for(i = 1 ; i <= n ; i ++ )for(j = 1 ; j <= n ; j ++ )if(i != j && (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= r[i] * r[i])add(i , j , inf);while(bfs()) sum -= dinic(s , inf);printf("%d\n" , sum);return 0; }

?

?

轉載于:https://www.cnblogs.com/GXZlegend/p/7491411.html

總結

以上是生活随笔為你收集整理的【bzoj5037】[Jsoi2014]电信网络 最大权闭合图的全部內容，希望文章能夠幫你解決所遇到的問題。

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